Let's make the Sudoku generator library in Kotlin

Rules

I guess that the first thing I should do is explaining the rules of Sudoku. Therefore, if you know them, you can go to the next paragraph without worries. For those who stayed with me here, I have a few pieces of information/rules you should get familiar with:

• A classic Sudoku puzzle, which is an object of my interest, is a grid of 81 cells, so it’s size is 9x9
• The grid is divided into 9 smaller 3x3 boxes, each containing 9 cells
• The grid is filled partially with digits from 1 to 9
• The purpose of the puzzle is to fill the rest of the cells with digits from 1 to 9 considering the following principles:
  • Each of 9 boxes has to contain exactly 9 distinct digits from 1 to 9
  • Each row and column of the grid also has to contain exactly 9 distinct digits from 1 to 9
  • Every sudoku puzzle has only one correct solution

Algorithm

Before we start, I will describe the algorithm that we will use to make the generator. I divided it into 3 main steps:

1. Fill diagonal boxes with digits from 1 to 9
2. Fill the rest of empty cells in non-diagonal boxes with digits from 1 to 9 while checking if each is not already used in box, row or column
3. Remove digits from the random cells only if the puzzle is still solvable after each removal and repeat that until the desired number of digits remain on a grid.

Implementation

Everything we are going to do next, is in my GitHub repository. I will provide you a link at the end of the post.

Starting the project with Gradle

I encourage you to use Gradle’s Build Init plugin as a tool to produce our library. Below is how you do it in terminal (assuming you already have the Gradle):

$ mkdir sudoku-lib-kotlin
$ cd sudoku-lib-kotlin/
$ gradle init
Starting a Gradle Daemon, 1 busy Daemon could not be reused, use --status for details
> Task :wrapper

Select type of project to generate:
  1: basic
  2: application
  3: library
  4: Gradle plugin
Enter selection (default: basic) [1..4] 3

Select implementation language:
  1: C++
  2: Groovy
  3: Java
  4: Kotlin
  5: Scala
  6: Swift
Enter selection (default: Java) [1..6] 4

Select build script DSL:
  1: Groovy
  2: Kotlin
Enter selection (default: Kotlin) [1..2] 2

Project name (default: sudoku-lib-kotlin): 

Source package (default: sudoku.lib.kotlin): 

> Task :init

BUILD SUCCESSFUL in 27s
2 actionable tasks: 2 executed

And that’s it. It cannot be simpler. Now you have everything to start implementing the Sudoku generator algorithm.

Preparation

Let’s create a file Constants.kt with constants shared in the whole project, just to keep tidiness in our project.

@file:JvmName("Constants")

internal const val GRID_SIZE = 9
internal const val GRID_SIZE_SQUARE_ROOT = 3
internal const val MIN_DIGIT_VALUE = 1
internal const val MAX_DIGIT_VALUE = 9
internal const val MIN_DIGIT_INDEX = 0
internal const val MAX_DIGIT_INDEX = 8
internal const val BOX_SIZE = 3

Thanks to @file:JvmName("Constants") you can use any of the constants simply typing e.g. this GRID_SIZE, not ConstantsKt.GRID_SIZE. Here we have sizes of our Sudoku grid and boxes. Also, max and min values for digits used in the puzzle and other useful stuff.

Another helpful file will be enum called Level, which will be indicating Sudoku’s difficulty. Each level has a defined number of digits that should remain in a grid after removal to generate it. I made sure that the names of levels are familiar to you, dear programmers.

enum class Level(val numberOfProvidedDigits: Int) {
    JUNIOR(25),
    MID(20),
    SENIOR(17);
}

Solver

In the algorithm description, I mentioned checking if the grid is still solvable after each digit removal. To make it possible, we need to implement a solver. It will be a simple, backtracking algorithm. Backtracking is an technique that solves problems recursively. It tries to build a solution piece by piece incrementally. I will go back to that in the right moment to give you an example.

This is the way the Solver works:

• Iterates through all cells in the grid
• In each cell it checks if the digit is equal 0 (0 means that it’s empty)
• If that is so, then it takes an int range from 1 to 9 inclusively and tries to shrink that collection to only available digits that can be put to that cell. To be more specific, it checks if each digit of the available is not already used in the same row, column and 3x3 box. Thanks to that check, the number of further iterations decreases significantly.
• Once the Solver has possible digits that can be put into a specific cell, the backtracking technique comes in. It puts the first one from available digits and goes on with filling other cells of the grid. If it finishes with a success, the Sudoku is solved, but if it fails, it goes back to the cell from where it started, tries another one and again goes to other cells to try its luck and fill them all with success.

