Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
sudoku solver using backtracking algorithm
def print_grid(grid):
for i in range(9):
for j in range(9):
print(grid[i][j], end="")
print('\n')
def find_empty_location(grid):
for row in range(9):
for column in range(9):
if grid[row][column] == 0:
return [row, column]
return False
def check_is_safe(row, num):
for field in row:
if num == field:
return False
return True
def check_box_is_safe(box, num):
for i in range(3):
for j in range(3):
if box[i][j] == num:
return False
return True
def location_is_safe(num, location, grid):
row_index, column_index = location
row = [item for item in grid[row_index]]
if not check_is_safe(row, num):
return False
column = [grid[index][column_index] for index in range(9)]
if not check_is_safe(column, num):
return False
box_row_index = row_index - row_index % 3
box_column_index = column_index - column_index % 3
box = [row[box_column_index:box_column_index + 3] for row in grid[box_row_index:box_row_index + 3]]
if not check_box_is_safe(box, num):
return False
return True
def solve(grid):
location = find_empty_location(grid)
# all fields are filled - done
if not location:
return True
for num in range(1, 10):
if location_is_safe(num, location, grid):
row_index, column_index = location
grid[row_index][column_index] = num
if solve(grid):
return True
grid[row_index][column_index] = 0
# backtracking
return False
grid = [
[0,5,8,0,0,0,0,0,3],
[1,7,0,0,5,0,0,0,8],
[0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,0,0],
[4,0,7,0,8,0,0,0,6],
[0,8,3,0,6,0,0,1,7],
[9,1,0,0,0,3,0,7,0],
[0,0,6,0,0,0,0,8,0],
[0,0,0,0,0,0,0,3,4],
]
if solve(grid):
print_grid(grid)
else:
print("No solution found")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment