解数独的回溯算法
Backtracking algorithm for solving Sudoku
首先，感谢您花时间阅读本文。
我正在尝试创建一个回溯算法来解决特定的数独游戏。然而，我遇到了一个问题，我想了很久，却没有把握住。下面是我的回溯算法：
# The puzzle itself
board = [
[0,0,6,8,4,0,0,0,0],
[2,0,1,0,6,0,0,0,7],
[0,3,9,0,0,0,0,1,0],
[0,0,0,0,9,8,3,0,0],
[0,6,0,0,0,0,0,9,0],
[0,0,7,3,2,0,0,0,0],
[0,4,0,0,0,0,1,3,0],
[7,0,0,0,1,0,8,0,4],
[0,0,0,0,3,5,7,0,0]
]
# A function which prints out the board in grids
def print_board():
j = 1
for rows in board:
i = 1
for elements in rows:
if i % 3 == 0:
print(elements, "|", end=" ")
else:
print(elements, end=" ")
i += 1
if j % 3 == 0:
print("")
print("-----------------------", end="")
j += 1
print("")
# A function which searches for the coordinate [x,y] of empty boxes (in this case if the value = 0 it is empty)
def search_empty():
empty_list = []
j = 0
for rows in board:
i = 0
for elements in rows:
if elements == 0:
empty_list.append([i,j])
i += 1
j += 1
return empty_list
# A function which takes the coordinate of an empty box and returns all the coordinates of boxes which fall in the same grid.
def set_grid(x, y):
if x in range(3) and y in range(3):
return [[0,0], [0,1], [0,2], [1,0], [1,1], [1,2], [2,0], [2,1], [2,2]]
elif x in range(3, 6) and y in range(3):
return [[3,0], [3,1], [3,2], [4,0], [4,1], [4,2], [5,0], [5,1], [5,2]]
elif x in range(6, 9) and y in range(3):
return [[6, 0], [6, 1], [6, 2], [7, 0], [7, 1], [7, 2], [8, 0], [8, 1], [8, 2]]
elif x in range(3) and y in range(3, 6):
return [[0,3], [0,4], [0,5], [1,3], [1,4], [1,5], [2,3], [2,4], [2,5]]
elif x in range(3, 6) and y in range(3, 6):
return [[3,3], [3,4], [3,5], [4,3], [4,4], [4,5], [5,3], [5,4], [5,5]]
elif x in range(6, 9) and y in range(3, 6):
return [[6, 3], [6, 4], [6, 5], [7, 3], [7, 4], [7, 5], [8, 3], [8, 4], [8, 5]]
elif x in range(3) and y in range(6, 9):
return [[0, 6], [0, 7], [0, 8], [1, 6], [1, 7], [1, 8], [2, 6], [2, 7], [2, 8]]
elif x in range(3, 6) and y in range(6, 9):
return [[3, 6], [3, 7], [3, 8], [4, 6], [4, 7], [4, 8], [5, 6], [5, 7], [5, 8]]
elif x in range(6, 9) and y in range(6, 9):
return [[6, 6], [6, 7], [6, 8], [7, 6], [7, 7], [7, 8], [8, 6], [8, 7], [8, 8]]
# A function which takes 3 inputs: lower, x and y.
# lower is the starting integer to test on, so first box defaults to 0. If say integer = 6 is the first answer to the first empty
# box, but 1 - 9 does not satisfy the rules of Sudoku for the second box, we backtrack to first box and start from integer + 1
# x and y are both coordinates of the empty box
def conditions(lower, x, y):
grid_list = set_grid(x, y)
for integers in range(lower, 10):
print("Conditions running.")
grid_test = True
vertical_test = True
horizontal_test = True
# Grid test is to test if the current integer is present in the grid. If present, fails the grid test.
for i in grid_list:
[p, q] = i
if integers == board[q][p]:
grid_test = False
break
# Horizontal test is to test if the current integer is present in the same row. If present, fails the row test.
for i in board[y]:
if integers == i:
horizontal_test = False
break
# Vertical test is to test if the current integer is present in the same column. If present, fails the vertical test.
for i in range(9):
if integers == board[i][x]:
vertical_test = False
break
# If all three tests are satisfied and passed, the function returns True and the integer which satisfies all 3 rules.
if grid_test and horizontal_test and vertical_test:
print("Condition satisfied.")
return True, integers
print("Condition unsatisfied.")
return False, 0
# This is where the backtracking begins.
def trials():
n = 0
a = 1
# A list which records all the "correct at that time" integers from previous empty boxes. New "correct" integers are appended.
history = []
# Creates a static list of coordinates of empty boxes.
empty_list = search_empty()
while True:
## This line is to debug
print(history)
# p has value of True or False, and q has value of the correct integer if True, 0 if False
[p, q] = conditions(a, empty_list[n][0], empty_list[n][1])
if not p:
# If p is false, we backtrack by shifting to the last empty box.
n -= 1
# a is the 'lower' input for conditions() function.
a = history[n] + 1
[x, y] = empty_list[n]
# Since the 'correct' answer of previous box is not correct anymore, we are replacing it back with 0 (erasing it).
board[y][x] = 0
## This line is to debug.
print("a:", a, "old a:", history[n])
# Removing the old 'correct' answer from the history list.
history.remove(history[n])
else:
# If p is True, the 'correct' integer gets appended to the list.
history.append(q)
[x, y] = empty_list[n]
# The correct answer is replacing the 0 (writing it on the empty box).
board[y][x] = q
# n increments by 1 to proceed to the next empty box.
n += 1
# When we run through the entire list of empty boxes, we break this loop.
if n == len(empty_list) - 1:
print("Done!")
break
print_board()
trials()
print_board()
然而，当 运行 时，我收到以下信息：
0 0 6 | 8 4 0 | 0 0 0 |
2 0 1 | 0 6 0 | 0 0 7 |
0 3 9 | 0 0 0 | 0 1 0 |
-----------------------
0 0 0 | 0 9 8 | 3 0 0 |
0 6 0 | 0 0 0 | 0 9 0 |
0 0 7 | 3 2 0 | 0 0 0 |
-----------------------
0 4 0 | 0 0 0 | 1 3 0 |
7 0 0 | 0 1 0 | 8 0 4 |
0 0 0 | 0 3 5 | 7 0 0 |
-----------------------
[]
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Condition satisfied.
[5]
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Condition satisfied.
[5, 7]
Conditions running.
Condition satisfied.
[5, 7, 1]
Conditions running.
Conditions running.
Condition satisfied.
[5, 7, 1, 2]
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Condition unsatisifed
a: 3 old a: 2
[5, 7, 1]
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Condition satisfied.
[5, 7, 1, 9]
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Condition unsatisifed
a: 10 old a: 9
[5, 7, 1]
Condition unsatisifed
a: 2 old a: 1
[5, 7]
Conditions running.
Condition satisfied.
[5, 7, 2]
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Condition satisfied.
[5, 7, 2, 9]
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Condition unsatisifed
a: 10 old a: 9
[5, 7, 2]
Condition unsatisifed
a: 3 old a: 2
[5, 7]
Conditions running.
Condition satisfied.
[5, 7, 3]
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Condition satisfied.
[5, 7, 3, 9]
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Condition unsatisifed
a: 10 old a: 9
[5, 7, 3]
Condition unsatisifed
a: 4 old a: 3
[5, 7]
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Condition satisfied.
[5, 7, 9]
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Condition unsatisifed
a: 10 old a: 9
[5, 7]
Condition unsatisifed
a: 8 old a: 7
[5]
Conditions running.
Conditions running.
Condition unsatisifed
a: 6 old a: 5
[]
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Condition unsatisifed
我很难理解 [5, 7] 是如何在不执行任何条件检查的情况下跳转到 [5] 的（从 [5] 和 [ 之间缺少“条件 运行”可以看出） 5, 7]. 这让我相信这是算法失败的主要原因
非常感谢任何帮助。这是我正在从事的第一个实际项目，所以如果有任何初学者错误，我会洗耳恭听:)。
请注意，数独问题的纯回溯通常会导致大量的执行时间。
您的问题是您在找到好的解决方案时从未重置 a。解决方案可能是在 while 循环的 else 末尾添加 a=1。此外，您使用 history.remove(history[n]) 删除等于 history[n] 的 history 的第一项，从而导致一些错误。您应该将其替换为 del。这是更正后的循环：
while True:
## This line is to debug
# p has value of True or False, and q has value of the correct integer if True, 0 if False
[p, q] = conditions(a, empty_list[n][0], empty_list[n][1])
if not p:
# Removing the old 'correct' answer from the history list.
del(history[n])
# If p is false, we backtrack by shifting to the last empty box.
n -= 1
# a is the 'lower' input for conditions() function.
a = history[n] + 1
history[n]+=1
board[y][x] = 0
[x, y] = empty_list[n]
# Since the 'correct' answer of previous box is not correct anymore, we are replacing it back with 0 (erasing it).
## This line is to debug.
else:
# If p is True, the 'correct' integer gets appended to the list.
history[n]=q
history.append(0)
[x, y] = empty_list[n]
# The correct answer is replacing the 0 (writing it on the empty box).
board[y][x] = q
n += 1
# n increments by 1 to proceed to the next empty box.
a=1
# When we run through the entire list of empty boxes, we break this loop.
if n == len(empty_list):
print("Done!")
break
这导致输出：
0 0 6 | 8 4 0 | 0 0 0 |
2 0 1 | 0 6 0 | 0 0 7 |
0 3 9 | 0 0 0 | 0 1 0 |
-----------------------
0 0 0 | 0 9 8 | 3 0 0 |
0 6 0 | 0 0 0 | 0 9 0 |
0 0 7 | 3 2 0 | 0 0 0 |
-----------------------
0 4 0 | 0 0 0 | 1 3 0 |
7 0 0 | 0 1 0 | 8 0 4 |
0 0 0 | 0 3 5 | 7 0 0 |
-----------------------
Done!
5 7 6 | 8 4 1 | 9 2 3 |
2 8 1 | 9 6 3 | 5 4 7 |
4 3 9 | 2 5 7 | 6 1 8 |
-----------------------
1 2 4 | 5 9 8 | 3 7 6 |
3 6 8 | 1 7 4 | 2 9 5 |
9 5 7 | 3 2 6 | 4 8 1 |
-----------------------
6 4 5 | 7 8 9 | 1 3 2 |
7 9 3 | 6 1 2 | 8 5 4 |
8 1 2 | 4 3 5 | 7 6 9 |
-----------------------
哪个是正确答案。
首先，感谢您花时间阅读本文。
我正在尝试创建一个回溯算法来解决特定的数独游戏。然而，我遇到了一个问题，我想了很久，却没有把握住。下面是我的回溯算法：
# The puzzle itself
board = [
[0,0,6,8,4,0,0,0,0],
[2,0,1,0,6,0,0,0,7],
[0,3,9,0,0,0,0,1,0],
[0,0,0,0,9,8,3,0,0],
[0,6,0,0,0,0,0,9,0],
[0,0,7,3,2,0,0,0,0],
[0,4,0,0,0,0,1,3,0],
[7,0,0,0,1,0,8,0,4],
[0,0,0,0,3,5,7,0,0]
]
# A function which prints out the board in grids
def print_board():
j = 1
for rows in board:
i = 1
for elements in rows:
if i % 3 == 0:
print(elements, "|", end=" ")
else:
print(elements, end=" ")
i += 1
if j % 3 == 0:
print("")
print("-----------------------", end="")
j += 1
print("")
# A function which searches for the coordinate [x,y] of empty boxes (in this case if the value = 0 it is empty)
def search_empty():
empty_list = []
j = 0
for rows in board:
i = 0
for elements in rows:
if elements == 0:
empty_list.append([i,j])
i += 1
j += 1
return empty_list
# A function which takes the coordinate of an empty box and returns all the coordinates of boxes which fall in the same grid.
def set_grid(x, y):
if x in range(3) and y in range(3):
return [[0,0], [0,1], [0,2], [1,0], [1,1], [1,2], [2,0], [2,1], [2,2]]
elif x in range(3, 6) and y in range(3):
return [[3,0], [3,1], [3,2], [4,0], [4,1], [4,2], [5,0], [5,1], [5,2]]
elif x in range(6, 9) and y in range(3):
return [[6, 0], [6, 1], [6, 2], [7, 0], [7, 1], [7, 2], [8, 0], [8, 1], [8, 2]]
elif x in range(3) and y in range(3, 6):
return [[0,3], [0,4], [0,5], [1,3], [1,4], [1,5], [2,3], [2,4], [2,5]]
elif x in range(3, 6) and y in range(3, 6):
return [[3,3], [3,4], [3,5], [4,3], [4,4], [4,5], [5,3], [5,4], [5,5]]
elif x in range(6, 9) and y in range(3, 6):
return [[6, 3], [6, 4], [6, 5], [7, 3], [7, 4], [7, 5], [8, 3], [8, 4], [8, 5]]
elif x in range(3) and y in range(6, 9):
return [[0, 6], [0, 7], [0, 8], [1, 6], [1, 7], [1, 8], [2, 6], [2, 7], [2, 8]]
elif x in range(3, 6) and y in range(6, 9):
return [[3, 6], [3, 7], [3, 8], [4, 6], [4, 7], [4, 8], [5, 6], [5, 7], [5, 8]]
elif x in range(6, 9) and y in range(6, 9):
return [[6, 6], [6, 7], [6, 8], [7, 6], [7, 7], [7, 8], [8, 6], [8, 7], [8, 8]]
# A function which takes 3 inputs: lower, x and y.
# lower is the starting integer to test on, so first box defaults to 0. If say integer = 6 is the first answer to the first empty
# box, but 1 - 9 does not satisfy the rules of Sudoku for the second box, we backtrack to first box and start from integer + 1
# x and y are both coordinates of the empty box
def conditions(lower, x, y):
grid_list = set_grid(x, y)
for integers in range(lower, 10):
print("Conditions running.")
grid_test = True
vertical_test = True
horizontal_test = True
# Grid test is to test if the current integer is present in the grid. If present, fails the grid test.
for i in grid_list:
[p, q] = i
if integers == board[q][p]:
grid_test = False
break
# Horizontal test is to test if the current integer is present in the same row. If present, fails the row test.
for i in board[y]:
if integers == i:
horizontal_test = False
break
# Vertical test is to test if the current integer is present in the same column. If present, fails the vertical test.
for i in range(9):
if integers == board[i][x]:
vertical_test = False
break
# If all three tests are satisfied and passed, the function returns True and the integer which satisfies all 3 rules.
if grid_test and horizontal_test and vertical_test:
print("Condition satisfied.")
return True, integers
print("Condition unsatisfied.")
return False, 0
# This is where the backtracking begins.
def trials():
n = 0
a = 1
# A list which records all the "correct at that time" integers from previous empty boxes. New "correct" integers are appended.
history = []
# Creates a static list of coordinates of empty boxes.
empty_list = search_empty()
while True:
## This line is to debug
print(history)
# p has value of True or False, and q has value of the correct integer if True, 0 if False
[p, q] = conditions(a, empty_list[n][0], empty_list[n][1])
if not p:
# If p is false, we backtrack by shifting to the last empty box.
n -= 1
# a is the 'lower' input for conditions() function.
a = history[n] + 1
[x, y] = empty_list[n]
# Since the 'correct' answer of previous box is not correct anymore, we are replacing it back with 0 (erasing it).
board[y][x] = 0
## This line is to debug.
print("a:", a, "old a:", history[n])
# Removing the old 'correct' answer from the history list.
history.remove(history[n])
else:
# If p is True, the 'correct' integer gets appended to the list.
history.append(q)
[x, y] = empty_list[n]
# The correct answer is replacing the 0 (writing it on the empty box).
board[y][x] = q
# n increments by 1 to proceed to the next empty box.
n += 1
# When we run through the entire list of empty boxes, we break this loop.
if n == len(empty_list) - 1:
print("Done!")
break
print_board()
trials()
print_board()
然而，当 运行 时，我收到以下信息：
0 0 6 | 8 4 0 | 0 0 0 |
2 0 1 | 0 6 0 | 0 0 7 |
0 3 9 | 0 0 0 | 0 1 0 |
-----------------------
0 0 0 | 0 9 8 | 3 0 0 |
0 6 0 | 0 0 0 | 0 9 0 |
0 0 7 | 3 2 0 | 0 0 0 |
-----------------------
0 4 0 | 0 0 0 | 1 3 0 |
7 0 0 | 0 1 0 | 8 0 4 |
0 0 0 | 0 3 5 | 7 0 0 |
-----------------------
[]
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Condition satisfied.
[5]
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Condition satisfied.
[5, 7]
Conditions running.
Condition satisfied.
[5, 7, 1]
Conditions running.
Conditions running.
Condition satisfied.
[5, 7, 1, 2]
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Condition unsatisifed
a: 3 old a: 2
[5, 7, 1]
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Condition satisfied.
[5, 7, 1, 9]
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Condition unsatisifed
a: 10 old a: 9
[5, 7, 1]
Condition unsatisifed
a: 2 old a: 1
[5, 7]
Conditions running.
Condition satisfied.
[5, 7, 2]
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Condition satisfied.
[5, 7, 2, 9]
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Condition unsatisifed
a: 10 old a: 9
[5, 7, 2]
Condition unsatisifed
a: 3 old a: 2
[5, 7]
Conditions running.
Condition satisfied.
[5, 7, 3]
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Condition satisfied.
[5, 7, 3, 9]
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Condition unsatisifed
a: 10 old a: 9
[5, 7, 3]
Condition unsatisifed
a: 4 old a: 3
[5, 7]
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Condition satisfied.
[5, 7, 9]
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Condition unsatisifed
a: 10 old a: 9
[5, 7]
Condition unsatisifed
a: 8 old a: 7
[5]
Conditions running.
Conditions running.
Condition unsatisifed
a: 6 old a: 5
[]
Conditions running.
Conditions running.
Conditions running.
Conditions running.
Condition unsatisifed
我很难理解 [5, 7] 是如何在不执行任何条件检查的情况下跳转到 [5] 的（从 [5] 和 [ 之间缺少“条件 运行”可以看出） 5, 7]. 这让我相信这是算法失败的主要原因
非常感谢任何帮助。这是我正在从事的第一个实际项目，所以如果有任何初学者错误，我会洗耳恭听:)。
请注意，数独问题的纯回溯通常会导致大量的执行时间。
您的问题是您在找到好的解决方案时从未重置 a。解决方案可能是在 while 循环的 else 末尾添加 a=1。此外，您使用 history.remove(history[n]) 删除等于 history[n] 的 history 的第一项，从而导致一些错误。您应该将其替换为 del。这是更正后的循环：
while True:
## This line is to debug
# p has value of True or False, and q has value of the correct integer if True, 0 if False
[p, q] = conditions(a, empty_list[n][0], empty_list[n][1])
if not p:
# Removing the old 'correct' answer from the history list.
del(history[n])
# If p is false, we backtrack by shifting to the last empty box.
n -= 1
# a is the 'lower' input for conditions() function.
a = history[n] + 1
history[n]+=1
board[y][x] = 0
[x, y] = empty_list[n]
# Since the 'correct' answer of previous box is not correct anymore, we are replacing it back with 0 (erasing it).
## This line is to debug.
else:
# If p is True, the 'correct' integer gets appended to the list.
history[n]=q
history.append(0)
[x, y] = empty_list[n]
# The correct answer is replacing the 0 (writing it on the empty box).
board[y][x] = q
n += 1
# n increments by 1 to proceed to the next empty box.
a=1
# When we run through the entire list of empty boxes, we break this loop.
if n == len(empty_list):
print("Done!")
break
这导致输出：
0 0 6 | 8 4 0 | 0 0 0 |
2 0 1 | 0 6 0 | 0 0 7 |
0 3 9 | 0 0 0 | 0 1 0 |
-----------------------
0 0 0 | 0 9 8 | 3 0 0 |
0 6 0 | 0 0 0 | 0 9 0 |
0 0 7 | 3 2 0 | 0 0 0 |
-----------------------
0 4 0 | 0 0 0 | 1 3 0 |
7 0 0 | 0 1 0 | 8 0 4 |
0 0 0 | 0 3 5 | 7 0 0 |
-----------------------
Done!
5 7 6 | 8 4 1 | 9 2 3 |
2 8 1 | 9 6 3 | 5 4 7 |
4 3 9 | 2 5 7 | 6 1 8 |
-----------------------
1 2 4 | 5 9 8 | 3 7 6 |
3 6 8 | 1 7 4 | 2 9 5 |
9 5 7 | 3 2 6 | 4 8 1 |
-----------------------
6 4 5 | 7 8 9 | 1 3 2 |
7 9 3 | 6 1 2 | 8 5 4 |
8 1 2 | 4 3 5 | 7 6 9 |
-----------------------
哪个是正确答案。