SudokuSolver.kt

import kotlin.time.ExperimentalTime
import kotlin.time.measureTime

typealias Board = Array<IntArray>

data class SpotRank(
    val at: Pos,
    val opts: Set<Int>,
)

operator fun Board.get(at: Pos) = this[at.row][at.col]
operator fun Board.set(at: Pos, value: Int) {
    this[at.row][at.col] = value
}

fun Board.allInBlock(at: Pos, includeSelf: Boolean = false): Set<Int> {
    val elems = mutableSetOf<Int>()
    val blockBase = (at.row / 3 * 3) to (at.col / 3 * 3)
    for (row in blockBase.row until blockBase.row + 3) {
        for (col in blockBase.col until blockBase.col + 3) {
            if (!includeSelf && (row == at.row && col == at.col)) continue
            if (this[row][col] == 0) continue
            elems += this[row][col]
        }
    }
    return elems
}

fun Board.allInCol(at: Pos, includeSelf: Boolean = false): Set<Int> {
    return (0..8).filter { includeSelf || it != at.row }.map { this[it][at.col] }.filter { it != 0 }.toSet()
}

fun Board.allInRow(at: Pos, includeSelf: Boolean = false): Set<Int> {
    return (0..8).filter { includeSelf || it != at.col }.map { this[at.row][it] }.filter { it != 0 }.toSet()
}

fun positions() = (0 until 9).flatMap { row -> (0 until 9).map { col -> row to col } }
val positions = positions()

fun Board.checkValid(): Boolean {
    if (any { it.any { it == 0 } }) return false

    return positions.all {
        allInRow(it, true).size == 9 ||
                allInCol(it, true).size == 9 ||
                allInBlock(it, true).size == 9
    }
}

fun Board.print() {
    val hsplit = "-".repeat(19) + "\n"
    val result = asList().windowed(size = 3, step = 3) {
        it.joinToString(separator = "\n", postfix = "\n") { row ->
            row.asList().windowed(size = 3, step = 3) { rowGroup ->
                rowGroup.joinToString(separator = " ")
            }.joinToString(separator = "|", prefix = "|", postfix = "|")
        }
    }.joinToString(separator = hsplit, prefix = hsplit, postfix = hsplit)
    print(result)
}

// Returns empty if no valid options available
fun Board.findOptions(at: Pos) = (1..9).toMutableSet().apply {
    // Could flatten
    this -= allInBlock(at)
    this -= allInRow(at)
    this -= allInCol(at)
}

fun solve(board: Board): Boolean {
    if (board.checkValid()) {
        board.print()
        return true
    }

    val elem = positions
        .filter { board[it] == 0 }
        .map { SpotRank(it, board.findOptions(it)) }
        .minByOrNull { it.opts.size }!!

    when (elem.opts.size) {
        // Check if we hit an impossible case
        0 -> return false
        else -> {
            // Try DFS, returning if we have a solved solution
            for (opt in elem.opts) {
                board[elem.at] = opt
                if (solve(board)) {
                    return true
                }
            }
            // Try to solve w/ DFS, no solution, maybe try some other path
            board[elem.at] = 0
        }
    }

    return false
}

val sudok4 = """000 000 030
                349 001 200
                050 000 900
                020 508 000
                000 000 867
                600 000 004
                000 600 000
                598 704 000
                700 200 008"""


val boardInput = sudok4
    .filter { !it.isWhitespace() || it == '\n' }
    .split("\n")
    .map { it.map { digit -> digit.digitToInt() }.toIntArray() }.toTypedArray()

@OptIn(ExperimentalTime::class)
fun main() {
    println(measureTime { solve(boardInput) })
}