数独求解器需要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。结果是，当你在递归调用返回后访问这些值时，它们已经改变了。这就是为什么两个版本的行为不同。