数独求解器回溯算法不起作用
Sudoko Solver Backtracking Algorithm Not Working
我对编程还很陌生，最近开始研究 sudoko 求解器，除了求解算法本身，一切都很好，我使用了一些来自互联网的帮助，但因为我自己编写了方法，我找不到我的代码的准确解决方案，任何帮助将不胜感激！
问题：代码一直运行到它无法将值输入空 (0) 索引之一，而不是回溯，它只是停止。
如果你能让我知道我做错了什么，或者提出改进代码的可能方法，任何事情都会有很大的帮助！
我的代码在这里：
import time
start_time = time.time()
grid = [
[7, 8, 0, 4, 0, 0, 1, 2, 0],
[6, 0, 0, 0, 7, 5, 0, 0, 9],
[0, 0, 0, 6, 0, 1, 0, 7, 8],
[0, 0, 7, 0, 4, 0, 2, 6, 0],
[0, 0, 1, 0, 5, 0, 9, 3, 0],
[9, 0, 4, 0, 6, 0, 0, 0, 5],
[0, 7, 0, 3, 0, 0, 0, 1, 2],
[1, 2, 0, 0, 0, 7, 4, 0, 0],
[0, 4, 9, 2, 0, 6, 0, 0, 7]
]
def printBoard():
print("Suduko Board")
for row in grid:
for elem in row:
print(elem, end=' ')
print()
def checkInRow(grid,row, num):
for i in range(0,9):
if(grid[row][i] == num):
return True
return False
def checkInCol(grid,col, num):
for i in range(0,9):
if(grid[i][col] == num):
return True
return False
def checkInBox(grid, row, col, num):
#This will give the starting point for the box
boxX = (row // 3) * 3
boxY = (col // 3) * 3
for i in range(3):
for j in range(3):
if((grid[boxY + j][boxX + i]) == num):
return True
return False
def findNextEmpty(grid, num):
for row in range(9):
for col in range(9):
if(grid[row][col] == num):
return row, col
return None
def checkSafe(grid, row, col, num): #Returns true if safe returns false if unsafe
return not checkInRow(grid,row,num) and not checkInCol(grid,col,num) and not checkInBox(grid,row,col,num)
#PROBLEM IS HERE \/
def solveSudoko(grid, i,j):
if not findNextEmpty(grid,0):
return True
else:
i = findNextEmpty(grid,0)[0] # Finds Row #
j = findNextEmpty(grid,0)[1] # Finds Col #
print(i, j)
for value in range(1,10):
if checkSafe(grid,i,j,value) == True:
grid[i][j] = value
printBoard()
print("--- %s seconds ---" % (time.time() - start_time))
if(solveSudoko(grid,i,j)):
return True
grid[i][j] = 0
return False
#print(str(value) + " can go in grid[" + str(i) + "]" + "[" + str(j) + "]")
printBoard()
solveSudoko(grid,0,0)
问题说明
我认为问题在于您的网格是一个列表，即可变的。这意味着如果您调用 solveSudoko(grid,i,j) 它不会复制网格，但内存中只有一个网格。所以在 solveSudoko 运行 出现问题后它不能回滚，因为你已经改变了原来的网格。可能的解决方案是使用非可变数据类型，如元组或有点难看，但也可能是制作网格的副本。
示例：
grid = [1,2,3]
def test(grid):
grid[0] = 0
test(grid)
print(grid)
---> [0,2,3]
快速但丑陋的解决方案
您可能可以在代码开头添加 import copy 并替换
if(solveSudoko(grid,i,j)):
来自
if(solveSudoko(copy.deepcopy(grid),i,j)):
示例：
grid = [1,2,3]
def test(grid):
grid[0] = 0
test(copy.deepcopy(grid))
print(grid)
---> [1,2,3]
请注意，使用 copy.copy 而不是 copy.deepcopy 也适用于该示例，因为整数是不可变的，但在您的代码中使用列表列表，您需要 copy.deepcopy.
好的解决方案
示例：
grid = (1,2,3)
def test(grid):
grid = (0,2,3)
test(grid)
print(grid)
---> (1,2,3)
元组的问题是获取新网格并不好玩。我可能会使用一些 class 来为我管理网格：
class Grid:
def __init__(self, grid):
assert type(grid) == tuple
self.grid = grid
@staticmethod
def gird_from_list(list_):
return Grid(tuple(list_[i][j] for i in range(len(list_)) for j in range(len(list_[0]))))
def __repr__(self):
return "\n".join(str(self.grid[i*9:(i+1)*9]) for i in range(9))
def set(self, i, j, value):
return Grid(tuple(value if i+j*9==k else x for k,x in enumerate(self.grid)))
tuple_grid = Grid.gird_from_list(gird)
tuple_grid2 = tuple_grid.set(8,8,0)
此处 grid_from_list 只是将您的列表转换为我的格式，而 __repr__ 为您提供了一个很好的二维网格表示，即使我实际上只保留了一个一维元组。如果您不知道 __repr__ 在您打印 class.
的实例时总是被调用
现在打印 tuple_grid 会产生
(7, 8, 0, 4, 0, 0, 1, 2, 0)
(6, 0, 0, 0, 7, 5, 0, 0, 9)
(0, 0, 0, 6, 0, 1, 0, 7, 8)
(0, 0, 7, 0, 4, 0, 2, 6, 0)
(0, 0, 1, 0, 5, 0, 9, 3, 0)
(9, 0, 4, 0, 6, 0, 0, 0, 5)
(0, 7, 0, 3, 0, 0, 0, 1, 2)
(1, 2, 0, 0, 0, 7, 4, 0, 0)
(0, 4, 9, 2, 0, 6, 0, 0, 7)
打印 tuple_grid2 会产生
(7, 8, 0, 4, 0, 0, 1, 2, 0)
(6, 0, 0, 0, 7, 5, 0, 0, 9)
(0, 0, 0, 6, 0, 1, 0, 7, 8)
(0, 0, 7, 0, 4, 0, 2, 6, 0)
(0, 0, 1, 0, 5, 0, 9, 3, 0)
(9, 0, 4, 0, 6, 0, 0, 0, 5)
(0, 7, 0, 3, 0, 0, 0, 1, 2)
(1, 2, 0, 0, 0, 7, 4, 0, 0)
(0, 4, 9, 2, 0, 6, 0, 0, 0)
因此，当您调用 set 时 gird 不会更改，但会为您提供一个具有新值的全新 gird。
我对编程还很陌生，最近开始研究 sudoko 求解器，除了求解算法本身，一切都很好，我使用了一些来自互联网的帮助，但因为我自己编写了方法，我找不到我的代码的准确解决方案，任何帮助将不胜感激！
问题：代码一直运行到它无法将值输入空 (0) 索引之一，而不是回溯，它只是停止。
如果你能让我知道我做错了什么，或者提出改进代码的可能方法，任何事情都会有很大的帮助！
我的代码在这里：
import time
start_time = time.time()
grid = [
[7, 8, 0, 4, 0, 0, 1, 2, 0],
[6, 0, 0, 0, 7, 5, 0, 0, 9],
[0, 0, 0, 6, 0, 1, 0, 7, 8],
[0, 0, 7, 0, 4, 0, 2, 6, 0],
[0, 0, 1, 0, 5, 0, 9, 3, 0],
[9, 0, 4, 0, 6, 0, 0, 0, 5],
[0, 7, 0, 3, 0, 0, 0, 1, 2],
[1, 2, 0, 0, 0, 7, 4, 0, 0],
[0, 4, 9, 2, 0, 6, 0, 0, 7]
]
def printBoard():
print("Suduko Board")
for row in grid:
for elem in row:
print(elem, end=' ')
print()
def checkInRow(grid,row, num):
for i in range(0,9):
if(grid[row][i] == num):
return True
return False
def checkInCol(grid,col, num):
for i in range(0,9):
if(grid[i][col] == num):
return True
return False
def checkInBox(grid, row, col, num):
#This will give the starting point for the box
boxX = (row // 3) * 3
boxY = (col // 3) * 3
for i in range(3):
for j in range(3):
if((grid[boxY + j][boxX + i]) == num):
return True
return False
def findNextEmpty(grid, num):
for row in range(9):
for col in range(9):
if(grid[row][col] == num):
return row, col
return None
def checkSafe(grid, row, col, num): #Returns true if safe returns false if unsafe
return not checkInRow(grid,row,num) and not checkInCol(grid,col,num) and not checkInBox(grid,row,col,num)
#PROBLEM IS HERE \/
def solveSudoko(grid, i,j):
if not findNextEmpty(grid,0):
return True
else:
i = findNextEmpty(grid,0)[0] # Finds Row #
j = findNextEmpty(grid,0)[1] # Finds Col #
print(i, j)
for value in range(1,10):
if checkSafe(grid,i,j,value) == True:
grid[i][j] = value
printBoard()
print("--- %s seconds ---" % (time.time() - start_time))
if(solveSudoko(grid,i,j)):
return True
grid[i][j] = 0
return False
#print(str(value) + " can go in grid[" + str(i) + "]" + "[" + str(j) + "]")
printBoard()
solveSudoko(grid,0,0)
问题说明
我认为问题在于您的网格是一个列表，即可变的。这意味着如果您调用 solveSudoko(grid,i,j) 它不会复制网格，但内存中只有一个网格。所以在 solveSudoko 运行 出现问题后它不能回滚，因为你已经改变了原来的网格。可能的解决方案是使用非可变数据类型，如元组或有点难看，但也可能是制作网格的副本。
示例：
grid = [1,2,3]
def test(grid):
grid[0] = 0
test(grid)
print(grid)
---> [0,2,3]
快速但丑陋的解决方案
您可能可以在代码开头添加 import copy 并替换
if(solveSudoko(grid,i,j)):
来自
if(solveSudoko(copy.deepcopy(grid),i,j)):
示例：
grid = [1,2,3]
def test(grid):
grid[0] = 0
test(copy.deepcopy(grid))
print(grid)
---> [1,2,3]
请注意，使用 copy.copy 而不是 copy.deepcopy 也适用于该示例，因为整数是不可变的，但在您的代码中使用列表列表，您需要 copy.deepcopy.
好的解决方案
示例：
grid = (1,2,3)
def test(grid):
grid = (0,2,3)
test(grid)
print(grid)
---> (1,2,3)
元组的问题是获取新网格并不好玩。我可能会使用一些 class 来为我管理网格：
class Grid:
def __init__(self, grid):
assert type(grid) == tuple
self.grid = grid
@staticmethod
def gird_from_list(list_):
return Grid(tuple(list_[i][j] for i in range(len(list_)) for j in range(len(list_[0]))))
def __repr__(self):
return "\n".join(str(self.grid[i*9:(i+1)*9]) for i in range(9))
def set(self, i, j, value):
return Grid(tuple(value if i+j*9==k else x for k,x in enumerate(self.grid)))
tuple_grid = Grid.gird_from_list(gird)
tuple_grid2 = tuple_grid.set(8,8,0)
此处 grid_from_list 只是将您的列表转换为我的格式，而 __repr__ 为您提供了一个很好的二维网格表示，即使我实际上只保留了一个一维元组。如果您不知道 __repr__ 在您打印 class.
现在打印 tuple_grid 会产生
(7, 8, 0, 4, 0, 0, 1, 2, 0)
(6, 0, 0, 0, 7, 5, 0, 0, 9)
(0, 0, 0, 6, 0, 1, 0, 7, 8)
(0, 0, 7, 0, 4, 0, 2, 6, 0)
(0, 0, 1, 0, 5, 0, 9, 3, 0)
(9, 0, 4, 0, 6, 0, 0, 0, 5)
(0, 7, 0, 3, 0, 0, 0, 1, 2)
(1, 2, 0, 0, 0, 7, 4, 0, 0)
(0, 4, 9, 2, 0, 6, 0, 0, 7)
打印 tuple_grid2 会产生
(7, 8, 0, 4, 0, 0, 1, 2, 0)
(6, 0, 0, 0, 7, 5, 0, 0, 9)
(0, 0, 0, 6, 0, 1, 0, 7, 8)
(0, 0, 7, 0, 4, 0, 2, 6, 0)
(0, 0, 1, 0, 5, 0, 9, 3, 0)
(9, 0, 4, 0, 6, 0, 0, 0, 5)
(0, 7, 0, 3, 0, 0, 0, 1, 2)
(1, 2, 0, 0, 0, 7, 4, 0, 0)
(0, 4, 9, 2, 0, 6, 0, 0, 0)
因此，当您调用 set 时 gird 不会更改，但会为您提供一个具有新值的全新 gird。