In this article we cover another interesting coding exercise: solving a Sudoku. The algorithm we use is backtracking, which is a type of brute force search. The idea is simple but works well: we select an empty cell and we insert a number and check whether this is allowed or not. If not, we stop and try with another number till when all combinations from 1 to 9 are exhausted. If it is allowed, we go look for the next empty cell and proceed. We have found a solution when we there are no more empty cells; if no solution is found the Sudoku has no solution.
The advantage of this method is that it works for all levels and it is quite quick despite having exponential complexity. In the worst case, we would test $9^{81}$ cases, but in reality most combinations would stop the recursion much earlier. In fact, all the tests below are solved almost instantaneously. Note that we only solve for one solution and stop there – there could be other solutions as well but we won’t find them.
Let’s start with the data structure: we only have one, the board. This is a list of nine lists, each of size 9. The function check_sizes() ensures we have a valid board.
def check_sizes(board):
if len(board) != 9:
return False
for i in range(9):
if len(board[i]) != 9:
return False
for i in range(9):
for j in range(9):
if board[i][j] not in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
return False
return True
We need two utility functions: find_empty() returns the first empty cell or None if there are none, while is_valid() returns True if the given number can be inserted in the specified position, of False if that action would result in a non-valid Sudoku.
def find_empty(board):
for i in range(9):
for j in range(9):
if board[i][j] == 0:
return (i, j)
return None
def is_valid(board, num, pos):
"Checks that it is valid to set num in pos"
# valid rows
for i in range(9):
if board[pos[0]][i] == num and pos[1] != i:
return False
# valid columns
for i in range(9):
if board[i][pos[1]] == num and pos[0] != i:
return False
# valid boxes
box_x = pos[1] // 3
box_y = pos[0] // 3
for i in range(box_y * 3, box_y * 3 + 3):
for j in range(box_x * 3, box_x * 3 + 3):
if board[i][j] == num and (i, j) != pos:
return False
return True
The counter decorator will be used to track the complexity of the algorithm; as we’ll see the number of calls do not always depend on the complexity for humans.
def counter(f):
def inner(*args, **kwargs):
inner.num_calls += 1
return f(*args, **kwargs)
inner.num_calls = 0
return inner
We are ready to write the actual solver, which takes board and performs the brute search by inserting all numbers from 1 to 9 in the first empty cell and then calls itself. The return value is either True when there are no empty cell (assuming we start from a valid board) or False if no number can be inserted in the first empty cell without breaking the Sudoku. The function itself is quite short; it is perhaps a bit fragile, so it would be better to wrap it in another function that checks the input board first and then starts the recursion.
@counter
def solve_sudoku(board):
empty = find_empty(board)
if not empty:
return True
row, col = empty
for num in range(1, 10):
if is_valid(board, num, (row, col)):
board[row][col] = num
if solve_sudoku(board):
return board
board[row][col] = 0
return False
Now some tests. Function print_board() is a utility function to pretty-print the boards used for testing, which come from the New York Times website for the easy, medium and hard levels; another website was used for the very hard and extreme levels.
def print_board(board):
"Pretty-prints the board"
for i in range(9):
for j in range(9):
number = board[i][j]
if number == 0:
number = ' '
print(f' {number} ', end='')
if j in [2, 5]:
print(' | ', end='')
print()
if i in [2, 5]:
print('-' * 32)
easy = [
[5, 0, 0, 0, 8, 0, 1, 0, 6],
[0, 0, 0, 0, 7, 3, 2, 8, 4],
[4, 0, 7, 1, 2, 0, 0, 0, 3],
[7, 0, 9, 2, 6, 0, 0, 0, 0],
[0, 0, 3, 0, 4, 5, 0, 1, 0],
[0, 0, 1, 0, 0, 0, 6, 2, 5],
[0, 9, 0, 7, 0, 4, 0, 3, 0],
[0, 7, 0, 0, 0, 2, 8, 9, 0],
[1, 2, 5, 9, 0, 0, 0, 0, 0],
]
assert check_sizes(easy)
solve_sudoku.num_calls = 0
if solve_sudoku(easy):
print_board(easy)
else:
print("No solution exists.")
print(f'\n# of calls: {solve_sudoku.num_calls}')
5 3 2 | 4 8 9 | 1 7 6
9 1 6 | 5 7 3 | 2 8 4
4 8 7 | 1 2 6 | 9 5 3
--------------------------------
7 5 9 | 2 6 1 | 3 4 8
2 6 3 | 8 4 5 | 7 1 9
8 4 1 | 3 9 7 | 6 2 5
--------------------------------
6 9 8 | 7 1 4 | 5 3 2
3 7 4 | 6 5 2 | 8 9 1
1 2 5 | 9 3 8 | 4 6 7
# of calls: 52
medium = [
[0, 0, 0, 6, 7, 0, 0, 2, 0],
[7, 0, 1, 0, 0, 0, 9, 0, 0],
[8, 0, 0, 0, 5, 3, 0, 0, 0],
[0, 1, 0, 0, 2, 0, 0, 6, 0],
[0, 0, 9, 0, 0, 6, 0, 0, 0],
[3, 0, 0, 0, 0, 0, 7, 8, 0],
[0, 0, 5, 0, 0, 0, 3, 0, 7],
[2, 0, 0, 3, 0, 0, 5, 0, 0],
[0, 0, 0, 0, 0, 5, 0, 4, 0],
]
assert check_sizes(medium)
solve_sudoku.num_calls = 0
if solve_sudoku(medium):
print_board(medium)
else:
print("No solution exists.")
print(f'\n# of calls: {solve_sudoku.num_calls}')
9 5 3 | 6 7 1 | 8 2 4
7 6 1 | 2 4 8 | 9 3 5
8 4 2 | 9 5 3 | 6 7 1
--------------------------------
5 1 8 | 7 2 9 | 4 6 3
4 7 9 | 8 3 6 | 1 5 2
3 2 6 | 5 1 4 | 7 8 9
--------------------------------
1 8 5 | 4 6 2 | 3 9 7
2 9 4 | 3 8 7 | 5 1 6
6 3 7 | 1 9 5 | 2 4 8
# of calls: 8797
hard = [
[0, 0, 7, 0, 0, 0, 4, 3, 0],
[3, 0, 0, 8, 0, 0, 0, 5, 6],
[5, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 7, 0, 0, 0, 0, 8, 0, 0],
[0, 0, 0, 6, 0, 2, 0, 0, 0],
[0, 2, 0, 3, 0, 9, 0, 6, 0],
[0, 0, 0, 0, 6, 0, 9, 0, 4],
[2, 0, 0, 4, 0, 1, 0, 0, 0],
[0, 5, 0, 0, 0, 0, 3, 0, 0],
]
assert check_sizes(hard)
solve_sudoku.num_calls = 0
if solve_sudoku(hard):
print_board(hard)
else:
print("No solution exists.")
print(f'\n# of calls: {solve_sudoku.num_calls}')
8 1 7 | 5 2 6 | 4 3 9
3 4 9 | 8 1 7 | 2 5 6
5 6 2 | 9 4 3 | 7 1 8
--------------------------------
6 7 3 | 1 5 4 | 8 9 2
9 8 5 | 6 7 2 | 1 4 3
1 2 4 | 3 8 9 | 5 6 7
--------------------------------
7 3 1 | 2 6 5 | 9 8 4
2 9 8 | 4 3 1 | 6 7 5
4 5 6 | 7 9 8 | 3 2 1
# of calls: 72686
very_hard = [
[1, 0, 0, 0, 3, 9, 0, 0, 8],
[0, 0, 5, 0, 7, 0, 0, 0, 0],
[0, 0, 0, 8, 0, 6, 0, 0, 5],
[9, 0, 6, 0, 0, 3, 0, 0, 0],
[0, 5, 1, 4, 0, 7, 2, 3, 0],
[0, 0, 0, 6, 0, 0, 9, 0, 1],
[7, 0, 0, 9, 0, 5, 0, 0, 0],
[0, 0, 0, 0, 2, 0, 4, 0, 0],
[5, 0, 0, 3, 4, 0, 0, 0, 7],
]
assert check_sizes(very_hard)
solve_sudoku.num_calls = 0
if solve_sudoku(very_hard):
print_board(very_hard)
else:
print("No solution exists.")
print(f'\n# of calls: {solve_sudoku.num_calls}')
1 6 4 | 5 3 9 | 7 2 8
3 8 5 | 2 7 4 | 1 6 9
2 7 9 | 8 1 6 | 3 4 5
--------------------------------
9 2 6 | 1 8 3 | 5 7 4
8 5 1 | 4 9 7 | 2 3 6
4 3 7 | 6 5 2 | 9 8 1
--------------------------------
7 4 3 | 9 6 5 | 8 1 2
6 9 8 | 7 2 1 | 4 5 3
5 1 2 | 3 4 8 | 6 9 7
# of calls: 3307
extreme = [
[0, 0, 5, 4, 0, 0, 0, 0, 9],
[0, 2, 0, 0, 6, 0, 0, 7, 0],
[6, 0, 0, 0, 0, 5, 1, 0, 0],
[1, 0, 0, 0, 0, 3, 7, 0, 0],
[0, 7, 0, 0, 9, 0, 0, 4, 0],
[0, 0, 3, 2, 0, 0, 0, 0, 6],
[0, 0, 1, 8, 0, 0, 0, 0, 7],
[0, 6, 0, 0, 7, 0, 0, 2, 0],
[9, 0, 0, 0, 0, 2, 8, 0, 0],
]
assert check_sizes(extreme)
solve_sudoku.num_calls = 0
if solve_sudoku(extreme):
print_board(extreme)
else:
print("No solution exists.")
print(f'\n# of calls: {solve_sudoku.num_calls}')
7 1 5 | 4 3 8 | 2 6 9
3 2 4 | 9 6 1 | 5 7 8
6 8 9 | 7 2 5 | 1 3 4
--------------------------------
1 9 6 | 5 4 3 | 7 8 2
8 7 2 | 1 9 6 | 3 4 5
4 5 3 | 2 8 7 | 9 1 6
--------------------------------
2 3 1 | 8 5 4 | 6 9 7
5 6 8 | 3 7 9 | 4 2 1
9 4 7 | 6 1 2 | 8 5 3
# of calls: 4428