Menu
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
677
Although it has been established that approximately 5.96 x 1126 final grids exist, a brute force algorithm can be a practical method to solve Sudoku puzzles. A brute force algorithm visits the empty cells in some order, filling in digits sequentially, or backtracking when the number is found to be not valid.
Backtracking algorithm is the fastest algorithm to solve sudoku puzzles, It is by far the fastest compared to the other two methods. Also, let's note that each algorithm was faster with harder problems than with easier problems.
As mentioned before, this application does not need a Backtracking Algorithm, because we don't depend only on random selections for the cells. And when the random strategy is needed, we pick a random value for the "more unfortunate cell", this is, the cell with the shortest set of valid values.
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.
127
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
