英文:
How to stop a recursive function from executing at a certain point in Python
问题
根据您提供的代码,您想要的是在找到多于一个解决方案时停止solve
函数,并通知用户。您可以通过以下方式修改代码来实现这一目标:
solution_count = 0 # 用于计数解决方案的全局变量
def solve():
global grid
global solution_count # 引用全局变量
for y in range(9):
for x in range(9):
if grid[y][x] == 0:
for n in range(1, 10):
if possible(x, y, n):
grid[y][x] = n
solve()
grid[y][x] = 0
# 检查是否已经找到多于一个解决方案
if solution_count > 1:
return
return
# 当找到一个解决方案时,增加解决方案计数
solution_count += 1
# 当找到多于一个解决方案时,停止递归
if solution_count > 1:
return
print(grid)
solve()
# 最后检查解决方案计数并通知用户
if solution_count == 1:
print("There is only one solution.")
elif solution_count > 1:
print("There are multiple solutions.")
else:
print("No solution found.")
这个修改后的代码将在找到多于一个解决方案时停止递归,并根据解决方案计数向用户报告结果。如果只有一个解决方案,它会打印出 "There is only one solution.",如果有多于一个解决方案,它会打印出 "There are multiple solutions.",如果没有找到解决方案,它会打印出 "No solution found."。
英文:
Following this code, I'm trying to write a piece to find out if a sudoku has one or more than one solutions (we can safely assume that there is at least one solution for sure). This is the code:
grid = []
while True:
row = list(input('Row: '))
ints = []
for n in row:
ints.append(int(n))
grid.append(ints)
if len(grid) == 9:
break
def possible(x, y, n):
for i in range(0, 9):
if grid[i][x] == n and i != y: # Checks for number (n) in X columns
return False
for i in range(0, 9):
if grid[y][i] == n and i != x: # Checks for number (n) in X columns
return False
x0 = (x // 3) * 3
y0 = (y // 3) * 3
for X in range(x0, x0 + 3):
for Y in range(y0, y0 + 3): # Checks for numbers in box(no matter the position, it finds the corner)
if grid[Y][X] == n:
return False
return True
def solve():
global grid
for y in range(9):
for x in range(9):
if grid[y][x] == 0:
for n in range(1, 10):
if possible(x, y, n):
grid[y][x] = n
solve()
grid[y][x] = 0
return
print(grid)
solve()
The problem is, this code will print out all of the solutions for a given sudoku, even if the puzzle has, say, 100 solutions. I am not interested in that. I just want to know if there is more than one answer or not. So basically, I want the solve
function to stop immediately once more than one solution is found, and inform the user about that. How can I do that? How can I stop the code to go all the way down to the very last solution?
答案1
得分: 1
使用一个表示你感兴趣的结果数量的参数。在你的情况下,你会传递2(它可以是默认值)。还要让函数返回还需要多少个结果。如果在递归调用之后返回的值为0,那么你就知道已经生成了所有所需的结果,并且可以退出(使用0表示不再需要更多结果)。
与此无关,但 grid
不应该是一个全局变量。将你的输入循环改成一个返回网格的函数,并将其作为参数传递给 solve
。
更新的代码:
def inputgrid():
grid = []
while len(grid) < 9:
row = list(input('Row: '))
ints = []
for n in row:
ints.append(int(n))
grid.append(ints)
return grid
def possible(x, y, n):
for i in range(0, 9):
if grid[i][x] == n and i != y: # 检查X列中的数字(n)
return False
for i in range(0, 9):
if grid[y][i] == n and i != x: # 检查X列中的数字(n)
return False
x0 = (x // 3) * 3
y0 = (y // 3) * 3
for X in range(x0, x0 + 3):
for Y in range(y0, y0 + 3): # 检查方块中的数字(无论位置如何,它都会找到角落)
if grid[Y][X] == n:
return False
return True
def solve(grid, count=2):
for y in range(9):
for x in range(9):
if grid[y][x] == 0:
for n in range(1, 10):
if possible(x, y, n):
grid[y][x] = n
count = solve(grid, count)
if count == 0: # 出来这里!
return 0
grid[y][x] = 0
return count
print(grid)
return count - 1
solve(inputgrid(), 2)
英文:
Use a parameter that represents the number of results you are interested in. In your case you would pass 2 (it could be the default).
Also have the function return how many results are still needed.
If after a recursive call the returned value is 0, you know you have produced all required results and can exit (with 0 to indicate no more results are needed).
Unrelated, but grid
should not be a global variable. Make your input loop a function that returns the grid and pass it as argument to solve
.
Updated code:
def inputgrid():
grid = []
while len(grid) < 9:
row = list(input('Row: '))
ints = []
for n in row:
ints.append(int(n))
grid.append(ints)
return grid
def possible(x, y, n):
for i in range(0, 9):
if grid[i][x] == n and i != y: # Checks for number (n) in X columns
return False
for i in range(0, 9):
if grid[y][i] == n and i != x: # Checks for number (n) in X columns
return False
x0 = (x // 3) * 3
y0 = (y // 3) * 3
for X in range(x0, x0 + 3):
for Y in range(y0, y0 + 3): # Checks for numbers in box(no matter the position, it finds the corner)
if grid[Y][X] == n:
return False
return True
def solve(grid, count=2):
for y in range(9):
for x in range(9):
if grid[y][x] == 0:
for n in range(1, 10):
if possible(x, y, n):
grid[y][x] = n
count = solve(grid, count)
if count == 0: # get out of here!
return 0
grid[y][x] = 0
return count
print(grid)
return count - 1
solve(inputgrid(), 2)
答案2
得分: 1
一个递归的 solve
函数可以被重写为一个生成器:
# print(solution) --> yield solution
# solve(...) --> yield from solve(...)
然后收集所有的解决方案:
```python
for s in solve(...):
print(s)
最后,在获得 N
(例如2)个解决方案后中止:
for i, s in enumerate(solve(...), start=1):
print(s)
if i >= N:
has_N_solutions = True
break
else:
# else = no break
has_N_solutions = False
英文:
A recursive solve
function could be rewritten as a generator:
# print(solution) --> yield solution
# solve(...) --> yield from solve(...)
Then to collect all solutions:
for s in solve(...):
print(s)
and finally to abort after N
(e.g. 2) solutions:
for i,s in enumerate(solve(...), start=1):
print(s)
if i >= N:
has_N_solutions = True
break
else:
# else = no break
has_N_solutions = False
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论