Welcome, guest | Sign In | My Account | Store | Cart
import re
import sys

def copy_board(board, sets):
   
"""Return a copy of board setting new squares from 'sets' 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)]
    nums
= nums_in_box + nums_in_row + nums_in_column
   
return sorted(set(range(1, 9+1)) - set(nums))

def get_more_constrained_square(board):
   
"""Get the square in board with more constrains (less alternatives)."""
    ranges
= ((x, y) for x in range(9) for y in range(9))
    constrains
= [(len(get_alternatives_for_square(board, r, c)), (r, c))
       
for (r, c) in ranges if not board[r][c]]
   
if constrains:
       
return min(constrains)[1]
     
def solve(board):
   
"""Return a solved Sudoku board (None if no solution was found)."""
    pos
= get_more_constrained_square(board)
   
if not pos:
       
return board # all squares are filled, so this board is the solution
    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 stripping spaces and 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 9 2010-04-22 18:04:35
+++ revision 10 2010-04-23 12:35:13
@@ -22,9 +22,8 @@
     ranges
= ((x, y) for x in range(9) for y in range(9))
     constrains
= [(len(get_alternatives_for_square(board, r, c)), (r, c))
         
for (r, c) in ranges if not board[r][c]]
-    if not constrains:
-        return
-    return min(constrains)[1]
+    if constrains:
+        return min(constrains)[1]
     
 
def solve(board):
     
"""Return a solved Sudoku board (None if no solution was found)."""

History