數獨求解器需要Python算法說明

Question

我已經在python中建立了一個數獨求解器回溯算法，只是爲了找出它不起作用。我看了一下互聯網上的例子，發現與我的情況相比，他們所做的只有一件事情不同。我相應地更改了我的代碼，現在我的程序正常工作。

這裏是工作代碼：

sudoku = [] 
next_empty_pos = [0,0] 

# Check if the number is already used in the given row 
def valid_in_row(number,row): 
    for i in range(9): 
     if(sudoku[row][i] == number): 
      return False 
    return True 

# Check if the number is already used in the given column 
def valid_in_col(number,col): 
    for i in range(9): 
     if(sudoku[i][col] == number): 
      return False; 
    return True; 

# Check if the number is already used in the given 3x3 box 
def valid_in_box(number,row,col): 
    # Find where 3x3 row and col starts 
    col_start = col-col%3 
    row_start = row-row%3 
    # Loop through the 3 columns and 3 rows 
    for i in range(3): 
     for z in range(3): 
      if(sudoku[i+row_start][z+col_start] == number): 
       return False 
    return True 

# Check if the position is valid for the given number by checking all three conditions above 
def position_valid(number,row,col): 
    return valid_in_row(number,row) and valid_in_col(number,col) and valid_in_box(number,row,col) 

# Find if there are any empty cells left and assign the next empty cell 
def empty_position_exists(): 
    for row in range(9): 
     for col in range(9): 
      if(sudoku[row][col] == 0): 
       global next_empty_pos 
       next_empty_pos = [row,col] 
       return True 
    return False 

# Solve the sudoku 
def solve_sudoku(): 

    # If there are no more empty cells, we are finished 
    if(not empty_position_exists()): 
     return True 

    row=next_empty_pos[0] 
    col=next_empty_pos[1] 

    # Try numbers from 1 
    for posssible_number in range(1,10): 

     if(position_valid(posssible_number,row,col)): 

      sudoku[row][col] = posssible_number 

      # If the next function call evalutes to true, then this should be true as well 
      if(solve_sudoku()): 
       return True 

      # If the above did not work then, set the number back to 0 (unassgined) 
      sudoku[row][col] = 0 

    # Return false if none of the numbers were good 
    return False 

我原來的代碼不同的是，我經過next_empty_pos[0]和next_empty_pos[1]直接在我solve_sudoku功能，而不是聲明爲外部獨立row和col變量for循環。

我的功能看起來像這樣：

# Solve the sudoku 
def solve_sudoku(): 

    # If there are no more empty cells, we are finished 
    if(not empty_position_exists()): 
     return True 

    # Try numbers from 1 
    for posssible_number in range(1,10): 

     if(position_valid(posssible_number,next_empty_pos[0],next_empty_pos[1])): 

      sudoku[next_empty_pos[0]][next_empty_pos[1]] = posssible_number 

      # If the next function call evalutes to true, then this should be true as well 
      if(solve_sudoku()): 
       return True 

      # If the above did not work then, set the number back to 0 (unassgined) 
      sudoku[next_empty_pos[0]][next_empty_pos[1]] = 0 

    # Return false if none of the numbers were good 
    return False 

有人能解釋爲什麼我的版本是不工作？

在此先感謝。

Answer 1

empty_position_exists變化next_empty_pos。當solve_sudoku遞歸調用自身時，將從遞歸調用中調用empty_position_exists，並更改next_empty_pos。結果是，當你在遞歸調用返回後訪問這些值時，它們已經改變了。這就是爲什麼兩個版本的行爲不同。