We will make an internal object which acts as a singleton. Some things to draw attention to:

• Solver makes a copy of the grid it will operate on, because in fact, we don’t really want to solve it, but we just want to check if it’s solvable.
• Check how the algorithm limits the set of available digits in terms of a possible solution.
• Look at how the recursion works and how the result is handled.

internal object Solver {

    lateinit var grid: Array

    fun solvable(grid: Array) : Boolean {
        this.grid = grid.copy()

        return solve()
    }

    private fun Array.copy() = Array(size) { get(it).clone() }

    private fun solve() : Boolean {
        for (i in 0 until GRID_SIZE) {
            for (j in 0 until GRID_SIZE) {
                if (grid[i][j] == 0) {
                    val availableDigits = getAvailableDigits(i, j)
                    for (k in availableDigits) {
                        grid[i][j] = k
                        if (solve()) {
                            return true
                        }
                        grid[i][j] = 0
                    }
                    return false
                }
            }
        }
        return true
    }

    private fun getAvailableDigits(row: Int, column: Int) : Iterable {
        val digitsRange = MIN_DIGIT_VALUE..MAX_DIGIT_VALUE
        var availableDigits = mutableSetOf()
        availableDigits.addAll(digitsRange)

        truncateByDigitsAlreadyUsedInRow(availableDigits, row)
        if (availableDigits.size > 1) {
            truncateByDigitsAlreadyUsedInColumn(availableDigits, column)
        }
        if (availableDigits.size > 1) {
            truncateByDigitsAlreadyUsedInBox(availableDigits, row, column)
        }

        return availableDigits.asIterable()
    }

    private fun truncateByDigitsAlreadyUsedInRow(availableDigits: MutableSet, row: Int) {
        for (i in MIN_DIGIT_INDEX..MAX_DIGIT_INDEX) {
            if (grid[row][i] != 0) {
                availableDigits.remove(grid[row][i])
            }
        }
    }

    private fun truncateByDigitsAlreadyUsedInColumn(availableDigits: MutableSet, column: Int) {
        for (i in MIN_DIGIT_INDEX..MAX_DIGIT_INDEX) {
            if (grid[i][column] != 0) {
                availableDigits.remove(grid[i][column])
            }
        }
    }

    private fun truncateByDigitsAlreadyUsedInBox(availableDigits: MutableSet, row: Int, column: Int) {
        val rowStart = findBoxStart(row)
        val rowEnd = findBoxEnd(rowStart)
        val columnStart = findBoxStart(column)
        val columnEnd = findBoxEnd(columnStart)

        for (i in rowStart until rowEnd) {
            for (j in columnStart until columnEnd) {
                if (grid[i][j] != 0) {
                    availableDigits.remove(grid[i][j])
                }
            }
        }
    }

    private fun findBoxStart(index: Int) = index - index % GRID_SIZE_SQUARE_ROOT

    private fun findBoxEnd(index: Int) = index + BOX_SIZE - 1
}

Generator

Finally, when we have our project prepared (including the Solver), we can proceed to the main part of this post. Above, I already gave you the algorithm on how the puzzle will be generated. So, let me show you the implementation first and then briefly describe it.

import kotlin.random.Random

class Sudoku private constructor(level: Level?) {

    val grid = Array(GRID_SIZE) { IntArray(GRID_SIZE) {0} }

    private val level: Level = level ?: Level.JUNIOR

    init {
        fillGrid()
    }

    fun printGrid() {
        for (i in 0 until GRID_SIZE) {
            for (j in 0 until GRID_SIZE) {
                print(grid[i][j].toString().plus(" "))
            }
            println()
        }
        println()
    }

    private fun fillGrid() {
        fillDiagonalBoxes()
        fillRemaining(0, GRID_SIZE_SQUARE_ROOT)
        removeDigits()
    }

    private fun fillDiagonalBoxes() {
        for (i in 0 until GRID_SIZE step GRID_SIZE_SQUARE_ROOT) {
            fillBox(i, i)
        }
    }

