Solving Expert-Level Sudoku Puzzles Quickly Using Python's Backtracking Algorithm
Sudoku is a good example for explaining backtracking because the rules are simple, but the search process is classic. When humans solve it manually, they often eliminate impossible numbers, fill obvious cells first, and then start testing possibilities. Backtracking turns that exact idea into a systematic algorithm.
This article uses Python to solve a 9x9 Sudoku puzzle with backtracking. The core loop is straightforward: find an empty cell, generate valid candidates, try them one by one, and roll back when a choice leads to a dead end.
Steps:
- Represent the Sudoku board as an array.
- Find the empty cells to fill.
- Print the current Sudoku board.
- Determine possible valid numbers for the current cell.
- Validate the current number based on the Sudoku rules.
- If valid, move to the next empty cell; if not, backtrack to the previous cell. If all cells are filled, a solution has been found.
Representing the Sudoku Board as an Array
A Sudoku board is a grid, so it can be represented as a two-dimensional array. For convenience, here’s an example:
board = [
[0,0,1,0,0,3,0,0,0],
[0,0,0,8,5,0,0,0,0],
[0,4,0,0,2,6,8,0,0],
[0,7,9,0,0,5,0,0,2],
[0,0,2,0,0,0,0,0,0],
[5,0,0,0,0,0,0,0,4],
[0,0,0,0,0,0,0,2,7],
[6,0,0,0,4,0,0,0,0],
[0,0,0,1,9,0,6,8,0]
]
A 0 indicates an empty cell that needs to be filled, while other numbers represent existing values.
Finding Empty Cells to Fill
The first step is to manually input the Sudoku puzzle. To find empty cells, we simply look for 0s in the array. We’ll fill them one by one, from left to right, top to bottom. Each time, we find a single empty cell. Here’s the code:
def find_empty(bo):
for i in range(len(bo)):
for j in range(len(bo[0])):
if bo[i][j] == 0:
return (i, j) # row, col
return None
Printing the Current Sudoku Board
We use | and - characters to visually separate the 3x3 blocks. These are inserted when the row or column index is a multiple of 3.
def print_board(bo):
for i in range(len(bo)):
if i % 3 == 0 and i != 0:
print("- - - - - - - - - - - - - ")
for j in range(len(bo[0])):
if j % 3 == 0 and j != 0:
print(" | ", end="")
if j == 8:
print(bo[i][j])
else:
print(str(bo[i][j]) + " ", end="")
Determining Possible Valid Numbers
All possible numbers are from 1 to 9. If a number already exists in the current cell’s row, column, or 3x3 block, it’s removed from the list of available numbers, leaving only the valid candidates.
def find_possible_valid(bo,pos):
num_list = list(range(1,10))
for i in range(9):
if bo[pos[0]][i]!=0 and bo[pos[0]][i] in num_list: # row
num_list.remove(bo[pos[0]][i])
if bo[i][pos[1]]!=0 and bo[i][pos[1]] in num_list: # column
num_list.remove(bo[i][pos[1]])
x,y = pos[0]//3,pos[1]//3
for i in range(3*x,3*x+3): # 3x3 box
for j in range(3*y,3*y+3):
if bo[i][j]!=0 and bo[i][j] in num_list:
num_list.remove(bo[i][j])
return num_list
Validating Numbers 1-9 Against the Current Sudoku Board
Sudoku rules dictate that no duplicate numbers are allowed in any row or column. If a duplicate is found, False is returned, indicating the current number is invalid.
def valid(bo, num, pos):
# Check row
for i in range(len(bo[0])):
if bo[pos[0]][i] == num and pos[1] != i:
return False
# Check column
for i in range(len(bo)):
if bo[i][pos[1]] == num and pos[0] != i:
return False
# Check box
x = pos[1] // 3
y = pos[0] // 3
for i in range(y*3, y*3 + 3):
for j in range(x * 3, x*3 + 3):
if bo[i][j] == num and (i,j) != pos:
return False
return True
Moving to the Next Empty Cell or Backtracking
This is the main loop. For each empty cell found, it iterates through the possible candidate numbers. If a number is valid, it attempts to fill the next empty cell recursively. If the recursive call returns True (meaning a solution was found), then the current number is correct, and True is propagated back up. If a number leads to a dead end (the recursive call returns False), the current cell is reset to 0, and the loop continues with the next candidate number for the current cell. This process continues until all empty cells are filled, indicating a solution has been found.
def solve_suduko(bo):
find = find_empty(bo)
if not find:
return True
else:
row, col = find
for i in find_possible_valid(bo,[row,col]):
if valid(bo, i, (row, col)):
bo[row][col] = i
if solve_suduko(bo):
return True
bo[row][col] = 0
return False
How to Verify the Solver Really Worked
After you write the solver, the simplest validation has two parts:
- Print the board before and after solving, and confirm that every
0has been replaced by a number from1to9. - Manually inspect any row, column, and 3x3 box to confirm there are no duplicates.
If you want a stricter check, you can also add a final validation function that verifies every row, every column, and every 3x3 sub-grid automatically.
Putting all the code together, we get the complete Sudoku solver.
import time
def print_board(bo):
for i in range(len(bo)):
if i % 3 == 0 and i != 0:
print("- - - - - - - - - - - - - ")
for j in range(len(bo[0])):
if j % 3 == 0 and j != 0:
print(" | ", end="")
if j == 8:
print(bo[i][j])
else:
print(str(bo[i][j]) + " ", end="")
def find_possible_valid(bo,pos):
num_list = list(range(1,10))
for i in range(9):
if bo[pos[0]][i]!=0 and bo[pos[0]][i] in num_list:
num_list.remove(bo[pos[0]][i])
if bo[i][pos[1]]!=0 and bo[i][pos[1]] in num_list:
num_list.remove(bo[i][pos[1]])
x,y = pos[0]//3,pos[1]//3
for i in range(3*x,3*x+3):
for j in range(3*y,3*y+3):
if bo[i][j]!=0 and bo[i][j] in num_list:
num_list.remove(bo[i][j])
return num_list
def find_empty(bo):
for i in range(len(bo)):
for j in range(len(bo[0])):
if bo[i][j] == 0:
return (i, j) # row, col
return None
def solve_suduko(bo):
find = find_empty(bo)
if not find:
return True
else:
row, col = find
for i in find_possible_valid(bo,[row,col]):
if valid(bo, i, (row, col)):
bo[row][col] = i
if solve_suduko(bo):
return True
bo[row][col] = 0
return False
def valid(bo, num, pos):
# Check row
for i in range(len(bo[0])):
if bo[pos[0]][i] == num and pos[1] != i:
return False
# Check column
for i in range(len(bo)):
if bo[i][pos[1]] == num and pos[0] != i:
return False
# Check box
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 bo[i][j] == num and (i,j) != pos:
return False
return True
if __name__ == "__main__":
board = [
[0,0,1,0,0,3,0,0,0],
[0,0,0,8,5,0,0,0,0],
[0,4,0,0,2,6,8,0,0],
[0,7,9,0,0,5,0,0,2],
[0,0,2,0,0,0,0,0,0],
[5,0,0,0,0,0,0,0,4],
[0,0,0,0,0,0,0,2,7],
[6,0,0,0,4,0,0,0,0],
[0,0,0,1,9,0,6,8,0]
]
print_board(board)
start_time = time.time()
solve_suduko(board)
end_time = time.time()
print("_____________________________n")
print_board(board)
print("time used:{}s".format(end_time-start_time))
Running the code solves an expert-level Sudoku puzzle in less than a second.
Summary:
This article demonstrates how to solve an expert-level Sudoku puzzle in under a second using Python’s backtracking algorithm. By finding possible candidate numbers, we significantly reduce the search space and execution time. While the current implementation requires manually inputting the Sudoku board as an array, a future enhancement could involve using image recognition to automatically capture the board, making it even more convenient to get instant solutions. Remember, the primary goal of Sudoku is to exercise your brain, not to simply find quick answers!
- 原文作者：春江暮客
- 原文链接：https://www.bobobk.com/en/756.html
- 版权声明：本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可，非商业转载请注明出处（作者，原文链接），商业转载请联系作者获得授权。