Python 递归数独求解器
Python Recursive Sudoku Solver
这是 recursive Sudoku solve 代码，这不是学校作业。我想不出如何通过我以前的动作把它弄到 "back up"。它卡在 first row 的末尾，因为该位置没有有效数字，只是一直试图找到适合那里的数字。我遇到问题的函数是 check.
阅读您的回答后，我对这个问题有了更深入的了解，但还不完全是。它一直返回并退出递归
import sys
class Board:
def __init__(self, grid):
self.grid = grid
self.ogrid = grid
def get_col(self, col):
column = []
for i in self.grid:
column.append(str(i[col]))
return column
def get_row(self, row):
return self.grid[row]
def check_row(self, r, val):
row = self.grid[r]
for i in range(0,9):
if str(val) in row:
return False
return True
def check_col(self, column, val):
col = self.get_col(column)
for i in range(0,9):
if str(val) in col:
return False
return True
def check_square(self, x, y, val):
col = (y//3)*3
row = (x//3)*3
s = ''
for i in range(row, row+3):
for j in range(col, col+3):
s += str(self.grid[i][j])
if str(val) in s:
return False
return True
def check_cell(self, x, y, val):
if self.check_col(y, val) == False:
return False
elif self.check_row(x, val) == False:
return False
elif self.check_square(x, y, val) == False:
return False
return True
def check(self, x, y):
if y == 9:
y = 0
x += 1
if x == 9:
self.print_board()
sys.exit()
if self.ogrid[x][y] == '.':
for val in range(1,10):
if self.check_cell(x, y, val):
self.grid[x][y] = str(val)
self.check(x, y+1)
##I don't think the reset is working and I'm not sure why
if self.ogrid[x][y] == '.': #reset index
self.grid[x][y] = '.'
self.print_board() #Notice it never prints a '.' in spots that have changed
else:
self.check(x,y+1)
return
def print_board(self):
for i in range(0,9):
for j in range(0,9):
sys.stdout.write(self.grid[i][j])
if j == 2 or j == 5:
sys.stdout.write(' ')
if i == 2 or i == 5:
sys.stdout.write('\n')
print('')
def main():
f = open("./easySudoku.txt",'r')
s = ''
grid = []
row = []
for line in f:
s += line
print line
s = s.replace(' ','')
s = s.replace('\n','')
for i in range(0,9):
row = []
for j in range(0,9):
row.append(s[(i*9) + j])
grid.append(row)
sudoku = Board(grid)
sudoku.check(0,0, 1)
if __name__ == "__main__":
main()
检查功能的工作原理如下
check takes an x and y coordinate for the board and starts at 0,0 it runs through a for loop from 1-9 and sets the first value that works at that index and then moves to the next index. When it reaches the end of a row it moves down one row and back to the first column. If no values work at an index then reset current index to '.' and move index back one and continue counting towards 9. i.e. if current value at index 0,0 is 2 then continue to 3. If 3 works then move forward one index so on and so forth until the board has been filled. For the simplistic answer it tries every value, 1-9, at every empty index
如果不清楚，请告诉我
这也是我正在使用的开发板
..6 ..7 3..
.18 ..9 .5.
5.. ... .64
92. .8. ...
... 763 ...
... .9. .75
63. ... ..8
.9. 3.. 52.
..2 4.. 6..
问题是您似乎为尝试的每个数字递归一步，这将消耗所有理智的堆栈。我建议您也使用迭代并使用 return 来进行备份（这样您应该只使用 81 个堆栈帧左右 - 当您获得一千级堆栈帧时它会失败）。
我以前做过求解器，它会很快找到解决方案...
我不明白这个片段：
if y == -1:
y = 8
x -= 1
如果 y 等于行中的最后一个位置，您将其设置为 8，这是行中最后一个位置的索引？这可能是它无法正常进行的原因吗？
我为检查您的代码所做的工作：将此行添加为您的 check 方法的第一行：
raw_input('x: %d, y: %d, val: %d' % (x,y,val))
并在输入数字后打印板。
您的求解器似乎在 (x,y) = (0,3) 处犯了第一个错误。它检查所有不超过 9 的数字，然后将 9 放在那里。根据您的算法，它应该放一个 1。挂断是您的 check_square 方法。你应该
col = (y//3)*3
row = (x//3)*3
修复后，下一个错误出现在 (x,y) = (1,8)，从 self.check(1, 8, 1) 开始。这个正方形（一直到 self.check(1, 8, 9)）没有合法值（到目前为止使用您的算法）。所以next叫做self.check(1, 8, 10)。由于 val==10，它 returns，然后在对 self.check(1, 8, 9) 的调用中，最后一行 self.check(x, y-1, val+1) 被调用，即 self.check(1, 7, 10)。它，当然立即 returns 以及因为 val == 10。我们回到 self.check(1, 8, 8) 并调用方法定义的最后一行。接下来要执行的是 self.check(1, 7, 9)，它会产生下一个 self.check(1, 8, 1)。看起来熟悉？我们已经在这里，同时没有状态变化。不知不觉就变成了死循环
是不是很困惑？当然是。程序员试图避免递归是有原因的，除非在教授递归概念时。追踪这些类型的递归错误很困难，但只需打印几行就可以完成。
P.S。你的算法很有趣。我想知道你是在哪里找到它的……这绝对不是人类的游戏方式（包括所有的猜测和编辑）。 FWIW，我首先只会在棋盘上插入一个值，如果该值是方块的唯一合法移动，并且只有当棋盘上的所有空白方块都不明确时才猜测。
编辑后编辑
在顶部添加标准库的一部分 import copy，并将 __init__ 更改为 self.ogrid = copy.deepcopy(grid)。应该可以解决你的问题。参见 。您创建网格复制版本的方法实现了同样的效果。
好的，我解决了我的问题！
这是我所做的。我采纳了@Skyking 给我的建议，只对索引进行递归，而不是按我最初拥有的每个索引的值进行递归。我改变的第二件事是采纳@James Pringles 关于如何修复我的 check_square 函数和复制网格的建议，这样当 grid 改变时 ogrid 不会改变。
因为我不能给两张绿色支票，所以我把它给了@James Pringle，因为 he/she 对我帮助最大，但如果没有@Skyking 的建议
，我不可能得到它
这是完成的代码
import sys
import copy
class Board:
def __init__(self, grid):
self.grid = grid
self.ogrid = copy.deepcopy(grid)
def get_col(self, col):
column = []
for i in self.grid:
column.append(str(i[col]))
return column
def get_row(self, row):
return self.grid[row]
def check_row(self, r, val):
row = self.grid[r]
if str(val) in row:
return False
return True
def check_col(self, column, val):
col = self.get_col(column)
if str(val) in col:
return False
return True
def check_square(self, x, y, val):
col = (y//3)*3
row = (x//3)*3
s = ''
for i in range(row, row+3):
for j in range(col, col+3):
s += str(self.grid[i][j])
if str(val) in s:
return False
return True
def check_cell(self, x, y, val):
if self.check_col(y, val) == False:
return False
elif self.check_row(x, val) == False:
return False
elif self.check_square(x, y, val) == False:
return False
return True
def check(self, x, y):
if y == 9:
y = 0
x += 1
if x == 9:
self.print_board()
sys.exit()
if self.ogrid[x][y] == '.':
for val in range(1,10):
if self.check_cell(x, y, val):
self.grid[x][y] = str(val)
self.check(x, y+1)
if self.ogrid[x][y] == '.':
self.grid[x][y] = self.ogrid[x][y]
else:
self.check(x,y+1)
return True
def print_board(self):
for i in range(0,9):
for j in range(0,9):
sys.stdout.write(self.grid[i][j])
if j == 2 or j == 5:
sys.stdout.write(' ')
if i == 2 or i == 5:
sys.stdout.write('\n')
print('')
def main():
f = open("./easySudoku.txt",'r')
s = ''
grid = []
row = []
for line in f:
s += line
s = s.replace(' ','')
s = s.replace('\n','')
for i in range(0,9):
row = []
for j in range(0,9):
row.append(s[(i*9) + j])
grid.append(row)
sudoku = Board(grid)
sudoku.check(0,0)
print('shouldn\'t be here')
if __name__ == "__main__":
main()
这是 recursive Sudoku solve 代码，这不是学校作业。我想不出如何通过我以前的动作把它弄到 "back up"。它卡在 first row 的末尾，因为该位置没有有效数字，只是一直试图找到适合那里的数字。我遇到问题的函数是 check.
阅读您的回答后，我对这个问题有了更深入的了解，但还不完全是。它一直返回并退出递归
import sys
class Board:
def __init__(self, grid):
self.grid = grid
self.ogrid = grid
def get_col(self, col):
column = []
for i in self.grid:
column.append(str(i[col]))
return column
def get_row(self, row):
return self.grid[row]
def check_row(self, r, val):
row = self.grid[r]
for i in range(0,9):
if str(val) in row:
return False
return True
def check_col(self, column, val):
col = self.get_col(column)
for i in range(0,9):
if str(val) in col:
return False
return True
def check_square(self, x, y, val):
col = (y//3)*3
row = (x//3)*3
s = ''
for i in range(row, row+3):
for j in range(col, col+3):
s += str(self.grid[i][j])
if str(val) in s:
return False
return True
def check_cell(self, x, y, val):
if self.check_col(y, val) == False:
return False
elif self.check_row(x, val) == False:
return False
elif self.check_square(x, y, val) == False:
return False
return True
def check(self, x, y):
if y == 9:
y = 0
x += 1
if x == 9:
self.print_board()
sys.exit()
if self.ogrid[x][y] == '.':
for val in range(1,10):
if self.check_cell(x, y, val):
self.grid[x][y] = str(val)
self.check(x, y+1)
##I don't think the reset is working and I'm not sure why
if self.ogrid[x][y] == '.': #reset index
self.grid[x][y] = '.'
self.print_board() #Notice it never prints a '.' in spots that have changed
else:
self.check(x,y+1)
return
def print_board(self):
for i in range(0,9):
for j in range(0,9):
sys.stdout.write(self.grid[i][j])
if j == 2 or j == 5:
sys.stdout.write(' ')
if i == 2 or i == 5:
sys.stdout.write('\n')
print('')
def main():
f = open("./easySudoku.txt",'r')
s = ''
grid = []
row = []
for line in f:
s += line
print line
s = s.replace(' ','')
s = s.replace('\n','')
for i in range(0,9):
row = []
for j in range(0,9):
row.append(s[(i*9) + j])
grid.append(row)
sudoku = Board(grid)
sudoku.check(0,0, 1)
if __name__ == "__main__":
main()
检查功能的工作原理如下
checktakes an x and y coordinate for the board and starts at0,0it runs through a for loop from1-9and sets the first value that works at that index and then moves to the next index. When it reaches the end of a row it moves down one row and back to the first column. If no values work at an index then reset current index to'.'and move index back one and continue counting towards9. i.e. if current value at index0,0is2then continue to3. If3works then move forward one index so on and so forth until the board has been filled. For the simplistic answer it tries every value,1-9, at every empty index
如果不清楚，请告诉我
这也是我正在使用的开发板
..6 ..7 3..
.18 ..9 .5.
5.. ... .64
92. .8. ...
... 763 ...
... .9. .75
63. ... ..8
.9. 3.. 52.
..2 4.. 6..
问题是您似乎为尝试的每个数字递归一步，这将消耗所有理智的堆栈。我建议您也使用迭代并使用 return 来进行备份（这样您应该只使用 81 个堆栈帧左右 - 当您获得一千级堆栈帧时它会失败）。
我以前做过求解器，它会很快找到解决方案...
我不明白这个片段：
if y == -1:
y = 8
x -= 1
如果 y 等于行中的最后一个位置，您将其设置为 8，这是行中最后一个位置的索引？这可能是它无法正常进行的原因吗？
我为检查您的代码所做的工作：将此行添加为您的 check 方法的第一行：
raw_input('x: %d, y: %d, val: %d' % (x,y,val))
并在输入数字后打印板。
您的求解器似乎在 (x,y) = (0,3) 处犯了第一个错误。它检查所有不超过 9 的数字，然后将 9 放在那里。根据您的算法，它应该放一个 1。挂断是您的 check_square 方法。你应该
col = (y//3)*3
row = (x//3)*3
修复后，下一个错误出现在 (x,y) = (1,8)，从 self.check(1, 8, 1) 开始。这个正方形（一直到 self.check(1, 8, 9)）没有合法值（到目前为止使用您的算法）。所以next叫做self.check(1, 8, 10)。由于 val==10，它 returns，然后在对 self.check(1, 8, 9) 的调用中，最后一行 self.check(x, y-1, val+1) 被调用，即 self.check(1, 7, 10)。它，当然立即 returns 以及因为 val == 10。我们回到 self.check(1, 8, 8) 并调用方法定义的最后一行。接下来要执行的是 self.check(1, 7, 9)，它会产生下一个 self.check(1, 8, 1)。看起来熟悉？我们已经在这里，同时没有状态变化。不知不觉就变成了死循环
是不是很困惑？当然是。程序员试图避免递归是有原因的，除非在教授递归概念时。追踪这些类型的递归错误很困难，但只需打印几行就可以完成。
P.S。你的算法很有趣。我想知道你是在哪里找到它的……这绝对不是人类的游戏方式（包括所有的猜测和编辑）。 FWIW，我首先只会在棋盘上插入一个值，如果该值是方块的唯一合法移动，并且只有当棋盘上的所有空白方块都不明确时才猜测。
编辑后编辑
在顶部添加标准库的一部分 import copy，并将 __init__ 更改为 self.ogrid = copy.deepcopy(grid)。应该可以解决你的问题。参见 。您创建网格复制版本的方法实现了同样的效果。
好的，我解决了我的问题！
这是我所做的。我采纳了@Skyking 给我的建议，只对索引进行递归，而不是按我最初拥有的每个索引的值进行递归。我改变的第二件事是采纳@James Pringles 关于如何修复我的 check_square 函数和复制网格的建议，这样当 grid 改变时 ogrid 不会改变。
因为我不能给两张绿色支票，所以我把它给了@James Pringle，因为 he/she 对我帮助最大，但如果没有@Skyking 的建议
这是完成的代码
import sys
import copy
class Board:
def __init__(self, grid):
self.grid = grid
self.ogrid = copy.deepcopy(grid)
def get_col(self, col):
column = []
for i in self.grid:
column.append(str(i[col]))
return column
def get_row(self, row):
return self.grid[row]
def check_row(self, r, val):
row = self.grid[r]
if str(val) in row:
return False
return True
def check_col(self, column, val):
col = self.get_col(column)
if str(val) in col:
return False
return True
def check_square(self, x, y, val):
col = (y//3)*3
row = (x//3)*3
s = ''
for i in range(row, row+3):
for j in range(col, col+3):
s += str(self.grid[i][j])
if str(val) in s:
return False
return True
def check_cell(self, x, y, val):
if self.check_col(y, val) == False:
return False
elif self.check_row(x, val) == False:
return False
elif self.check_square(x, y, val) == False:
return False
return True
def check(self, x, y):
if y == 9:
y = 0
x += 1
if x == 9:
self.print_board()
sys.exit()
if self.ogrid[x][y] == '.':
for val in range(1,10):
if self.check_cell(x, y, val):
self.grid[x][y] = str(val)
self.check(x, y+1)
if self.ogrid[x][y] == '.':
self.grid[x][y] = self.ogrid[x][y]
else:
self.check(x,y+1)
return True
def print_board(self):
for i in range(0,9):
for j in range(0,9):
sys.stdout.write(self.grid[i][j])
if j == 2 or j == 5:
sys.stdout.write(' ')
if i == 2 or i == 5:
sys.stdout.write('\n')
print('')
def main():
f = open("./easySudoku.txt",'r')
s = ''
grid = []
row = []
for line in f:
s += line
s = s.replace(' ','')
s = s.replace('\n','')
for i in range(0,9):
row = []
for j in range(0,9):
row.append(s[(i*9) + j])
grid.append(row)
sudoku = Board(grid)
sudoku.check(0,0)
print('shouldn\'t be here')
if __name__ == "__main__":
main()