Skip to content

Instantly share code, notes, and snippets.

@Veeyikpong
Created December 27, 2022 07:39
Show Gist options
  • Save Veeyikpong/2d7e3857021f2b2c606d86d63228ae6b to your computer and use it in GitHub Desktop.
Save Veeyikpong/2d7e3857021f2b2c606d86d63228ae6b to your computer and use it in GitHub Desktop.
Sudoku solver using backtracking
solveSudoku(
arrayOf(
charArrayOf('8', '.', '.', '.', '.', '.', '.', '.', '.'),
charArrayOf('.', '.', '3', '6', '.', '.', '.', '.', '.'),
charArrayOf('.', '7', '.', '.', '9', '.', '2', '.', '.'),
charArrayOf('.', '5', '.', '.', '.', '7', '.', '.', '.'),
charArrayOf('.', '.', '.', '.', '4', '5', '7', '.', '.'),
charArrayOf('.', '.', '.', '1', '.', '.', '.', '3', '.'),
charArrayOf('.', '.', '1', '.', '.', '.', '.', '6', '8'),
charArrayOf('.', '.', '8', '5', '.', '.', '.', '1', '.'),
charArrayOf('.', '9', '.', '.', '.', '.', '4', '.', '.')
)
)
fun solveSudoku(board: Array<CharArray>): Unit {
if (!solve(board)) print("No solution")
}
fun solve(board: Array<CharArray>): Boolean {
var emptyRow = -1
var emptyCol = -1
outerLoop@ for (i in board.indices) {
for (j in board.indices) {
if (board[i][j] == '.') {
emptyRow = i
emptyCol = j
break@outerLoop
}
}
}
if (emptyRow == -1 && emptyCol == -1) {
return true
}
for (n in 1..9) {
val char = '0' + n
if (isValid(board, emptyRow, emptyCol, char)) {
board[emptyRow][emptyCol] = char
if (solve(board)) {
return true
} else {
board[emptyRow][emptyCol] = '.'
}
}
}
return false
}
fun isValid(board: Array<CharArray>, row: Int, col: Int, num: Char): Boolean {
// check row
for (colIndex in board.indices) {
if (board[row][colIndex] == num) return false
}
// check col
for (rowIndex in board.indices) {
if (board[rowIndex][col] == num) return false
}
// check box
val boxSize = 3
val boxRowStartIndex = row - row % boxSize
val boxColStartIndex = col - col % boxSize
for (index in boxRowStartIndex..boxRowStartIndex + 2) {
for (index1 in boxColStartIndex..boxColStartIndex + 2) {
if (board[index][index1] == num) return false
}
}
return true
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment