Generating Sudoku Puzzles with Backtracking in Kotlin: A Simple Approach

Last time I wrote about my Sudoku project, I was still working on the puzzle logic. Since then, I’ve made progress, and today I decided to share how I implemented Sudoku puzzle generation for my app. In previous posts, I mentioned how much I love Sudoku. I’ve been solving it even more ever since dementia showed up in my family. It’s a great way to keep my brain sharp, and I truly hope it will preserve my mental vitality. But let’s get back to the logic. Initially, I planned to build the whole project in Kotlin using the Ktor framework. I’ve strayed from this plan a little, especially regarding authentication, but I’ll cover that another time.

How Does Sudoku Logic Come to Life?

The rules of Sudoku are simple: You get a 9×9 grid, and your job is to fill in numbers from 1 to 9. However, the twist is that you can’t repeat numbers in any row, column, or 3×3 subgrid. There are several ways to generate a valid Sudoku solution, but I decided to use backtracking.

In this article, I’ll show you how to implement a fully populated Sudoku grid using recursive backtracking in Kotlin.

How Does Sudoku Generation Work?

Here’s a quick rundown of the algorithm:

1. Traverse the grid and find the first empty spot (a zero).
2. Try placing numbers 1–9 in a random order into this spot.
3. If the number is valid (i.e., it doesn’t appear in the same row, column, or 3×3 box), set it and move to the next empty spot.
4. If there’s no valid solution at some point, backtrack and try other numbers.
5. This process continues until the entire grid is filled.

Kotlin Code Implementation

My task was to create a Sudoku.kt class that generates a valid Sudoku grid.

package com.example

class Sudoku {
    private val grid = Array(9) { IntArray(9) }

    fun generateSudoku(): Array<IntArray> {
        fillGrid()
        return grid
    }

    private fun fillGrid(): Boolean {
        for (row in 0 until 9) {
            for (column in 0 until 9) {
                if (grid[row][column] == 0) {
                    val numbers = (1..9).shuffled()
                    for (number in numbers) {
                        if (isValidGrid(row, column, number)) {
                            grid[row][column] = number
                            if (fillGrid()) return true
                            grid[row][column] = 0
                        }
                    }
                    return false
                }
            }
        }
        return true
    }

    private fun isValidGrid(row: Int, column: Int, number: Int): Boolean {
        return !isInRow(row, number) && !isInColumn(column, number) && !isInBox(row, column, number)
    }

    private fun isInRow(row: Int, number: Int): Boolean = grid[row].contains(number)

    private fun isInColumn(column: Int, number: Int): Boolean = grid.any { it[column] == number }

    private fun isInBox(row: Int, column: Int, number: Int): Boolean {
        val startRow = row - row % 3
        val startColumn = column - column % 3
        for (i in 0 until 3) {
            for (j in 0 until 3) {
                if (grid[startRow + i][startColumn + j] == number) {
                    return true
                }
            }
        }
        return false
    }
}

fun main() {
    val sudoku = Sudoku()
    val grid = sudoku.generateSudoku()
    for (row in grid) {
        println(row.joinToString(" "))
    }
}

Code Breakdown

• grid: A 9×9 array representing the Sudoku grid.
• generateSudoku(): Starts the Sudoku generation and returns the filled grid.
• fillGrid(): Recursively fills the grid using backtracking.
• isValidGrid(): Checks if a number can be placed in the given position.
• isInRow(), isInColumn(), isInBox(): Helper functions to check if the number already exists in the row, column, or 3×3 subgrid.

Conclusion

In this article, we’ve learned how to generate a valid Sudoku grid using backtracking in Kotlin. This algorithm is easy to implement, but it can be a bit slow when generating grids with certain constraints. You could optimize it by adjusting the number selection order or by pre-filling some cells to speed things up.

I hope this article helped you understand how Sudoku generation works! If you have any questions or suggestions for improvements, feel free to share them in the comments below.