A brute force approach to solving a sudoku board, in Python.

pythonSudokuSolver.py

__author__ = 'kengarber'


import datetime

# SETUP ------------------------------------------------------------------
given_board = [[0, 0, 0, 0, 4, 0, 0, 0, 0],
               [1, 0, 7, 0, 0, 0, 0, 8, 0],
               [5, 0, 0, 6, 0, 7, 0, 3, 0],
               [2, 0, 0, 3, 0, 4, 8, 9, 0],
               [0, 0, 0, 0, 0, 0, 0, 0, 0],
               [0, 6, 9, 2, 0, 1, 0, 0, 5],
               [0, 7, 0, 9, 0, 6, 0, 0, 8],
               [0, 4, 0, 0, 0, 0, 1, 0, 3],
               [0, 0, 0, 0, 1, 0, 0, 0, 0]]
current_board = []
for i in given_board:
    current_board.append(i[:])
current_location = (0, 0)
moving_forward = True
out_of_bounds = False

# FUNCTIONS ------------------------------------------------------------------


def print_board():
    print()
    for n in range(9):
        for j in range(9):
            num_to_print = current_board[n][j]
            if num_to_print == 0:
                num_to_print = ' '
            if j == 2 or j == 5:
                print(num_to_print, end='|')
            else:
                print(num_to_print, end=' ')
        if n == 2 or n == 5:
            print()
            print('------------------')
        else:
            print()
    print()


def advance_location():
    global current_location
    global out_of_bounds
    current_row = current_location[0]
    current_col = current_location[1] + 1
    current_location = (current_row, current_col)
    if current_col == 9:
        current_location = (current_row + 1, 0)
    if current_row == 8 and current_col == 9:
        out_of_bounds = True


def devance_location():
    global current_location
    global out_of_bounds
    current_row = current_location[0]
    current_col = current_location[1] - 1
    current_location = (current_row, current_col)
    if current_col == -1:
        current_location = (current_row - 1, 8)
    if current_row == 0 and current_col == -1:
        out_of_bounds = True


def is_given():
    if given_board[current_location[0]][current_location[1]] != 0:
        return True
    else:
        return False


def get_current_val(location=current_location):
    return current_board[location[0]][location[1]]


def is_collision():
    current_value = get_current_val(current_location)
    # test horizontal
    for j in range(9):
        if j != current_location[1]:
            if get_current_val((current_location[0], j)) == current_value:
                return True
    # vertical
    for j in range(9):
        if j != current_location[0]:
            if get_current_val((j, current_location[1])) == current_value:
                return True
    # box
    horizontal_third = int(current_location[1] / 3)
    vertical_third = int(current_location[0] / 3)
    for j in range(horizontal_third * 3, (horizontal_third + 1) * 3):
        for n in range(vertical_third * 3, (vertical_third + 1) * 3):
            if j != current_location[1] and n != current_location[0]:
                if get_current_val((n, j)) == current_value:
                    return True

    return False


def re_setup(board):
    global given_board, current_board, current_location, moving_forward, out_of_bounds
    given_board = board
    current_board = []
    for z in given_board:
        current_board.append(z[:])
    current_location = (0, 0)
    moving_forward = True
    out_of_bounds = False

# SOLVING PUZZLE(S) ------------------------------------------------------------------


puzzle = '800000000003600000070090200050007000000045700000100030001000068008500010090000400'
temp_puzzle = []
for i in puzzle:
    temp_puzzle.append(int(i))
temp_puzzle.reverse()
for i in range(9):
    for n in range(9):
        given_board[i][n] = temp_puzzle.pop()
current_board = []
for i in given_board:
    current_board.append(i[:])

print('puzzle: ')
print_board()

start_time = datetime.datetime.now()

while not out_of_bounds:
    if is_given():
        if moving_forward:
            advance_location()
        else:
            devance_location()
    else:
        current_board[current_location[0]][current_location[1]] += 1
        square_value = get_current_val(current_location)
        if square_value == 10:
            current_board[current_location[0]][current_location[1]] = 0
            moving_forward = False
            devance_location()
        elif not is_collision():
            moving_forward = True
            advance_location()

end_time = datetime.datetime.now()
delta_time = end_time - start_time

print('solved: ')
print_board()
print('in: ' + str(delta_time.seconds) + ' seconds, ' + str(delta_time.microseconds) + ' microseconds')