Sudoku solver

sudoku_hard.txt

0 0 0 0 0 0 0 1 2
0 0 0 0 3 5 0 0 0
0 0 0 6 0 0 0 7 0
7 0 0 0 0 0 3 0 0
0 0 0 4 0 0 8 0 0
1 0 0 0 0 0 0 0 0
0 0 0 1 2 0 0 0 0
0 8 0 0 0 0 0 4 0
0 5 0 0 0 0 6 0 0

Sudokusolver.py

"""
In the book a game state is
struct {
    int x;
    int y;
} move
Essentially this represent value,  
struct {
     int board[DIMENSION+1][DIMENSION+1];
     int freecount;
     move moves[NCELLS];
     } boardtype
so moves will be in sequence
"""
# Got a feeling that this won't make it, stack too deep
"""
    board = [
        [ 0, 0, 9, 0, 0, 0, 0, 0, 1, ],
        [ 0, 6, 0, 0, 0, 0, 9, 7, 0, ],
        [ 0, 0, 0, 0, 0, 0, 0, 6, 4, ],
        [ 7, 8, 0, 5, 2, 0, 0, 0, 0, ],
        [ 0, 0, 4, 7, 6, 1, 8, 0, 0, ],
        [ 0, 0, 0, 0, 3, 8, 0, 9, 5, ],
        [ 6, 1, 0, 0, 0, 0, 0, 0, 0, ],
        [ 0, 7, 5, 0, 0, 0, 0, 3, 0, ],
        [ 9, 0, 0, 0, 0, 0, 4, 0, 0, ],
    ]   
"""
class BoardState(object):
    # I love dynamic language ;-)
    board = [
        [ 0, 0, 0, 0, 0, 0, 0, 1, 2, ],
        [ 0, 0, 0, 0, 3, 5, 0, 0, 0, ],
        [ 0, 0, 0, 6, 0, 0, 0, 7, 0, ],
        [ 7, 0, 0, 0, 0, 0, 3, 0, 0, ],
        [ 0, 0, 0, 4, 0, 0, 8, 0, 0, ],
        [ 1, 0, 0, 0, 0, 0, 0, 0, 0, ],
        [ 0, 0, 0, 1, 2, 0, 0, 0, 0, ],
        [ 0, 8, 0, 0, 0, 0, 0, 4, 0, ],
        [ 0, 5, 0, 0, 0, 0, 6, 0, 0, ],
    ]   
    # a list of move = { "x":0, "y":0, "value":0 }
    moves = []
    n_moves = 0

solved = False
quadrant = [[0, 1, 2], [3, 4, 5], [6, 7, 8]]
total_moves = 0

def load_board_state(filename):
    """
    File format:
    0 0 9 0 0 0 0 0 1
    0 6 0 0 0 0 9 7 0
    0 0 0 0 0 0 0 6 4
    7 8 0 5 2 0 0 0 0
    0 0 4 7 6 1 8 0 0
    0 0 0 0 3 8 0 9 5
    6 1 0 0 0 0 0 0 0
    0 7 5 0 0 0 0 3 0
    9 0 0 0 0 0 4 0 0
    """
    f = open(filename)
    board = []
    for l in f:
        line = l.split("\n")[0]
        board.append([ int(i) for i in line.split(" ")])
    board_state = BoardState()
    board_state.board = board
    return board_state

def main():
    global total_moves, solved
    for filename in [ "websudoku_hard.txt", "sudoku_hard.txt", "websudoku_hard_2.txt", "websudoku_easy.txt" ]:
        board_state = load_board_state(filename)
        print_result(board_state)
        solve_problem(board_state)
        total_moves = 0
        solved = False

# This is an exercise in backtracking
def solve_problem(current_state):
    global solved
    global total_moves
    if solved:
        # Someone found a solution, quitting
        return 
    if is_solution(current_state.board):
        print_result(current_state)
        solved = True
        return 
    else:
        candidates = generate_candidate(current_state.board)
        # What if there is no candidate? 
        
        for candidate in candidates:
            total_moves += 1
            make_move(current_state, candidate)
            solve_problem(current_state)
            unmake_move(current_state, candidate)
            

def print_result(board_state):
    print "-------------------"
    printed = []
    for row in board_state.board:
        temp = [row[i:i+3] for i in range(0,9,3)]
        temp = [ " ".join(map(str, i)) for i in temp]
        printed.append("|"+"|".join(temp)+"|")
    
    printed = ["\n".join(printed[i:i+3]) for i in range(0,9,3)]
    print "\n|-----------------|\n".join(printed)
    print "-------------------"
    
    print board_state.n_moves
    print total_moves

