Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Sudoku solver using recursive backtracking
import sys
# initial sudoku matrix
V = [
0, 0, 0, 2, 6, 0, 7, 0, 1,
6, 8, 0, 0, 7, 0, 0, 9, 0,
1, 9, 0, 0, 0, 4, 5, 0, 0,
8, 2, 0, 1, 0, 0, 0, 4, 0,
0, 0, 4, 6, 0, 2, 9, 0, 0,
0, 5, 0, 0, 0, 3, 0, 2, 8,
0, 0, 9, 3, 0, 0, 0, 7, 4,
0, 4, 0, 0, 5, 0, 0, 3, 6,
7, 0, 3, 0, 1, 8, 0, 0, 0
]
# fill matrix using recursive backtracking
# `fw` stands for forward and `bw` for backward
def fill_matrix(V, ignore_pos, i = 0, direction = 'fw'):
if i > 80:
return True
if i in ignore_pos:
if direction == 'fw':
fill_matrix(V, ignore_pos, i + 1)
else :
fill_matrix(V, ignore_pos, i - 1, 'bw')
elif V[i] < 9:
if has_violation(V, V[i] + 1, i):
V[i] += 1
fill_matrix(V, ignore_pos, i)
else :
V[i] += 1
fill_matrix(V, ignore_pos, i + 1)
else :
V[i] = 0
fill_matrix(V, ignore_pos, i - 1, 'bw')
# get positions for previously propulated values
def set_ignore_pos_array(V):
ignore_pos = []
for index, value in enumerate(V):
if value != 0:
ignore_pos.append(index)
return ignore_pos
# given an index, get all of its crossing positions
def get_positions_to_check(V, i):
positions_to_check = [i]
before_up = i - 9
after_down = i + 9
before_left = i
after_right = i + 1
if i >= 0 and i <= 80:
while before_up >= 0:
positions_to_check.append(before_up)
before_up -= 9
while after_down <= 80:
positions_to_check.append(after_down)
after_down += 9
while before_left % 9 != 0:
before_left -= 1
positions_to_check.append(before_left)
while after_right % 9 != 0:
positions_to_check.append(after_right)
after_right += 1
return positions_to_check
# check for violations when inserting a value in a given position
def has_violation(V, value, index):
pos_to_check = get_positions_to_check(V, index)
if pos_to_check:
for i in pos_to_check:
if V[i] == value:
return True
return False
else :
return "No index available."
def main():
#Increase recursion limit due to no TRE in Python
sys.setrecursionlimit(10000)
ignore_pos = set_ignore_pos_array(V)
fill_matrix(V, ignore_pos)
# solved sudoku matrix
print(V)
if __name__ == "__main__": main()
# solved sudoku matrix
'''
4, 3, 5, 2, 6, 9, 7, 8, 1,
6, 8, 2, 5, 7, 1, 4, 9, 3,
1, 9, 7, 8, 3, 4, 5, 6, 2,
8, 2, 6, 1, 9, 5, 3, 4, 7,
3, 7, 4, 6, 8, 2, 9, 1, 5,
9, 5, 1, 7, 4, 3, 6, 2, 8,
5, 1, 9, 3, 2, 6, 8, 7, 4,
2, 4, 8, 9, 5, 7, 1, 3, 6,
7, 6, 3, 4, 1, 8, 2, 5, 9
'''
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment