Sudoku solver (kotlin)

Main.kt

import kotlin.time.ExperimentalTime
import kotlin.time.measureTimedValue

@OptIn(ExperimentalTime::class)
fun main() {
    val empty = listOf(
       0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0,
    )

    val hard = listOf(
       5, 0, 0, 0, 0, 0, 0, 0, 3,
       0, 0, 6, 0, 0, 9, 2, 5, 0,
       7, 0, 0, 0, 4, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 8, 0, 0,
       0, 2, 0, 9, 0, 0, 0, 0, 0,
       0, 0, 5, 0, 0, 2, 6, 1, 0,
       6, 0, 0, 7, 0, 0, 1, 3, 0,
       0, 0, 0, 0, 0, 1, 0, 0, 8,
       0, 0, 3, 0, 0, 0, 0, 0, 9,
    )

    val data = listOf(
       0, 3, 0, 0, 0, 0, 0, 8, 0,
       5, 0, 0, 0, 6, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 8, 2, 1, 9,
       0, 0, 7, 9, 0, 0, 0, 6, 0,
       0, 0, 0, 0, 0, 7, 0, 0, 2,
       0, 0, 0, 2, 0, 0, 1, 0, 0,
       0, 7, 1, 3, 4, 0, 0, 0, 0,
       2, 0, 0, 0, 0, 0, 4, 0, 3,
       0, 0, 9, 0, 0, 0, 0, 0, 0,
    )

    val easy = listOf(
       0, 0, 0, 4, 6, 0, 0, 3, 0,
       3, 9, 0, 0, 0, 1, 7, 0, 5,
       2, 8, 4, 0, 0, 0, 0, 9, 0,
       5, 0, 0, 8, 7, 0, 6, 1, 3,
       8, 3, 1, 0, 9, 0, 0, 0, 0,
       0, 0, 2, 5, 1, 0, 0, 8, 0,
       0, 6, 0, 0, 0, 0, 9, 0, 0,
       4, 0, 5, 0, 2, 6, 3, 0, 0,
       0, 0, 0, 0, 4, 7, 5, 6, 1,
    )

    val solved = listOf(
       1, 5, 7, 4, 6, 9, 8, 3, 2,
       3, 9, 6, 2, 8, 1, 7, 4, 5,
       2, 8, 4, 7, 3, 5, 1, 9, 6,
       5, 4, 9, 8, 7, 2, 6, 1, 3,
       8, 3, 1, 6, 9, 4, 2, 5, 7,
       6, 7, 2, 5, 1, 3, 4, 8, 9,
       7, 6, 3, 1, 5, 8, 9, 2, 4,
       4, 1, 5, 9, 2, 6, 3, 7, 8,
       9, 2, 8, 3, 4, 7, 5, 6, 1,
    )

    val foo = listOf(
        0, 6, 9, 7, 5, 0, 8, 0, 2,
        0, 8, 0, 0, 9, 3, 0, 0, 0,
        7, 0, 0, 0, 8, 2, 0, 9, 6,
        0, 0, 0, 5, 0, 0, 0, 0, 0,
        0, 5, 0, 3, 0, 7, 4, 0, 9,
        3, 4, 7, 0, 2, 9, 0, 0, 1,
        8, 7, 2, 0, 4, 5, 0, 1, 3,
        0, 0, 0, 0, 3, 8, 0, 5, 0,
        5, 0, 0, 2, 0, 0, 0, 0, 0,
    )

    val result = measureTimedValue {
        Sudoku(foo)
    }

    val time = "(time ${result.duration.inWholeMilliseconds}ms)".padStart(37)
    println("Solution:\n${result.value}\n$time")
}

Sudoku.kt

typealias Board = List<List<Int>>

object Sudoku {

    const val GRID_SIZE = 9
    const val SUBGRID_SIZE = 3
    const val EMPTY = 0
    val DIGITS = (1..9).toSet()
    val SQUARES = DIGITS.flatMap { r ->
        DIGITS.map { c -> r - 1 to c - 1 }
    }
    private const val SEPARATOR = "+-----------+-----------+-----------+"

    operator fun invoke(input: List<Int>): String {
        require(input.size == SQUARES.size) { "The board must be a 9x9 grid" }
        val sanitized = input.filter { (DIGITS + EMPTY).contains(it) }
        require(sanitized.size == SQUARES.size) {
            "All squares should be filled with numbers from 1-9 or 0 w" +
                "hen empty"
        }
        val board = sanitized.windowed(GRID_SIZE, GRID_SIZE)
        return solve(board)?.let(::debug) ?: throw IllegalStateException("no solution found")
    }

    fun debug(board: Board): String =
        buildString {
            append(SEPARATOR)
            board.windowed(SUBGRID_SIZE, SUBGRID_SIZE).forEach { subgrid ->
                append(subgrid.joinToString("\n", "\n", "\n") { row ->
                    row.joinToString(" | ", "| ", " |") { col ->
                        col.takeIf { it != EMPTY }?.toString() ?: " "
                    }
                })
                append(SEPARATOR)
            }
        }

    /**
     * Return the solution of the board using a backtracking algorithm
     */
    private fun solve(board: Board): Board? {
        if (board.isSolved()) return board

        SQUARES.forEach { (row, col) ->
            if (board[row][col] == EMPTY) {
                val s = board.solutions(row, col)
                s.forEach { n ->
                    val result = solve(board.update(row, col, n))
                    if (result != null) return result
                }
                return null
            }
        }

        return null
    }

    /**
     * Check if row, column and subgrid has only digits from 1 to 9
     */
    private fun Board.isSolved(): Boolean =
        (0 until GRID_SIZE).fold(true) { result, i ->
            result && row(i) == DIGITS && col(i) == DIGITS && subgrid(i) == DIGITS
        }

    /**
     * Returns the set of possible numbers for a particular square considering
     * all number on the row, column and subgrid.
     */
    private fun Board.solutions(row: Int, col: Int): Set<Int> {
        val n = this[row][col]
        return if (n == EMPTY) {
            val idx = (row / SUBGRID_SIZE * SUBGRID_SIZE) + (col / SUBGRID_SIZE)
            return  DIGITS - row(row) - col(col) - subgrid(idx) - EMPTY
        } else setOf(n)
    }

    /** Return the set of numbers in a particular row */
    private fun Board.row(idx: Int): Set<Int> = this[idx].toSet() - EMPTY

    /** Return the set of numbers in a particular column */
    private fun Board.col(idx: Int): Set<Int> = mapNotNull { it[idx] }.toSet() - EMPTY

    /**
     * Returns the set of numbers in the 3x3 grid a particular square
     * */
    private fun Board.subgrid(idx: Int): Set<Int> {
        val row = idx / SUBGRID_SIZE * SUBGRID_SIZE
        val col = idx % SUBGRID_SIZE * SUBGRID_SIZE
        return setOfNotNull(
            this[row+0][col+0],
            this[row+0][col+1],
            this[row+0][col+2],
            this[row+1][col+0],
            this[row+1][col+1],
            this[row+1][col+2],
            this[row+2][col+0],
            this[row+2][col+1],
            this[row+2][col+2],
        ) - EMPTY
    }

    /**
     * Returns an immutable list with the value at give square updated
     */
    private fun Board.update(row: Int, col: Int, value: Int): Board {
        val r = this.toMutableList()
        val c = r[row].toMutableList()
        c[col] = value
        r[row] = c.toList()
        return r.toList()
    }
}