Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
sudoku solver
val boardStr = """
53 7 |
6 195 |
98 6 |
8 6 3|
4 8 3 1|
7 2 6|
6 28 |
419 5|
8 79|
"""
val _boardStr = """
534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179
"""
// row major
val board: Array[Int] = boardStr.lines.map {
line => line.take(9).map { ch => if (ch == ' ') 0 else ch.toString.toInt }
} .flatten.toArray
def check(board: Array[Int]) = {
for (p <- 0 until 81 if board(p) > 0) {
val prev = board(p)
board(p) = 0
if (!isValidRow(p, prev)) { println(s"invalid row $p") }
if (!isValidCol(p, prev)) { println(s"invalid col $p") }
if (!isValidBlock(p, prev)) { println(s"invalid block $p") }
board(p) = prev
}
}
def choose(pos: Int): Boolean = {
if (pos >= 81) { // done
true
} else if (board(pos) > 0) { // already fixed
choose(pos+1)
} else {
var solved = false
var x = 1
while (x <= 9 && !solved) {
val valid = isValidRow(pos, x) && isValidCol(pos, x) && isValidBlock(pos, x)
if (valid) {
val prev = board(pos)
board(pos) = x
solved = choose(pos+1)
if (!solved) {
board(pos) = prev
}
}
x += 1
}
solved
}
}
board.toVector.grouped(9).toVector foreach println
check(board)
println(choose(0))
board.toVector.grouped(9).toVector foreach println
check(board)
def isValidRow(pos: Int, x: Int): Boolean = {
require(x > 0 && x <= 9)
val row = pos / 9
var i = 0
while (i < 9) {
if (board(row*9+i) == x) {
return false
}
i += 1
}
return true
}
def isValidCol(pos: Int, x: Int): Boolean = {
require(x > 0 && x <= 9)
val col = pos % 9
var i = 0
while (i < 9) {
if (board(col+i*9) == x) {
return false
}
i += 1
}
return true
}
def isValidBlock(pos: Int, x: Int): Boolean = {
require(x > 0 && x <= 9)
val blRow = (pos / 9 / 3) * 3
val blCol = ((pos % 9) / 3) * 3
var row = 0
while (row < 3) {
var col = 0
while (col < 3) {
val p = (row+blRow) * 9 + (col+blCol)
if (board(p) == x) {
return false
}
col += 1
}
row += 1
}
return true
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.