sudoku solver

sepukku.scala

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
}