Python遞回的區域與全域

我正在研究python中的演算法，并試圖實作python數獨解算器。經過多次嘗試，我決定尋找解決方案，并決定使用這里列出的

我試著玩了一下代碼，并將其修改為接受一個區域變數sudoku，而不是全域變數，然而我的代碼似乎解決了sudoku，然后將已解決的sudoku替換為未解決的sudoku，這可能是由于遞回的修改。

以下是我修改后的代碼：

#Forming the Puzzle Grid。 def form_grid（puzzle_string）。 global網格 print('The Sudoku Problem'/span>) for i in range（0, len（puzzle_string）, 9）。 行 = puzzle_string[i:i 9] temp = [] for block in row: temp.append(int（block）) grid.append(temp) printGrid() 列印網格的函式 #Function to print the grid[/span]。 def printGrid()。 global grid for row in grid: print(row) #Function to check if a digit can be placed in the given block[/span]。 def possible(grid,row, col, digit)。 for i in range（0,9）。 if grid[row][i] == digit: return False for i in range（0,9）。 if grid[i][col] == digit: return False square_row = (row//3)*3。 square_col = (col//3)*3。 for i in range（0,3）。 for j in range（0,3）。 if grid[square_row i][square_col j] == digit: return False return True True def solve（grid）。 for row in range（9）。 for col in range（9）。 if grid[row][col] == 0: for digit in range（1,10）。 if possible(grid, row, col, digit): grid[row][col] = digit 解決(grid) grid[row][col] = 0 #Backtrack stepreturn grid puzzle_string = "004300209005009001070060043006002087190007400050083000600000105003508690042910300" 解決(form_grid(puzzle_string))

不知道如何修改代碼，以接受數獨作為引數，同時回傳正確的結果，我也試著在每個卡中檢查有效性，如：

但這產生了相同的結果

主要的問題是，你把當前單元格總是分配回0，并檢查所有可能的數字，而不管遞回solve的結果。你應該檢查遞回solve是否有效，并決定下一步是什么。

下面是對你的代碼的一個小修正。首先，solve應該回傳bool（即，True或False），因為指向grid的指標保持不變，所以你并不真的需要回傳它。然后你應該使用遞回呼叫來檢查是否找到了一個有效的解決方案。如果沒有，繼續下一個數字，如果你檢查了所有的數字，將0分配回當前單元格，并回傳False。否則（如果找到了有效的解決方案）回傳True.

def solve（grid）。
    for row in range（9）。
        for col in range（9）。
            if grid[row][col] == 0:
                valid = False。
                for digit in range（1, 10）。
                    if possible（grid, row,col,digit）。
                        grid[row][col] = digit
                        if solve(grid):
                            return True[/span
                
                grid[row][col] = 0 #回溯步驟
                return False

    return True

puzzle_string = "004300209005009001070060043006002087190007400050083000600000105003508690042910300"
grid = form_grid(puzzle_string)
printGrid()
解決(grid)
print()
printGrid()

BTW，你的代碼中有一些錯誤，例如與一個全域的grid有關，但沒有在任何地方初始化它。

另外，solve的效率并不高，因為在每個遞回呼叫中，你都在尋找下一個空單元。目前只是一個9X9的網格，所以無論如何都會很快，但是為了普及，或者只是作為一個原則，一個更好的使用遞回呼叫的方法是，solve將接收下一個位置的row和col來檢查。

最后，洗掉全域網格并直接從form_grid函式中回傳可能會更好。同樣的，printGrid也應該獲得網格的列印。下面是一個經過上述修改的版本：

#Forming the Puzzle Grid。 def form_grid（puzzle_string）。 grid = [] print('The Sudoku Problem'/span>) for i in range（0, len（puzzle_string）, 9）。 行 = puzzle_string[i:i 9] temp = [] for block in row: temp.append(int（block）) grid.append(temp) return grid #Function to print the grid[/span]。 def printGrid（grid）。 for row in grid: print(row) print() #Function to check if a digit can be placed in the given block。 def possible（grid, row, col, digit）。 for i in range（0, 9）。 if grid[row][i] == digit: return False for i in range（0, 9）。 if grid[i][col] == digit: return False square_row = (row // 3) * 3 square_col = (col // 3) * 3 for i in range（0, 3）。 for j in range（0, 3）。 if grid[square_row i][square_col j] == digit: return False return True True def get_next_position（current_row, current_col）。 if current_col == 8: if current_row == 8: return None, None. return current_row 1, 0. return current_row, current_col 1. def solve（grid, row, col）。 if row is None: next_row, next_col = get_next_position(row, col) if grid[row][col] != 0: return solve(grid, next_row, next_col) for digit in range（1, 10）。 if possible（grid, row, col, digit）。 grid[row][col] = digit if solve(grid, next_row, next_col): return True[/span grid[row][col] =0 return False puzzle_string = "004300209005009001070060043006002087190007400050083000600000105003508690042910300" grid = form_grid(puzzle_string) print("Initial grid"/span>) printGrid(grid) is_solved = solve(grid, 0, 0) print(f "Solved: {is_solved}") print("Solved grid"/span>) printGrid(grid)

uj5u.com熱心網友回復：

你可以采取以下步驟：

class Sudoku。
    def __init__(self, puzzle_string):
        self.grid = [
            list(map(int, puzzle_string[i:i 9] )
            for i in range（0, len（puzzle_string）, 9)
        ]    

    #Function to print the grid。
    def printGrid（self）。
        for row in self.grid。
            print(row)

    #Function to check if a digit can be placed in the given block[/span]。
    def possible（self, row, col, digit）。
        if digit in self.grid[row] 。
            return False False
        for i in range（0,9）。
            if self.grid[i][col] == digit:
                return False 
        square_row = (row//3)*3。
        square_col = (col//3)*3。
        for i in range（0,3）。
            for j in range（0,3）。
                if self.grid[square_row i][square_col j] == digit:
                    return False[/span
        return True True

    def solve（self）。
        for row in range（9）。
            for col in range（9）。
                if self.grid[row][col] == 0:
                    for digit in range（1,10）。
                        if self.possible(row, col, digit):
                            self.grid[row][col] = digit
                            if self.solve():
                                return True[/span]。
                            self.grid[row][col] = 0 # Backtrack step
                    return False
        return True

puzzle_string = "004300209005009001070060043006002087190007400050083000600000105003508690042910300"
謎題 = Sudoku(puzzle_string)
print('The Sudoku Problem: ')
puzzle.printGrid()
謎題決議()
if puzzle.solve():
    print("Solved:")
    puzzle.printGrid()
else:
    print("對不起，沒有找到解決方案")