def unmake_move(board_state, candidate):
    board_state.board[candidate["x"]][candidate["y"]] = 0
    board_state.moves.pop()

def make_move(board_state, move):    
    board_state.board[move["x"]][move["y"]] = move["value"]
    board_state.moves.append(move)
    # We need to know how much in total, not how many step needed to fill in the square
    board_state.n_moves += 1
        
def generate_candidate(board):
    squares = empty_square(board)
    # pick a square is better? or pick the most constraint, why it matter?
    # square = squares[0]
    # square = choose_square(squares)
    square = choose_constraint_square(squares, board)
    values = possible_value(square["x"], square["y"], board)
    # What if there is no values. Reason the move before fill in the wrong value?
    candidates = []
    for value in values:
        candidates.append({"x":square["x"], "y":square["y"], "value":value})
    return candidates

def choose_square(squares):
    # Least square heuristics. is there other heuristics?
    result = {}
    min = 10
    min_key = []
    for square in squares:
        if square["x"] not in result:
            result[square["x"]] = []
        result[square["x"]].append(square)
        
    for x in result:
        if min > len(result[x]):
            min = len(result[x])
            min_key = result[x]
    return min_key[0]    
    
def choose_constraint_square(squares, board):
    # squares is empty square
    results = {}
    for square in squares:
        candidates = possible_value(square["x"], square["y"], board)
        results[square["x"], square["y"]] = candidates
    min_candidates = 10
    min_key        = (10,10)
    for square in results:  
        if min_candidates > len(results[square]):
            min_candidates = len(results[square])
            min_key        = square
    # just to preserve the API
    result = { "x":min_key[0], "y": min_key[1] }
    return result
    
def possible_value(x, y, board):
    # Homework how set work?
    # because sudoku value is 1-9, 0 is there for convenience sake
    values = set(range(10))
    row_set = set(board[x])
    # now to flip the list
    col_set = set()
    # because list is 0 indexed
    for point in range(9):
        col_set.add(board[point][y])
    empty_col = values.intersection(col_set)
    existing_value = col_set.union(row_set)
    
    existing_value = existing_value.union(get_quadrant(x, y, board))
    return list(values.difference(existing_value))

def get_quadrant(x, y, board):
    x_quadrant = select_quadrant(x)
    y_quadrant = select_quadrant(y)

    result = set()
    for x_value in quadrant[x_quadrant]:
        for y_value in quadrant[y_quadrant]:
            result.add(board[x_value][y_value])
    
    return result

def select_quadrant(point):
    selected = 0
    for q in quadrant:
        if point in q:
            break
        selected += 1
    return selected

def empty_square(board):
    row_count = 0
    result    = []
    for row in board:
        col_count = 0
        for col in row:
            if col == 0:
                result.append({"x": row_count, "y": col_count})
            col_count += 1
        row_count += 1
    return result
    
def is_solution(board):
    # Why this work?
    for row in board:
        if 0 in row:
            return False
    return True

if __name__ == "__main__":
    main()

websudoku_easy.txt

0 0 6 0 8 3 0 1 4
9 8 0 0 7 0 0 5 3
0 0 2 0 0 0 0 0 0
8 2 0 9 0 0 0 0 0
1 7 9 8 0 5 4 6 2
0 0 0 0 0 1 0 7 9
0 0 0 0 0 0 5 0 0
5 4 0 0 9 0 0 2 1
6 9 0 5 1 0 7 0 0

websudoku_hard.txt

0 0 9 0 0 0 0 0 1
0 6 0 0 0 0 9 7 0
0 0 0 0 0 0 0 6 4
7 8 0 5 2 0 0 0 0
0 0 4 7 6 1 8 0 0
0 0 0 0 3 8 0 9 5
6 1 0 0 0 0 0 0 0
0 7 5 0 0 0 0 3 0
9 0 0 0 0 0 4 0 0

websudoku_hard_2.txt

0 0 0 5 7 0 0 9 1
0 0 7 0 9 0 5 0 0
4 0 0 1 0 0 0 2 0
7 0 0 0 0 3 0 0 0
0 3 2 0 0 0 1 4 0
0 0 0 8 0 0 0 0 9
0 6 0 0 0 5 0 0 8
0 0 3 0 6 0 9 0 0
2 7 0 0 1 9 0 0 0