스도쿠 솔버 Python 알고리즘 설명이 필요합니다

Question

저는 스도쿠 솔버 역 추적 알고리즘을 파이썬으로 작성하여 작동하지 않는 것을 확인했습니다. 나는 인터넷에서 예를 쳐다 보았고, 그들이 내 방식과 다르게 행동하고있는 유일한 일이 있다는 것을 알았다. 그에 따라 코드를 변경했고 프로그램이 올바르게 작동합니다.

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 

내 원래의 코드에 차이가 나는 직접 내 solve_sudoku 기능에 next_empty_pos[0] 및 next_empty_pos[1]을 전달하고 이외의 별도의 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이 호출됩니다. 결과적으로 재귀 호출이 반환 된 후에 해당 값에 액세스하면 변경됩니다. 그래서 두 버전이 다르게 작동하는 것입니다.