Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A brute force approach to solving a sudoku board, in Python.
__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')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.