将数独求解器从 C 移植到 Python 时出现问题

Question

我最近用 C 语言编写了一个数独求解器来练习编程。完成后，我决定用 Python 编写一个等效程序，以进行语言之间的比较和更多实践，这就是问题所在。似乎我在 while 循环外部声明的全局变量 (sudokupossibilities[][][]) 在循环内不可用。我尝试添加 print 语句进行调试，似乎它在 while 循环之外设置正确（全部），但是一旦进入循环，值大部分为零，有一些为 1。我发现解决这个问题的唯一方法是在“for k in range(9):”之后添加一条语句，将其设置为一个 - 这使得以下语句过时并减慢程序速度。我已经包含了下面的 Python 版本和其后的 C 版本的源代码。

#! /usr/bin/python3.1    

sudoku = [[0] * 9] * 9
sudokupossibilities = [[[1] * 9] * 9] * 9
completion = 0

#Input a set of values, storing them in the list "sudoku".
print("Input sudoku, using spaces to separate individual values and return \
to separate lines.")
for i in range(9):
    string = input()
    values = string.split(" ")
    sudoku[i] = [int(y) for y in values]

for i in range(9):
    for j in range(9):
        for k in range(9):
            print(i+1, j+1, k+1, "=", sudokupossibilities[i][j][k])

#Solve the puzzle.
while True:
    for i in range(9):
        for j in range(9):
            #If the number is already known, go to the next.
            if sudoku[i][j] != 0:
                continue
            #Check which values are possible.
            for k in range(9):
                #If the value is already eliminated, skip it.
                if sudokupossibilities[i][j][k] == 0:
                    continue
                print(i+1, j+1, k+1, "=", sudokupossibilities[i][j][k])
                #If it overlaps horizontally, eliminate that possibility.
                for l in range(9):
                    if ((sudoku[i][l]) == (k + 1)) & (l != j):
                        sudokupossibilities[i][j][k] = 0
                #If it overlaps vertically, eliminate that possibility.
                for l in range(9):
                    if ((sudoku[l][j]) == (k + 1)) & (l != i):
                        sudokupossibilities[i][j][k] = 0
                #If it overlaps in the same 3x3 box, set to 0.
                x = 0
                y = 0
                #Find which box it's in on the x axis.
                for m in [0, 3, 6]:
                    for n in range(3):
                        if (m + n) == i:
                            x = m
                #Find which box it's in on the y axis.
                for m in [0, 3, 6]:
                    for n in range(3):
                        if (m + n) == j:
                            y = m
                #Check for overlap.
                for m in range(3):
                    for n in range(3):
                        if (sudoku[x+m][y+n] == (k + 1)) & ((x+m) != i) & ((y+n) != j):
                            sudokupossibilities[i][j][k] = 0
            #Count the values possible for the square. If only one is possible, set it.
            valuespossible = 0
            valuetoset = 0
            for l in range(9):
                if sudokupossibilities[i][j][l] == 1:
                    valuespossible += 1
                    valuetoset = l + 1
            if valuespossible == 1:
                sudoku[i][j] = valuetoset
    #Count the unsolved squares, if this is zero, the puzzle is solved.
    completion = 0
    for x in sudoku:
        for y in x:
            if y == 0:
                completion += 1
    if completion == 0:
        break
    else:
        print(completion)
        continue
#Print the array.
for x in sudoku:
    for y in x:
        print(y, end=" ")
    print(end="\n")

C版本：

#include <stdio.h>

