python - 打印工作,但使用回溯解决数独时返回值为 None
问题描述
我编写了以下代码来使用回溯方法解决数独游戏。可以打印正确的结果,但是我还没有找到一种方法来获得与返回值相同的结果而不是打印它。我必须如何更改程序才能使其正常工作?
import numpy as np
def find_possible(sudoku,r,c):
"""returns the possible Values as numpy array for a given position"""
position = sudoku[r, c]
if position == 0:
line = sudoku[r, :]
column = sudoku[: ,c]
r0 = (r//3)*3
c0 = (c//3)*3
square = sudoku[r0:r0+3,c0:c0+3]
numbers = np.arange(1, 10)
blocked_numbers = np.unique(np.append(np.append(line,column),square))
return np.setdiff1d(numbers,blocked_numbers)
else: return np.array([])
def backtrack(sudoku):
"""solve the game with the backtracking method"""
for r in range(9):
for c in range(9):
list_of_possible = find_possible(sudoku,r, c)
if sudoku[r,c] == 0:
for i in range(len(list_of_possible)):
sudoku[r,c] = list_of_possible[i]
backtrack(sudoku)
sudoku[r,c] = 0
return
result = sudoku
print(result)
table = np.array([[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]])
backtrack(table)
编辑
如果将print
替换为return
,则返回值仍然是None
因为第一个return
。如果我给第一return
个数独矩阵的值,输出不是最终结果
解决方案
您没有将结果“沿轨道返回”给backtrack
函数的原始调用。(结果意味着数独已解决。)您的print
作品,因为您恰好到达那条线一次:当您的for
循环在没有零之后完成时。但是,解决问题并不止于此,您的backtrack
呼叫“树”还在继续。您可以通过查看来验证这一点table
:在某些时候它已被完全解决(没有留下零),但如果您在最后打印它,那里将再次出现零。
通过以下更改,您的函数要么返回None
(就像你之前所做的那样,我只是添加了None
for 显式性),要么在sudoku
. 在for
循环内部,result
存储调用的结果,backtrack
我们可以测试结果是None
(并且我们必须继续解决)或者我们已经完成并且可以返回result
(或者到上一个backtrack
调用,或者到外部的原始调用功能)。
def backtrack(sudoku):
"""solve the game with the backtracking method"""
for r in range(9):
for c in range(9):
list_of_possible = find_possible(sudoku, r, c)
if sudoku[r, c] == 0:
for i in range(len(list_of_possible)):
sudoku[r, c] = list_of_possible[i]
result = backtrack(sudoku)
if result is not None:
return result
sudoku[r, c] = 0
return None
return sudoku
顺便说一句,result
名称只是对与 . 相同对象的另一个引用sudoku
。我认为这可能有助于了解正在发生的事情,但您并不真正需要它:
def backtrack(sudoku):
"""solve the game with the backtracking method"""
for r in range(9):
for c in range(9):
list_of_possible = find_possible(sudoku, r, c)
if sudoku[r, c] == 0:
for i in range(len(list_of_possible)):
sudoku[r, c] = list_of_possible[i]
if backtrack(sudoku) is not None:
return sudoku
sudoku[r, c] = 0
return None
return sudoku
此外,尝试开始使用 Pylint 或 flake8 之类的 linter,它会稍微分析您的代码以进行一些改进。例如,在 Python 中,而不是
for i in range(len(list_of_possible)):
你可以写
for possible in list_of_possible:
推荐阅读
- python - TypeError:字符串格式化期间并非所有参数都转换 - sqlite
- linux - 如何检查是否在 CSH 中设置了环境变量?
- html - Png变成意想不到的字符串
- php - m-Pesa STKPush 请求抛出错误“更新失败9”
- java - 如何通过移动电话进行更改
- python - self.driver.set_network_connection(1) 不适用于 selenium-python-client 的 android OS 版本 8
- python - 如何添加 matplotlib 轴单元
- node.js - pm2 中 GET 的可疑问题
- angular - 将查询字符串附加到 Angular 中的页面 url(没有 JQUERY)
- firebase - AngularFire(angular 8)存储——上传文档