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