如何在Python中在特定点停止递归函数的执行

huangapple
go评论117阅读模式
英文:

How to stop a recursive function from executing at a certain point in Python

问题

根据您提供的代码，您想要的是在找到多于一个解决方案时停止solve函数，并通知用户。您可以通过以下方式修改代码来实现这一目标：

  1. solution_count = 0  # 用于计数解决方案的全局变量
  3. def solve():
  4.     global grid
  5.     global solution_count  # 引用全局变量
  7.     for y in range(9):
  8.         for x in range(9):
  9.             if grid[y][x] == 0:
  10.                 for n in range(1, 10):
  11.                     if possible(x, y, n):
  12.                         grid[y][x] = n
  13.                         solve()
  14.                         grid[y][x] = 0
  16.                         # 检查是否已经找到多于一个解决方案
  17.                         if solution_count > 1:
  18.                             return
  20.                 return
  22.     # 当找到一个解决方案时，增加解决方案计数
  23.     solution_count += 1
  25.     # 当找到多于一个解决方案时，停止递归
  26.     if solution_count > 1:
  27.         return
  29.     print(grid)
  31. solve()
  33. # 最后检查解决方案计数并通知用户
  34. if solution_count == 1:
  35.     print("There is only one solution.")
  36. elif solution_count > 1:
  37.     print("There are multiple solutions.")
  38. else:
  39.     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:

  1. grid = []
  2. while True:
  3.     row = list(input('Row: '))
  4.     ints = []
  6.     for n in row:
  7.         ints.append(int(n))
  8.     grid.append(ints)
  10.     if len(grid) == 9:
  11.         break
  14. def possible(x, y, n):
  15.     for i in range(0, 9):
  16.         if grid[i][x] == n and i != y: # Checks for number (n) in X columns
  17.             return False
  19.     for i in range(0, 9):
  20.         if grid[y][i] == n and i != x: # Checks for number (n) in X columns
  21.             return False
  23.     x0 = (x // 3) * 3
  24.     y0 = (y // 3) * 3
  25.     for X in range(x0, x0 + 3):
  26.         for Y in range(y0, y0 + 3):  # Checks for numbers in box(no matter the position, it finds the corner)
  27.             if grid[Y][X] == n:
  28.                 return False    
  29.     return True
  32. def solve():
  33.     global grid
  34.     for y in range(9):
  35.         for x in range(9):
  36.             if grid[y][x] == 0:
  37.                 for n in range(1, 10):
  38.                     if possible(x, y, n):
  39.                         grid[y][x] = n
  40.                         solve()
  41.                         grid[y][x] = 0
  42.                 return
  43.     print(grid)
  46. 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。

更新的代码：

  1. def inputgrid():
  2.     grid = []
  3.     while len(grid) < 9:
  4.         row = list(input('Row: '))
  5.         ints = []
  6.     
  7.         for n in row:
  8.             ints.append(int(n))
  9.         grid.append(ints)
  10.     return grid
  12. def possible(x, y, n):
  13.     for i in range(0, 9):
  14.         if grid[i][x] == n and i != y: # 检查X列中的数字（n）
  15.             return False
  17.     for i in range(0, 9):
  18.         if grid[y][i] == n and i != x: # 检查X列中的数字（n）
  19.             return False
  21.     x0 = (x // 3) * 3
  22.     y0 = (y // 3) * 3
  23.     for X in range(x0, x0 + 3):
  24.         for Y in range(y0, y0 + 3):  # 检查方块中的数字（无论位置如何，它都会找到角落）
  25.             if grid[Y][X] == n:
  26.                 return False    
  27.     return True
  29. def solve(grid, count=2):
  30.     for y in range(9):
  31.         for x in range(9):
  32.             if grid[y][x] == 0:
  33.                 for n in range(1, 10):
  34.                     if possible(x, y, n):
  35.                         grid[y][x] = n
  36.                         count = solve(grid, count)
  37.                         if count == 0:  # 出来这里！
  38.                             return 0
  39.                         grid[y][x] = 0
  40.                 return count
  41.     print(grid)
  42.     return count - 1
  44. 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:

  1. def inputgrid():
  2.     grid = []
  3.     while len(grid) &lt; 9:
  4.         row = list(input(&#39;Row: &#39;))
  5.         ints = []
  6.     
  7.         for n in row:
  8.             ints.append(int(n))
  9.         grid.append(ints)
  10.     return grid
  12. def possible(x, y, n):
  13.     for i in range(0, 9):
  14.         if grid[i][x] == n and i != y: # Checks for number (n) in X columns
  15.             return False
  17.     for i in range(0, 9):
  18.         if grid[y][i] == n and i != x: # Checks for number (n) in X columns
  19.             return False
  21.     x0 = (x // 3) * 3
  22.     y0 = (y // 3) * 3
  23.     for X in range(x0, x0 + 3):
  24.         for Y in range(y0, y0 + 3):  # Checks for numbers in box(no matter the position, it finds the corner)
  25.             if grid[Y][X] == n:
  26.                 return False    
  27.     return True
  30. def solve(grid, count=2):
  31.     for y in range(9):
  32.         for x in range(9):
  33.             if grid[y][x] == 0:
  34.                 for n in range(1, 10):
  35.                     if possible(x, y, n):
  36.                         grid[y][x] = n
  37.                         count = solve(grid, count)
  38.                         if count == 0:  # get out of here!
  39.                             return 0
  40.                         grid[y][x] = 0
  41.                 return count
  42.     print(grid)
  43.     return count - 1
  45. solve(inputgrid(), 2)

答案2

得分: 1

一个递归的 solve 函数可以被重写为一个生成器：

  1. # print(solution) --> yield solution
  2. # solve(...) --> yield from solve(...)
  4. 然后收集所有的解决方案：
  6. ```python
  7. for s in solve(...):
  8.     print(s)

最后，在获得 N（例如2）个解决方案后中止：

  1. for i, s in enumerate(solve(...), start=1):
  2.     print(s)
  3.     if i >= N:
  4.         has_N_solutions = True
  5.         break
  6. else:
  7.     # else = no break
  8.     has_N_solutions = False
英文:

A recursive solve function could be rewritten as a generator:

  1. # print(solution) --&gt; yield solution
  2. # solve(...) --&gt; yield from solve(...)

Then to collect all solutions:

  1. for s in solve(...):
  2.     print(s)

and finally to abort after N (e.g. 2) solutions:

  1. for i,s in enumerate(solve(...), start=1):
  2.     print(s)
  3.     if i &gt;= N:
  4.         has_N_solutions = True
  5.         break
  6. else:
  7.     # else = no break
  8.     has_N_solutions = False

huangapple
  • 本文由 发表于 2023年6月19日 11:27:53
  • 转载请务必保留本文链接：https://go.coder-hub.com/76503446.html
  • backtracking
  • python
  • recursion
  • sudoku
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定