sudoku_solver.py

import numpy as np
import re, sys
from collections import defaultdict

def build_board(filename):
    board = np.zeros((9, 9))
    f = open(filename, 'r')
    for i in range(9):
        board[i] = [int(k) for k in re.findall(r'\d', f.readline())]
    return board

def eliminate(choices, val, i, j):
    result = {}
    # deep copy
    for item in choices:
        result[item] = list(choices[item])
    del result[(i,j)]
    for m in range(9):
        # propagate in the same row
        if (i,m) in result and val in result[(i,m)]:
            result[(i,m)].remove(val)
        # propagate in the same col
        if (m,j) in result and val in result[(m, j)]:
            result[(m, j)].remove(val)
    # propagate in the same zone
    for m in range(i/3*3, i/3*3+3):
        for n in range(j/3*3, j/3*3+3):
            if (m,n) in result and val in result[(m,n)]:
                result[(m,n)].remove(val)
    return result

def process(board):
    result = defaultdict()
    for i in range(9):
        for j in range(9):
            result[(i, j)] = range(1,10)
    for i in range(9):
        for j in range(9):
            if board[i, j] != 0:
                result = eliminate(result, board[i,j], i, j)
    return result

def solve_opt(board, choices):
    if len(choices) == 0:
        return board

    temp = np.array(board)
    x, y = min(choices, key=(lambda k: len(choices[k])))
    if len(choices[(x, y)]) == 0:
        return None
    for i in choices[(x, y)]:
        temp[x, y] = i
        temp_choices = eliminate(choices, i, x, y)
        result = solve_opt(temp, temp_choices)
        if result is not None:
            return result
        temp[x, y] = 0

def print_board(board):
    print ""
    for i in range(9):
        sys.stdout.write("   ")
        for j in range(9):
           sys.stdout.write("%d "%board[i,j])
           if j == 2 or j == 5:
               sys.stdout.write("| ")
        sys.stdout.write('\n')
        if i == 2 or i == 5:
            print "   ------+-------+------"
    print ""

if __name__ == "__main__":
    b = build_board("sample.txt")
    print_board(solve_opt(b, process(b)))