int main() {
    int sudoku[9][9];
    int sudokupossibilities[9][9][9];
    int completion = 0;
    int valuespossible = 0;
    int valuetoset = 0;
    int x = 0;
    int y = 0;

    //Set sudoku to all zeros.
    for (int i = 0; i <= 8; i++) {
        for (int j = 0; j <= 8; j++) {
            sudoku[i][j] = 0;
        }
    }
    //Set sudokupossibilities to all ones.
    for (int i = 0; i <= 8; i++) {
        for (int j = 0; j <= 8; j++) {
            for (int k = 0; k <= 8; k++) {
                sudokupossibilities[i][j][k] = 1;
            }
        }
    }
    //Take an unsolved puzzle as input.
    printf("Please input unsolved sudoku with spaces between each number, pressing enter after each line. Use zeros for unknowns.\n");
    for (int i = 0; i <= 8; i++) {
        scanf("%d %d %d %d %d %d %d %d %d", &sudoku[i][0], &sudoku[i][1],
        &sudoku[i][2], &sudoku[i][3], &sudoku[i][4], &sudoku[i][5],
        &sudoku[i][6], &sudoku[i][7], &sudoku[i][8]);
    }

    //Solve the puzzle.
    while (1) {
        for (int i = 0; i <= 8; i++) {
            for (int j = 0; j <= 8; j++) {
                //If the number is already known, go to the next.
                if (sudoku[i][j] != 0) {
                    continue;
                }
                //Check which values are possible.
                for (int k = 0; k <= 8; k++) {
                    //If it's already eliminated, it doesn't need to be checked.
                    if (sudokupossibilities[i][j][k] == 0) {
                        continue;
                    }
                    //If it overlaps horizontally, eliminate that possibility.
                    for (int l = 0; l <= 8; l++) {
                        if ((sudoku[i][l] == (k + 1)) && (l != j)) {
                            sudokupossibilities[i][j][k] = 0;
                        }
                    }
                    //If it overlaps vertically, eliminate that possibility.
                    for (int l = 0; l <= 8; l++) {
                        if ((sudoku[l][j] == (k + 1)) && (l != i)) {
                            sudokupossibilities[i][j][k] = 0;
                        }
                    }
                    //If it overlaps in the same 3x3 box, set to 0.
                    x = 0;
                    y = 0;
                    for (int m = 0; m <= 6; m += 3) {
                        for (int n = 0; n <= 2; n++) {
                            if ((m + n) == i) {
                                x = m;
                            }
                        }
                    }
                    for (int m = 0; m <= 6; m += 3) {
                        for (int n = 0; n <= 2; n++) {
                            if ((m + n) == j) {
                                y = m;
                            }
                        }
                    }
                    for (int m = 0; m <= 2; m++) {
                        for (int n = 0; n <= 2; n++) {
                            if ((sudoku[x+m][y+n] == (k + 1)) && ((x+m) != i) && ((y+n) != j)) {
                                sudokupossibilities[i][j][k] = 0;
                            }
                        }
                    }
                }
                //Count the values possible for the square. If only
                //one is possible, set it.
                valuespossible = 0;
                valuetoset = 0;
                for (int l = 0; l <= 8; l++) {
                    if (sudokupossibilities[i][j][l] == 1) {
                        valuespossible++;
                        valuetoset = l + 1;
                    }
                }
                if (valuespossible == 1) {
                    sudoku[i][j] = valuetoset;
                }
            }
        }
        //Count the unsolved squares, if this is zero, the puzzle is solved.
        completion = 0;
        for (int i = 0; i <= 8; i++) {
            for (int j = 0; j <= 8; j++) {
                if (sudoku[i][j] == 0) {
                    completion++;
                }
            }
        }
        if (completion == 0) {
            break;
        }
        else {
            continue;
        }
    }
    //Print the completed puzzle.
    printf("+-------+-------+-------+\n");
    for (int i = 0; i <= 8; i++) {
        for (int j = 0; j <= 8; j++) {
            if (j == 0) {
                printf("| ");
            }
            printf("%d ", sudoku[i][j]);
            if ((j == 2) || (j == 5)) {
                printf("| ");
            }
            if (j == 8) {
                printf("|");
            }
        }
        printf("\n");
        if (((i + 1) % 3) == 0) {
            printf("+-------+-------+-------+\n");
        }
    }
}

我使用Python 3.1和C99。 我也很感激与我的代码质量有关的任何事情（尽管我知道我的程序缺乏功能 - 我已将它们添加到 C 版本，并计划在运行后将它们添加到 Python 版本）。

谢谢。

编辑：下面有一个未解决的难题。

0 1 0 9 0 0 0 8 7
0 0 0 2 0 0 0 0 6
0 0 0 0 0 3 2 1 0
0 0 1 0 4 5 0 0 0
0 0 2 1 0 8 9 0 0
0 0 0 3 2 0 6 0 0
0 9 3 8 0 0 0 0 0
7 0 0 0 0 1 0 0 0
5 8 0 0 0 6 0 9 0

Answer 1

这行代码并不符合您的想法：

sudokupossibilities = [[[1] * 9] * 9] * 9

尝试这个简单的程序：（

sudokupossibilities = [[[1] * 9] * 9] * 9
sudokupossibilities
sudokupossibilities[1][1][1]=2
sudokupossibilities

以及简化版本的输出：）

>>> s=[[[1] * 3] * 3] * 3
>>> s
[[[1, 1, 1], [1, 1, 1], [1, 1, 1]], [[1, 1, 1], [1, 1, 1], [1, 1, 1]], [[1, 1, 1], [1, 1, 1], [1, 1, 1]]]
>>> s[1][1][1]=2
>>> s
[[[1, 2, 1], [1, 2, 1], [1, 2, 1]], [[1, 2, 1], [1, 2, 1], [1, 2, 1]], [[1, 2, 1], [1, 2, 1], [1, 2, 1]]]

数组中的元素不是独立的；它是 * 方法的产物。当用于克隆列表时，* 为您提供对列表的引用，而不是新的副本。欢闹随之而来。