将数独求解器从C移植到Python的问题
我最近用C语言写了一个数独求解器，目的是练习编程。完成后，我决定用Python写一个相同的程序，想比较一下这两种语言，并且继续练习。这时候我遇到了问题。看起来我在while循环外面声明的一个全局变量（sudokupossibilities[][][]）在循环里面无法使用。我尝试添加一些打印语句来调试，发现这个变量在while循环外面是正确设置的（全是1），但一进入循环，里面的值大部分变成了0，只有少数是1。我发现唯一能解决这个问题的方法是在“for k in range(9):”后面加一句，把它设置为1，这样就让后面的语句变得多余，还拖慢了程序的运行速度。我在下面附上了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
1 个回答
12
这一行代码并不是你想的那样：
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]]]
你数组里的元素并不是独立的；这是因为使用了*这个方法。当用*来复制一个列表时，它给你的是对这个列表的引用，而不是新的副本。这就会引发一些有趣的情况。