如何改进这个数独求解器？
How to improve this Sudoku Solver?
前一段时间我有一个想法，想编写一个可以解决数独游戏的程序，所以我编写了下面的代码。该代码接收一个 9x9 整数列表作为输入，其中不完整的单元格由数字 0 表示。
def checkSolutions(grid, i, j):
"""
Given a Sudoku board and the position of an
incomplete cell, it returns a list with all
the possible numbers that this position can occupy.
"""
digits = [1, 2, 3, 4, 5, 6, 7, 8, 9]
solutions = []
solutions1x9 = [grid[x][j] for x in range(9)]
solutions9x1 = [grid[i][x] for x in range(9)]
rowGrid = i // 3
columnGrid = j // 3
solutions3x3 = [grid[i][j] for i in range(3*rowGrid, 3*rowGrid+3)
for j in range(3*columnGrid, 3*columnGrid+3)]
solutions = solutions + [i for i in digits if i not in solutions1x9]
solutions = solutions + [i for i in digits if i not in solutions9x1]
solutions = solutions + [i for i in digits if i not in solutions3x3]
solutions = list(set(solutions))
solutions = [i for i in solutions if i not in solutions1x9]
solutions = [i for i in solutions if i not in solutions9x1]
solutions = [i for i in solutions if i not in solutions3x3]
return solutions
def checkSudoku(grid):
"""
Given a Sudoku board, it returns True if it is
a board that follows the rules of the game and
returns False otherwise.
"""
digits = [1, 2, 3, 4, 5, 6, 7, 8, 9]
for i in range(9):
if sorted(grid[i]) != digits:
return False
for i in range(9):
column = [grid[j][i] for j in range(9)]
if sorted(column) != digits:
return False
for i in range(3):
for j in range(3):
grid3x3 = [grid[x][y] for x in range(3*i, 3*i+3)
for y in range(3*j, 3*j+3)]
if sorted(grid3x3) != digits:
return False
return True
def sudoku(grid):
"""
Given an incomplete Sudoku board, it prints on
the screen the solution of that game.
"""
for i in range(9):
for j in range(9):
if grid[i][j] == 0:
solutions = checkSolutions(grid, i, j)
if len(solutions) == 1:
grid[i][j] = solutions[0]
continue
for k in solutions:
auxGrid = [x.copy() for x in grid]
auxGrid[i][j] = k
sudoku(auxGrid)
if checkSudoku(grid):
print(grid)
我的问题是：如果函数 sudoku 接收以下列表作为输入
grid1 = [[0, 3, 7, 6, 0, 1, 5, 8, 4],
[8, 0, 0, 3, 0, 4, 9, 2, 0],
[6, 0, 9, 2, 5, 0, 3, 7, 1],
[9, 8, 0, 5, 6, 7, 1, 0, 0],
[0, 6, 0, 4, 1, 2, 0, 9, 0],
[0, 0, 1, 8, 3, 9, 0, 6, 5],
[7, 9, 6, 0, 4, 3, 8, 0, 2],
[0, 5, 8, 7, 0, 6, 0, 0, 9],
[1, 2, 4, 9, 0, 5, 6, 3, 0]]
它returns不到一秒的结果，也就是
[[2, 3, 7, 6, 9, 1, 5, 8, 4],
[8, 1, 5, 3, 7, 4, 9, 2, 6],
[6, 4, 9, 2, 5, 8, 3, 7, 1],
[9, 8, 2, 5, 6, 7, 1, 4, 3],
[5, 6, 3, 4, 1, 2, 7, 9, 8],
[4, 7, 1, 8, 3, 9, 2, 6, 5],
[7, 9, 6, 1, 4, 3, 8, 5, 2],
[3, 5, 8, 7, 2, 6, 4, 1, 9],
[1, 2, 4, 9, 8, 5, 6, 3, 7]]
但是如果它接收列表作为输入：
grid2 = [[1, 6, 8, 0, 0, 0, 9, 0, 2],
[0, 0, 0, 3, 0, 1, 0, 0, 0],
[0, 3, 0, 6, 2, 0, 0, 0, 0],
[0, 0, 9, 0, 0, 0, 1, 0, 6],
[0, 0, 1, 0, 0, 0, 3, 7, 0],
[0, 4, 3, 5, 0, 0, 0, 0, 9],
[0, 0, 0, 8, 0, 2, 6, 0, 0],
[0, 0, 0, 9, 0, 5, 0, 2, 3],
[2, 0, 6, 0, 3, 0, 7, 0, 0]]
应该returns
[[1, 6, 8, 4, 5, 7, 9, 3, 2],
[5, 7, 2, 3, 9, 1, 4, 6, 8],
[9, 3, 4, 6, 2, 8, 5, 1, 7],
[8, 2, 9, 7, 4, 3, 1, 5, 6],
[6, 5, 1, 2, 8, 9, 3, 7, 4],
[7, 4, 3, 5, 1, 6, 2, 8, 9],
[3, 9, 5, 8, 7, 2, 6, 4, 1],
[4, 1, 7, 9, 6, 5, 8, 2, 3],
[2, 8, 6, 1, 3, 4, 7, 9, 5]]
但是程序需要很长时间才能 运行 我什至不知道它是否 returns 什么（我等了 30 分钟才关闭代码执行）。所以我的疑惑是：
- 我的代码中是否存在某些输入类型的错误？
- 如何改进我的代码以接受包含更多空单元格的条目？
- 我的代码运行得非常好，对于包含更多空单元格的条目，需要更长的时间是否正常？
感谢您的帮助！
正如我评论的那样，这是一个很难的数独，所以你必须猜测几个单元格才能解决它。如果有帮助，您可以查看我之前编写的硬数独解算器：
def sudoku(grid):
sudoku_dict = {}
r = 'ABCDEFGHI'
c = '123456789'
for i in range(9):
for j in range(9):
sudoku_dict[r[i]+c[j]] = str(grid[i][j]) if grid[i][j] != 0 else c
square = [[x+y for x in i for y in j] for i in ('ABC','DEF','GHI') for j in ('123','456','789')]
peers = {}
for key in sudoku_dict.keys():
value = [i for i in square if key in i][0]
row = [[x+y for x in i for y in j][0] for i in key[0] for j in c]
col = [[x+y for x in i for y in j][0] for i in r for j in key[1]]
peers[key] = set(x for x in value+row+col if x != key)
for i in range(9):
sudoku_dict = Check(sudoku_dict,peers)
sudoku_dict = search(sudoku_dict, peers)
solution = []
for i in r:
solution.append([])
for j in c:
solution[r.find(i)].append(int(sudoku_dict[i+j]))
return solution
def Check(sudoku_dict, peers):
for k,v in sudoku_dict.items():
if len(v) == 1:
for s in peers[k]:
sudoku_dict[s] = sudoku_dict[s].replace(v,'')
if len(sudoku_dict[s])==0:
return False
return sudoku_dict
def search(sudoku_dict,peers):
if Check(sudoku_dict,peers)==False:
return False
if all(len(sudoku_dict[s]) == 1 for s in sudoku_dict.keys()):
return sudoku_dict
n,s = min((len(sudoku_dict[s]), s) for s in sudoku_dict.keys() if len(sudoku_dict[s]) > 1)
res = []
for value in sudoku_dict[s]:
new_sudoku_dict = sudoku_dict.copy()
new_sudoku_dict[s] = value
ans = search(new_sudoku_dict, peers)
if ans:
res.append(ans)
if len(res) > 1:
raise Exception("Error")
elif len(res) == 1:
return res[0]
您可以通过在嵌套循环末尾向 sudoku() 函数添加 return 语句来让您的程序解决第二个难题。下面的代码有这个修复和一些其他的返工想法：
DIGITS = [1, 2, 3, 4, 5, 6, 7, 8, 9]
def checkSolutions(grid, i, j):
"""
Given a Sudoku board, and the position of an
incomplete cell, it returns a list with all
the possible numbers that can occupy this position.
"""
solutions1x9 = [grid[x][j] for x in range(9)]
solutions9x1 = [grid[i][x] for x in range(9)]
rowGrid = 3 * (i // 3)
columnGrid = 3 * (j // 3)
solutions3x3 = [grid[i][j] for i in range(rowGrid, rowGrid + 3) for j in range(columnGrid, columnGrid + 3)]
return [digit for digit in DIGITS if digit not in solutions1x9 and digit not in solutions9x1 and digit not in solutions3x3]
def checkSudoku(grid):
"""
Given a Sudoku board, it returns True if it is
a board that follows the rules of the game and
returns False otherwise.
"""
for i in range(9):
if sorted(grid[i]) != DIGITS:
return False
for j in range(9):
column = [grid[i][j] for i in range(9)]
if sorted(column) != DIGITS:
return False
for i in range(3):
for j in range(3):
grid3x3 = [grid[x][y] for x in range(3 * i, 3 * i + 3) for y in range(3 * j, 3 * j + 3)]
if sorted(grid3x3) != DIGITS:
return False
return True
def sudoku(grid):
"""
Given an incomplete Sudoku board, it prints on
the screen the solution of that game.
"""
for i in range(9):
for j in range(9):
if grid[i][j] == 0:
solutions = checkSolutions(grid, i, j)
if len(solutions) == 1:
grid[i][j] = solutions[0] # permanent change to *this* reality
continue
for k in solutions:
auxGrid = [x.copy() for x in grid] # spawn a new reality
auxGrid[i][j] = k
sudoku(auxGrid)
return # already solved it recursively or no solution in *this* reality
if checkSudoku(grid):
print(grid)
grid2 = [[1, 6, 8, 0, 0, 0, 9, 0, 2],
[0, 0, 0, 3, 0, 1, 0, 0, 0],
[0, 3, 0, 6, 2, 0, 0, 0, 0],
[0, 0, 9, 0, 0, 0, 1, 0, 6],
[0, 0, 1, 0, 0, 0, 3, 7, 0],
[0, 4, 3, 5, 0, 0, 0, 0, 9],
[0, 0, 0, 8, 0, 2, 6, 0, 0],
[0, 0, 0, 9, 0, 5, 0, 2, 3],
[2, 0, 6, 0, 3, 0, 7, 0, 0]]
sudoku(grid2)
输出
> python3 test.py
[[1, 6, 8, 4, 5, 7, 9, 3, 2],
[5, 7, 2, 3, 9, 1, 4, 6, 8],
[9, 3, 4, 6, 2, 8, 5, 1, 7],
[8, 2, 9, 7, 4, 3, 1, 5, 6],
[6, 5, 1, 2, 8, 9, 3, 7, 4],
[7, 4, 3, 5, 1, 6, 2, 8, 9],
[3, 9, 5, 8, 7, 2, 6, 4, 1],
[4, 1, 7, 9, 6, 5, 8, 2, 3],
[2, 8, 6, 1, 3, 4, 7, 9, 5]]
>
你的解算器是一个蛮力解算器，它使用了一些关于游戏本身的智慧。所以，我不能保证不会有一个谜题再次需要很长时间才能完成。一个更高效的求解器可能会在诉诸蛮力之前尝试人类放置数字的所有技巧。
我所做的修改可能会阻止您的代码找到多个 解决方案（如果存在）。
前一段时间我有一个想法，想编写一个可以解决数独游戏的程序，所以我编写了下面的代码。该代码接收一个 9x9 整数列表作为输入，其中不完整的单元格由数字 0 表示。
def checkSolutions(grid, i, j):
"""
Given a Sudoku board and the position of an
incomplete cell, it returns a list with all
the possible numbers that this position can occupy.
"""
digits = [1, 2, 3, 4, 5, 6, 7, 8, 9]
solutions = []
solutions1x9 = [grid[x][j] for x in range(9)]
solutions9x1 = [grid[i][x] for x in range(9)]
rowGrid = i // 3
columnGrid = j // 3
solutions3x3 = [grid[i][j] for i in range(3*rowGrid, 3*rowGrid+3)
for j in range(3*columnGrid, 3*columnGrid+3)]
solutions = solutions + [i for i in digits if i not in solutions1x9]
solutions = solutions + [i for i in digits if i not in solutions9x1]
solutions = solutions + [i for i in digits if i not in solutions3x3]
solutions = list(set(solutions))
solutions = [i for i in solutions if i not in solutions1x9]
solutions = [i for i in solutions if i not in solutions9x1]
solutions = [i for i in solutions if i not in solutions3x3]
return solutions
def checkSudoku(grid):
"""
Given a Sudoku board, it returns True if it is
a board that follows the rules of the game and
returns False otherwise.
"""
digits = [1, 2, 3, 4, 5, 6, 7, 8, 9]
for i in range(9):
if sorted(grid[i]) != digits:
return False
for i in range(9):
column = [grid[j][i] for j in range(9)]
if sorted(column) != digits:
return False
for i in range(3):
for j in range(3):
grid3x3 = [grid[x][y] for x in range(3*i, 3*i+3)
for y in range(3*j, 3*j+3)]
if sorted(grid3x3) != digits:
return False
return True
def sudoku(grid):
"""
Given an incomplete Sudoku board, it prints on
the screen the solution of that game.
"""
for i in range(9):
for j in range(9):
if grid[i][j] == 0:
solutions = checkSolutions(grid, i, j)
if len(solutions) == 1:
grid[i][j] = solutions[0]
continue
for k in solutions:
auxGrid = [x.copy() for x in grid]
auxGrid[i][j] = k
sudoku(auxGrid)
if checkSudoku(grid):
print(grid)
我的问题是：如果函数 sudoku 接收以下列表作为输入
grid1 = [[0, 3, 7, 6, 0, 1, 5, 8, 4],
[8, 0, 0, 3, 0, 4, 9, 2, 0],
[6, 0, 9, 2, 5, 0, 3, 7, 1],
[9, 8, 0, 5, 6, 7, 1, 0, 0],
[0, 6, 0, 4, 1, 2, 0, 9, 0],
[0, 0, 1, 8, 3, 9, 0, 6, 5],
[7, 9, 6, 0, 4, 3, 8, 0, 2],
[0, 5, 8, 7, 0, 6, 0, 0, 9],
[1, 2, 4, 9, 0, 5, 6, 3, 0]]
它returns不到一秒的结果，也就是
[[2, 3, 7, 6, 9, 1, 5, 8, 4],
[8, 1, 5, 3, 7, 4, 9, 2, 6],
[6, 4, 9, 2, 5, 8, 3, 7, 1],
[9, 8, 2, 5, 6, 7, 1, 4, 3],
[5, 6, 3, 4, 1, 2, 7, 9, 8],
[4, 7, 1, 8, 3, 9, 2, 6, 5],
[7, 9, 6, 1, 4, 3, 8, 5, 2],
[3, 5, 8, 7, 2, 6, 4, 1, 9],
[1, 2, 4, 9, 8, 5, 6, 3, 7]]
但是如果它接收列表作为输入：
grid2 = [[1, 6, 8, 0, 0, 0, 9, 0, 2],
[0, 0, 0, 3, 0, 1, 0, 0, 0],
[0, 3, 0, 6, 2, 0, 0, 0, 0],
[0, 0, 9, 0, 0, 0, 1, 0, 6],
[0, 0, 1, 0, 0, 0, 3, 7, 0],
[0, 4, 3, 5, 0, 0, 0, 0, 9],
[0, 0, 0, 8, 0, 2, 6, 0, 0],
[0, 0, 0, 9, 0, 5, 0, 2, 3],
[2, 0, 6, 0, 3, 0, 7, 0, 0]]
应该returns
[[1, 6, 8, 4, 5, 7, 9, 3, 2],
[5, 7, 2, 3, 9, 1, 4, 6, 8],
[9, 3, 4, 6, 2, 8, 5, 1, 7],
[8, 2, 9, 7, 4, 3, 1, 5, 6],
[6, 5, 1, 2, 8, 9, 3, 7, 4],
[7, 4, 3, 5, 1, 6, 2, 8, 9],
[3, 9, 5, 8, 7, 2, 6, 4, 1],
[4, 1, 7, 9, 6, 5, 8, 2, 3],
[2, 8, 6, 1, 3, 4, 7, 9, 5]]
但是程序需要很长时间才能 运行 我什至不知道它是否 returns 什么（我等了 30 分钟才关闭代码执行）。所以我的疑惑是：
- 我的代码中是否存在某些输入类型的错误？
- 如何改进我的代码以接受包含更多空单元格的条目？
- 我的代码运行得非常好，对于包含更多空单元格的条目，需要更长的时间是否正常？
感谢您的帮助！
正如我评论的那样，这是一个很难的数独，所以你必须猜测几个单元格才能解决它。如果有帮助，您可以查看我之前编写的硬数独解算器：
def sudoku(grid):
sudoku_dict = {}
r = 'ABCDEFGHI'
c = '123456789'
for i in range(9):
for j in range(9):
sudoku_dict[r[i]+c[j]] = str(grid[i][j]) if grid[i][j] != 0 else c
square = [[x+y for x in i for y in j] for i in ('ABC','DEF','GHI') for j in ('123','456','789')]
peers = {}
for key in sudoku_dict.keys():
value = [i for i in square if key in i][0]
row = [[x+y for x in i for y in j][0] for i in key[0] for j in c]
col = [[x+y for x in i for y in j][0] for i in r for j in key[1]]
peers[key] = set(x for x in value+row+col if x != key)
for i in range(9):
sudoku_dict = Check(sudoku_dict,peers)
sudoku_dict = search(sudoku_dict, peers)
solution = []
for i in r:
solution.append([])
for j in c:
solution[r.find(i)].append(int(sudoku_dict[i+j]))
return solution
def Check(sudoku_dict, peers):
for k,v in sudoku_dict.items():
if len(v) == 1:
for s in peers[k]:
sudoku_dict[s] = sudoku_dict[s].replace(v,'')
if len(sudoku_dict[s])==0:
return False
return sudoku_dict
def search(sudoku_dict,peers):
if Check(sudoku_dict,peers)==False:
return False
if all(len(sudoku_dict[s]) == 1 for s in sudoku_dict.keys()):
return sudoku_dict
n,s = min((len(sudoku_dict[s]), s) for s in sudoku_dict.keys() if len(sudoku_dict[s]) > 1)
res = []
for value in sudoku_dict[s]:
new_sudoku_dict = sudoku_dict.copy()
new_sudoku_dict[s] = value
ans = search(new_sudoku_dict, peers)
if ans:
res.append(ans)
if len(res) > 1:
raise Exception("Error")
elif len(res) == 1:
return res[0]
您可以通过在嵌套循环末尾向 sudoku() 函数添加 return 语句来让您的程序解决第二个难题。下面的代码有这个修复和一些其他的返工想法：
DIGITS = [1, 2, 3, 4, 5, 6, 7, 8, 9]
def checkSolutions(grid, i, j):
"""
Given a Sudoku board, and the position of an
incomplete cell, it returns a list with all
the possible numbers that can occupy this position.
"""
solutions1x9 = [grid[x][j] for x in range(9)]
solutions9x1 = [grid[i][x] for x in range(9)]
rowGrid = 3 * (i // 3)
columnGrid = 3 * (j // 3)
solutions3x3 = [grid[i][j] for i in range(rowGrid, rowGrid + 3) for j in range(columnGrid, columnGrid + 3)]
return [digit for digit in DIGITS if digit not in solutions1x9 and digit not in solutions9x1 and digit not in solutions3x3]
def checkSudoku(grid):
"""
Given a Sudoku board, it returns True if it is
a board that follows the rules of the game and
returns False otherwise.
"""
for i in range(9):
if sorted(grid[i]) != DIGITS:
return False
for j in range(9):
column = [grid[i][j] for i in range(9)]
if sorted(column) != DIGITS:
return False
for i in range(3):
for j in range(3):
grid3x3 = [grid[x][y] for x in range(3 * i, 3 * i + 3) for y in range(3 * j, 3 * j + 3)]
if sorted(grid3x3) != DIGITS:
return False
return True
def sudoku(grid):
"""
Given an incomplete Sudoku board, it prints on
the screen the solution of that game.
"""
for i in range(9):
for j in range(9):
if grid[i][j] == 0:
solutions = checkSolutions(grid, i, j)
if len(solutions) == 1:
grid[i][j] = solutions[0] # permanent change to *this* reality
continue
for k in solutions:
auxGrid = [x.copy() for x in grid] # spawn a new reality
auxGrid[i][j] = k
sudoku(auxGrid)
return # already solved it recursively or no solution in *this* reality
if checkSudoku(grid):
print(grid)
grid2 = [[1, 6, 8, 0, 0, 0, 9, 0, 2],
[0, 0, 0, 3, 0, 1, 0, 0, 0],
[0, 3, 0, 6, 2, 0, 0, 0, 0],
[0, 0, 9, 0, 0, 0, 1, 0, 6],
[0, 0, 1, 0, 0, 0, 3, 7, 0],
[0, 4, 3, 5, 0, 0, 0, 0, 9],
[0, 0, 0, 8, 0, 2, 6, 0, 0],
[0, 0, 0, 9, 0, 5, 0, 2, 3],
[2, 0, 6, 0, 3, 0, 7, 0, 0]]
sudoku(grid2)
输出
> python3 test.py
[[1, 6, 8, 4, 5, 7, 9, 3, 2],
[5, 7, 2, 3, 9, 1, 4, 6, 8],
[9, 3, 4, 6, 2, 8, 5, 1, 7],
[8, 2, 9, 7, 4, 3, 1, 5, 6],
[6, 5, 1, 2, 8, 9, 3, 7, 4],
[7, 4, 3, 5, 1, 6, 2, 8, 9],
[3, 9, 5, 8, 7, 2, 6, 4, 1],
[4, 1, 7, 9, 6, 5, 8, 2, 3],
[2, 8, 6, 1, 3, 4, 7, 9, 5]]
>
你的解算器是一个蛮力解算器，它使用了一些关于游戏本身的智慧。所以，我不能保证不会有一个谜题再次需要很长时间才能完成。一个更高效的求解器可能会在诉诸蛮力之前尝试人类放置数字的所有技巧。
我所做的修改可能会阻止您的代码找到多个 解决方案（如果存在）。