    private fun fillBox(row: Int, column: Int) {
        var generatedDigit: Int

        for (i in 0 until GRID_SIZE_SQUARE_ROOT) {
            for (j in 0 until GRID_SIZE_SQUARE_ROOT) {
                do {
                    generatedDigit = generateRandomInt(MIN_DIGIT_VALUE, MAX_DIGIT_VALUE)
                } while (!isUnusedInBox(row, column, generatedDigit))

                grid[row + i][column + j] = generatedDigit
            }
        }
    }

    private fun generateRandomInt(min: Int, max: Int) = Random.nextInt(min, max + 1)

    private fun isUnusedInBox(rowStart: Int, columnStart: Int, digit: Int) : Boolean {
        for (i in 0 until GRID_SIZE_SQUARE_ROOT) {
            for (j in 0 until GRID_SIZE_SQUARE_ROOT) {
                if (grid[rowStart + i][columnStart + j] == digit) {
                    return false
                }
            }
        }
        return true
    }

    private fun fillRemaining(i: Int, j: Int) : Boolean {
        var i = i
        var j = j

        if (j >= GRID_SIZE && i < GRID_SIZE - 1) {
            i += 1
            j = 0
        }
        if (i >= GRID_SIZE && j >= GRID_SIZE) {
            return true
        }
        if (i < GRID_SIZE_SQUARE_ROOT) {
            if (j < GRID_SIZE_SQUARE_ROOT) {
                j = GRID_SIZE_SQUARE_ROOT
            }
        } else if (i < GRID_SIZE - GRID_SIZE_SQUARE_ROOT) {
            if (j == (i / GRID_SIZE_SQUARE_ROOT) * GRID_SIZE_SQUARE_ROOT) {
                j += GRID_SIZE_SQUARE_ROOT
            }
        } else {
            if (j == GRID_SIZE - GRID_SIZE_SQUARE_ROOT) {
                i += 1
                j = 0
                if (i >= GRID_SIZE) {
                    return true
                }
            }
        }

        for (digit in 1..MAX_DIGIT_VALUE) {
            if (isSafeToPutIn(i, j, digit)) {
                grid[i][j] = digit
                if (fillRemaining(i, j + 1)) {
                    return true
                }
                grid[i][j] = 0
            }
        }
        return false
    }

    private fun isSafeToPutIn(row: Int, column: Int, digit: Int) =
            isUnusedInBox(findBoxStart(row), findBoxStart(column), digit)
                    && isUnusedInRow(row, digit)
                    && isUnusedInColumn(column, digit)

    private fun findBoxStart(index: Int) = index - index % GRID_SIZE_SQUARE_ROOT

    private fun isUnusedInRow(row: Int, digit: Int) : Boolean {
        for (i in 0 until GRID_SIZE) {
            if (grid[row][i] == digit) {
                return false
            }
        }
        return true
    }

    private fun isUnusedInColumn(column: Int, digit: Int) : Boolean {
        for (i in 0 until GRID_SIZE) {
            if (grid[i][column] == digit) {
                return false
            }
        }
        return true
    }

    private fun removeDigits() {
        var digitsToRemove = GRID_SIZE * GRID_SIZE - level.numberOfProvidedDigits

        while (digitsToRemove > 0) {
            val randomRow = generateRandomInt(MIN_DIGIT_INDEX, MAX_DIGIT_INDEX)
            val randomColumn = generateRandomInt(MIN_DIGIT_INDEX, MAX_DIGIT_INDEX)

            if (grid[randomRow][randomColumn] != 0) {
                val digitToRemove = grid[randomRow][randomColumn]
                grid[randomRow][randomColumn] = 0
                if (!Solver.solvable(grid)) {
                    grid[randomRow][randomColumn] = digitToRemove
                } else {
                    digitsToRemove --
                }
            }
        }
    }

    class Builder {
        private lateinit var level: Level

        fun setLevel(level: Level) : Builder {
            this.level = level
            return this
        }

        fun build() : Sudoku {
            return Sudoku(this.level)
        }
    }
}

I decided to give this class a private constructor with Level enum as a parameter and make a Builder as the only way to initialize Sudoku. What is more, in the constructor, I made the difficulty level nullable to let the consumer of the library decide if he wants to set the level in the builder or skip it. If it’s skipped, then the default value JUNIOR is set. Also, I made one public method printGrid(), which I guess I don’t need to explain. Of course, it’s up to you how you would like to consume the lib, so feel free to make adjustments.

