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

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

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) &lt; 9:
        row = list(input(&#39;Row: &#39;))
        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) --&gt; yield solution
# solve(...) --&gt; 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 &gt;= N:
        has_N_solutions = True
        break
else:
    # else = no break
    has_N_solutions = False

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

发表评论

匿名网友

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

确定