Problem porting sudoku solver from C to Python

Question

I recently wrote a sudoku solver in C to practice programming. After completing it I decided to write an equivalent program in Python for a comparison between the languages and more practice and this is where the problem is. It seems to be that a global variable (sudokupossibilities[][][]) I declared outside the while loop isn't available within the loop. I've tried adding print statements for debugging and it seems that it's set correctly (all ones) outside of the while loop, but once it enters the loop, the values are mostly zeros, with a few ones. The only way I've found to fix this is adding a statement after "for k in range(9):" setting it to a one there - which makes the following statement obsolete and slowing the program. Ive included the source code for the Python version below and the C version after it.

#! /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 version:

#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");
        }
    }
}

I'm using Python 3.1 and C99. I'd also appreciate anything to do with the quality of my code (although I know my programs are lacking in functions - I've added them to the C version and plan to add them to the Python version after it's working).

Thanks.

Edit: an unsolved puzzle below.

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

This line does not do what you think:

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

Try this simple program:

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

(And the output of a much-simplified version:)

>>> 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]]]

The elements in your array are not independent; it is an artifact of the * method. When used to clone a list, * gives you references to the list, rather than new copies. Hilarity ensues.