需要数独解算器 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

与我的原始代码不同的是，我在我的 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 从递归调用中调用，改变 next_empty_pos。结果是，当您在递归调用 returns 之后访问这些值时，它们已经更改。这就是为什么这两个版本的行为不同。

需要数独解算器 Python 算法说明

Sudoku solver Python algorithm clarification needed

python

sudoku

backtracking