Last active
January 13, 2023 17:38
-
-
Save hilios/a1aded27cab1d16ab25016d9846d3e4c to your computer and use it in GitHub Desktop.
Sudoku solver (kotlin)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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") | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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() | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment