Sudoku：解数独

sudoku.py

#!/usr/bin/python
import copy

def grid_id(x, y):
    return ((x - 1) / 3 * 3) + (y - 1) / 3 + 1

class Position:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.gid = grid_id(x, y)
        self.moves = set()
        self.solution = 0

def sudoku(in_board, need_all_solutions=False):
    board = copy.deepcopy(in_board)
    horizon  = [[0] * 10 for i in range(10)]
    vertical = [[0] * 10 for i in range(10)]
    grid     = [[0] * 10 for i in range(10)]

    for i in range(9):
        for j in range(9):
            x, y, gid = i + 1, j + 1, grid_id(i + 1, j + 1)
            t = board[i][j]
            if t != 0:
                horizon[x][t]  = 1
                vertical[y][t] = 1
                grid[gid][t]   = 1
    
    todo = []
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                x, y, gid = i + 1, j + 1, grid_id(i + 1, j + 1)
                p = Position(x, y)
                for s in range(1, 10):
                    if horizon[x][s] + vertical[y][s] + grid[gid][s] == 0:
                        p.moves.add(s)
                todo.append(p)

    def solve(n):
        if n >= len(todo):
            for p in todo:
                board[p.x-1][p.y-1] = p.solution
            for line in board:
                print line
            return True
        else:
            remain = todo[n:]
            remain.sort(key=lambda p: len(p.moves))
            todo[n:] = remain

            p = todo[n]
            for s in p.moves:
                x, y, gid = p.x, p.y, p.gid
                p.solution = s

                horizon[x][s]  += 1
                vertical[y][s] += 1
                grid[gid][s]   += 1

                affected = []
                for j in range(n + 1, len(todo)):
                    q = todo[j]
                    if q.x == x or q.y == y or q.gid == gid:
                        if s in q.moves:
                            q.moves.remove(s)
                            affected.append(q)
                
                solved = solve(n + 1)
                if solved == True and not need_all_solutions:
                    return True

                for q in affected:
                    q.moves.add(s)

                horizon[x][s]  -= 1
                vertical[y][s] -= 1
                grid[gid][s]   -= 1
            return False

    solve(0)

board = [
    [0,0,0,0,0,0,0,0,0],
    [0,9,1,0,5,2,0,0,0],
    [7,0,0,0,0,9,0,0,4],
    [6,0,2,0,8,0,0,0,9],
    [0,0,4,1,9,0,0,0,0],
    [5,0,9,0,6,0,0,0,3],
    [9,4,0,0,0,5,0,0,8],
    [0,5,7,0,4,8,0,0,0],
    [0,0,0,0,0,0,0,0,0],
]

sudoku(board, need_all_solutions=False)