Solveur Sudoku Clarification de l'algorithme Python nécessaire

Question

J'ai construit un algorithme de retour arrière de solveur de sudoku en python juste pour découvrir qu'il ne fonctionne pas. J'ai regardé des exemples sur internet et j'ai vu qu'il n'y a qu'une seule chose qu'ils font différemment, par rapport au mien. J'ai changé mon code en conséquence et mon programme fonctionne maintenant très bien.

Voici le code de travail:

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 

La différence à mon code d'origine a été que je passe next_empty_pos[0] et next_empty_pos[1] directement dans ma fonction solve_sudoku et non les déclarant séparés row et col variables extérieures de la boucle for.

Ma fonction ressemblait à ceci:

# 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 

Quelqu'un pourrait-il expliquer pourquoi ma version ne fonctionnait pas?

Merci d'avance.

Answer 1

empty_position_exists changements next_empty_pos. Lorsque solve_sudoku s'appelle récursivement, empty_position_exists est appelée à partir de l'appel récursif, en changeant next_empty_pos. Le résultat est que lorsque vous accédez à ces valeurs après le retour de l'appel récursif, elles ont changé. C'est pourquoi les deux versions se comportent différemment.