Ok, let’s go to the algorithm implementation, which starts in fillGrid() method. It can be divided into 3 parts:

• Filling diagonal boxes.
  Sudoku puzzle has 3 diagonal 3x3 boxes that share neither common rows nor columns. Because of that, it’s super safe to fill them first with digits from 1 to 9 and to already have 33% of the grid completed.
• Filling all remaining cells.
  Here we have a recursion again. We are iterating through all empty cells from non-diagonal boxes and taking the random digit from 1 to 9 to check if it’s safe to put it in just like in the Solver implementation until we find the correct one.
• Removing the desired number of digits.
  Once we have made a grid with correctly filled digits, we have to remove some of them to complete the Sudoku puzzle. The number of removed digits is dependent on the given difficulty level. So, until the desired number of digits is removed, we take the digit from the random row and column and check if removing it is safe. By writing “safe” I mean the fact that, after this action, the Sudoku is still solvable. That’s all. After the third step, we have our Sudoku puzzle ready.

Library

To accomplish our goal set at the beginning of this post, we should publish our project as a library. We will create a jar file and place it in the {projectDir}/build/repository directory. The task is quite simple. There are only a few steps. Let’s add some necessary things in build.gradle.kts. At first, add a plugin in the plugins section that will basically do the job for us.

`maven-publish`

Next, add these two lines wherever you want in this script. Of course, change the group name to the same as you set as a project group with gradle init command. Also, it’s up to you which version you type.

group = "org.example"
version = "0.0.1"

Then, add the configuration of how Gradle should make the publication.

publishing {
   publications {
       create("default") {
           from(components["java"])
       }
   }
   repositories {
       maven {
           url = uri("$buildDir/repository")
       }
   }
}

Optionally, you can change the name of the project in settings.gradle.kts script. By default, it’s just the project directory name.

rootProject.name = "sudoku-lib-kotlin"

Finally, we are ready to publish the library by typing gradle publish in the terminal in the project directory.

$ gradle publish
> Task :generatePomFileForDefaultPublication
> Task :compileKotlin
> Task :compileJava NO-SOURCE
> Task :processResources NO-SOURCE
> Task :classes UP-TO-DATE
> Task :inspectClassesForKotlinIC
> Task :jar
> Task :publishDefaultPublicationToMavenRepository
> Task :publish

BUILD SUCCESSFUL in 826ms
5 actionable tasks: 5 executed

Now, you can check that there is a JAR file in {projectDir}/build/repository directory, which you can use in any other project without implementing the Sudoku generator again. You can create a basic Kotlin project and add our JAR file to external libraries. For example, in Intellij, you can do it here:

File -> Project Structure -> Project Settings -> Libraries

Once you have done it you will be able to put this code in the main executable method:

Sudoku.Builder().setLevel(Level.SENIOR).build().printGrid()

I mentioned before that this is how I wanted my lib to be used:

• Initialized by the Builder
• With optional Level setter
• With public printGrid() method

Let’s run it and check the output:

0 0 9 1 0 0 0 0 0 
0 0 0 0 0 0 1 0 9 
0 5 0 0 9 8 2 0 0 
0 0 0 0 0 1 0 4 0 
0 0 0 0 0 0 3 0 0 
0 0 5 0 3 0 0 0 0 
9 0 0 6 0 2 0 0 0 
0 0 0 0 0 0 0 0 3 
0 0 0 0 0 0 0 0 0

The result looks promising. We can see a 9x9 grid with 17 digits different than 0, because of the SENIOR level. The last step would be solving it, but I leave it to you :)

As I mentioned I the project is in my GitHub repository so feel free to check it out: https://github.com/TypicalDevStuff/sudoku-generator

Summary

In this post, I showed you how to make a library in Kotlin, which generates the popular Sudoku puzzle. We built it and published it with the help of the Gradle and Maven Publish plugin. We also used a recursive backtracking algorithm to accomplish the implementation of the generator and solver. I guess that I have no choice but to use this library in a mobile application, as I promised. Also, as always, I encourage you to share this post and your thoughts about it below.

• Kotlin
• Github
• Programming