python - Sudoku Alogirthm 无法按预期工作
问题描述
我正在尝试解决数独结果。但它没有像我预期的那样工作。
import numpy as np
grid = [[5, 3, 0, 0, 7, 0, 0, 0, 0],#x0
[6, 0, 0, 1, 9, 5, 0, 0, 0],#x1
[0, 9, 8, 0, 0, 0, 0, 6, 0],#x2
[8, 0, 0, 0, 6, 0, 0, 0, 3],#x3
[4, 0, 0, 9, 0, 3, 0, 0, 1],#x4
[7, 0, 0, 0, 2, 0, 0, 0, 6],#x5
[0, 6, 0, 0, 0, 0, 2, 8, 0],#x6
[0, 0, 0, 4, 1, 9, 0, 0, 5],#x7
[0, 0, 0, 0, 8, 0, 0, 7, 9]]#x8
# y0 y1 y2 y3 y4 y5 y6 y7 y8
def possible(x,y,n, matris):
for i in range(0, 9):
if matris[x][i] == n:
return False
for i in range(0, 9):
if matris[i][y] == n:
return False
x0 = (x//3)*3
y0 = (x//3)*3
for i in range(0, 3):
for j in range(0, 3):
if matris[x0+i][y0+j] == n:
return False
return True
def solve(sudoku):
for x in range(9):
for y in range(9):
if sudoku[x][y] == 0:
for n in range(1, 10):
if possible(x, y, n, sudoku):
sudoku[x][y]=n
return np.matrix(sudoku)
print(solve(grid))
如您所见,输出没有给我未解决的数独网格的结果。我看不出有什么问题。
[[5 3 4 2 7 1 0 0 0]
[6 7 2 1 9 5 0 0 0]
[1 9 8 0 0 0 0 6 0]
[8 5 7 0 6 4 1 0 3]
[4 8 5 9 0 3 7 0 1]
[7 1 0 8 2 0 5 0 6]
[3 6 1 0 4 0 2 8 0]
[0 0 6 4 1 9 3 0 5]
[0 4 0 6 8 0 0 7 9]]
可能是什么问题,有什么想法吗?
解决方案
首先,您在问题中列出的难题没有解决方案。您可以在Sudoku Solutions上进行验证。单击加载按钮并输入“trincot_for_so”作为识别码以加载拼图。
如果在中心的 3x3 框中将 9 更改为 0,则有一个解决方案。该解决方案将在该单元格中有一个 8。
其次,您的代码在这一行中有一个(复制/粘贴)错误:
y0 = (x//3)*3
那应该是:
y0 = (y//3)*3
要解决确实有解决方案的谜题,您需要实施回溯。为此,您可以使用递归。您的主要功能如下所示:
def solve(sudoku):
for x in range(9):
for y in range(9):
if sudoku[x][y] == 0:
for n in range(1, 10):
if possible(x, y, n, sudoku):
sudoku[x][y] = n
# Use recursion to solve the rest of the puzzle
result = solve(sudoku)
# If rest of the puzzle could be solved, return the solution
if result is not None:
return result
# Backtrack. Allow inner loop to try another value
sudoku[x][y] = 0
# If none of the values for this cell work: no solution (None)
return
# We only get here when solve was called with a completely filled-in grid
return np.matrix(sudoku)
推荐阅读
- sql - SQL 语句没有返回正确的数据
- postgresql - 如何使用烧瓶迁移迁移创建视图?
- java - Javac 不编译依赖于 jar 和类的 java 类
- javascript - 如何使用 ajax 从烧瓶中获取数据到我的模板?
- distributed-system - Dolphindb集群支持多个数据节点使用同一个磁盘目录?
- ios - 如何将可观察的元组元素与可观察的单个元素结合起来?
- java - 使用 RestHighLevelClient 的 ElasticSearch 批量插入错误
- javascript - 根据操作系统分辨率和 CSS 位置,会出现轻微的空间
- c# - 无法捕获在具有调试模式的任务中生成的异常
- javascript - 奇怪的 Java Base64.decode 结果