#!/usr/bin/python
"""Simple brute-force Sudoku solver (FP style)."""
import re
import sys
def first(it, default=None):
"""Return first element in iterator (default if exhausted)."""
return next(it, default)
def copy_board(board, sets):
"""Return a copy of board setting new squares from 'values' dictionary."""
return [[sets.get((r, c), board[r][c]) for c in range(9)] for r in range(9)]
def get_alternatives_for_square(board, nrow, ncolumn):
"""Return sequence of valid digits for square (nrow, ncolumn) in board."""
def _box(idx, size=3):
"""Return indexes to cover a box (3x3 sub-matrix of a board)."""
start = (idx // size) * size
return range(start, start + size)
nums_in_box = [board[r][c] for r in _box(nrow) for c in _box(ncolumn)]
nums_in_row = [board[nrow][c] for c in range(9)]
nums_in_column = [board[r][ncolumn] for r in range(9)]
groups = [nums_in_box, nums_in_row, nums_in_column]
return sorted(set(range(1, 9+1)) - reduce(set.union, map(set, groups)))
def solve(board):
"""Return a solved Sudoku board (None if no solution was found)."""
pos = first((r, c) for r in range(9) for c in range(9) if not board[r][c])
if not pos:
# all squares are filled, so this board is the solution
return board
nrow, ncolumn = pos
for test_digit in get_alternatives_for_square(board, nrow, ncolumn):
test_board = copy_board(board, {(nrow, ncolumn): test_digit})
solved_board = solve(test_board)
if solved_board:
return solved_board
def lines2board(lines):
"""Parse a text board setting 0's for empty squares."""
spaces = re.compile("\s+")
return [[(int(c) if c in "123456789" else 0) for c in spaces.sub("", line)]
for line in lines if line.strip()]
def main(args):
"""Solve a Sudoku board read from a text file."""
from pprint import pprint
path, = args
board = lines2board(open(path))
pprint(board)
pprint(solve(board))
if __name__ == '__main__':
sys.exit(main(sys.argv[1:]))
Diff to Previous Revision
--- revision 5 2010-04-12 09:42:05
+++ revision 6 2010-04-12 18:34:59
@@ -3,44 +3,47 @@
import re
import sys
-def copy_board(board, values):
- """Return a copy of board setting new squares from values dictionary."""
- return [[values.get((r, c), board[r][c]) for c in range(9)] for r in range(9)]
+def first(it, default=None):
+ """Return first element in iterator (default if exhausted)."""
+ return next(it, default)
+
+def copy_board(board, sets):
+ """Return a copy of board setting new squares from 'values' dictionary."""
+ return [[sets.get((r, c), board[r][c]) for c in range(9)] for r in range(9)]
def get_alternatives_for_square(board, nrow, ncolumn):
"""Return sequence of valid digits for square (nrow, ncolumn) in board."""
- def _box(pos, size=3):
- start = (pos // size) * size
+ def _box(idx, size=3):
+ """Return indexes to cover a box (3x3 sub-matrix of a board)."""
+ start = (idx // size) * size
return range(start, start + size)
nums_in_box = [board[r][c] for r in _box(nrow) for c in _box(ncolumn)]
nums_in_row = [board[nrow][c] for c in range(9)]
nums_in_column = [board[r][ncolumn] for r in range(9)]
groups = [nums_in_box, nums_in_row, nums_in_column]
- return sorted(set(range(1, 10)) - reduce(set.union, map(set, groups)))
+ return sorted(set(range(1, 9+1)) - reduce(set.union, map(set, groups)))
def solve(board):
- """Return a solved Sudoku board (None if it has no solution)."""
- for nrow, ncolumn in ((r, c) for r in range(9) for c in range(9)):
- if board[nrow][ncolumn]:
- continue # digit set, move to the next square
- for test_digit in get_alternatives_for_square(board, nrow, ncolumn):
- test_board = copy_board(board, {(nrow, ncolumn): test_digit})
- solved_board = solve(test_board)
- if solved_board:
- # return the solved board all the way up to break recursion
- return solved_board
- # no solution was found for the square, so let's go back
- return
- # all squares are filled so this must be the first solution.
- return board
+ """Return a solved Sudoku board (None if no solution was found)."""
+ pos = first((r, c) for r in range(9) for c in range(9) if not board[r][c])
+ if not pos:
+ # all squares are filled, so this board is the solution
+ return board
+ nrow, ncolumn = pos
+ for test_digit in get_alternatives_for_square(board, nrow, ncolumn):
+ test_board = copy_board(board, {(nrow, ncolumn): test_digit})
+ solved_board = solve(test_board)
+ if solved_board:
+ return solved_board
def lines2board(lines):
- """Parse a text board setting 0's for empty squares and ignoring all spaces."""
- return [[(int(c) if c in "123456789" else 0) for c in re.sub("\s+", "", line)]
+ """Parse a text board setting 0's for empty squares."""
+ spaces = re.compile("\s+")
+ return [[(int(c) if c in "123456789" else 0) for c in spaces.sub("", line)]
for line in lines if line.strip()]
def main(args):
- """Solve a Sudoku board reading the grid from a file."""
+ """Solve a Sudoku board read from a text file."""
from pprint import pprint
path, = args
board = lines2board(open(path))
