# Sudoku solver

• 12-13-2009
M-S-H
Need Help understanding a Sudoku solver
So I found this sudoku solver and I understand the basics, but there are a few things that I quite dont understand, and was wondering if anyone could help.

Code:

```#include <stdio.h>   int grid[9][9];   void print_solution(void) {   static int nsol = 0;   int r, c;     printf("----- solution %d -----\n", ++nsol);   for (r = 0; r < 9; r++)   {     for (c = 0; c < 9; c++)     {       printf("%d", grid[r][c]);       if (c % 3 == 2) printf("  ");     }     printf("\n");     if (r % 3 == 2) printf("\n");   }   }   int safe(int row, int col, int n) {   int r, c, br, bc;     if (grid[row][col] == n) return 1;   if (grid[row][col] != 0) return 0;   for (c = 0; c < 9; c++)     if (grid[row][c] == n) return 0;   for (r = 0; r < 9; r++)     if (grid[r][col] == n) return 0;   br = row / 3;   bc = col / 3;   for (r = br * 3; r < (br + 1) * 3; r++)     for (c = bc * 3; c < (bc + 1) * 3; c++)       if (grid[r][c] == n) return 0;     return 1; }   void solve(int row, int col) {   int n, t;     if (row == 9)     print_solution();   else     for (n = 1; n <= 9; n++)       if (safe(row, col, n)) {         t = grid[row][col];         grid[row][col] = n;         if (col == 8)           solve(row + 1, 0);         else           solve(row, col + 1);           grid[row][col] = t;       } }   int main() {   int i, j;     printf("enter the sudoku: \n");   for(i=0;i<9;i++)     for(j=0;j<9;j++)     {       printf("(%d, %d): ", i+1, j+1);       scanf("%d", &grid[i][j]);     }   solve(0,0);   return 0; }```
What I do understand is that it goes to each empty square and assigns a 1, and checks to see if it works. If it does, it'll assign 1 to the square, if it doesnt it will continue to 2 until it finds a number that works.

One thing I dont understand is how this is able to give multiple solutions. After it solves a puzzle once, how does it loop back to solve it again.

I also dont understand how "t" is used in the solve function. I think it has something to do with going back to a previous cell if the program comes to a cell in which no number would work, and if "t" doesnt work that way, then i dont know how the program goes back to a previous square.

Thanks for the help.
• 12-13-2009
You think it might?

You *THINK* it might?

Holy crap! Add a print statement and find out!!

Man these posters aren't LAZY. They're damn near *INERT*!!

I love having you on the forum, but Key-rist, where's your sense of exploration, here?

P.S. Watch out for those barnacles - they really like attaching to stationary objects. :)

It's a wonderfully concise brute force solver! Study it!
• 12-13-2009
M-S-H
LOL,
in my defense, ive only been programming for a month or two
I did add a print statement, but that cause the program to not work. It would print values of t, but it wouldn't print the solution...

I also tried to follow program, and I understand that it will go back and change values...i worked part of a sudoku by and hand using the program's logic, but i still couldn't follow how it actually goes back...and how it will start finding another solution (if there is one) after it solves it once...

So i wouldnt mind some hints if you dont want to give me answers lol
• 12-13-2009
jeffcobb
Code deconstruction
If it were me trying to pick this code apart I would single step through it with a source debugger (Visual Studio on windows, GDB (preferably something like DDD) on Linux. As you step through and watch the code execute, inspect the variables, including your elusive 't' var. You can learn volumes about code this way....often code paths execute far differently than your assumptions ;)

I am not trying to evade your question, just trying to supply tools to you to make the journey easier if you are just starting out...try this and see if you are not muttering "A-Ha!" within a few minutes....

^__^

Another alternative to your printf() approach to seeing what is going on, try creating a log file and writing variable states to that at various points....

Jeff
• 12-13-2009
jeffcobb
One other thing I would add to the above is that if it were me and I were to be deconstructing this, I would save the starting sodoku data to a data file and read it that way. The way the app is constructed, you have to hand-enter it every time which can lead to mistakes.. If you replace that initial loop that reads the values from the keyboard with a simple file-load, this will make your path easier....

Jeff
• 12-13-2009
MSH, I am adding the features that Jeff mentioned, right now. Also, I'm adding some hard puzzles, so they can be chosen from inside the program, itself.

Several other features as well.

I'll post this up tomorrow.
• 12-14-2009
iMalc
That might be simple but it looks like a pretty slow solver. How long does it take?

It also looks like it would take a while to exit after printing the solution because the recursive calls don't return whether the solution was found. So it would continue to search the rest of the search space for quite a while longer after finding the solution. That's quite a large oversight on someone's part.
• 12-14-2009
Quote:

Originally Posted by iMalc
That might be simple but it looks like a pretty slow solver. How long does it take?

It also looks like it would take a while to exit after printing the solution because the recursive calls don't return whether the solution was found. So it would continue to search the rest of the search space for quite a while longer after finding the solution. That's quite a large oversight on someone's part.

It's fast. I fed it four of my toughest (for computers), and it solved all four in just a few seconds. The only one that took more than 4 seconds (maybe 7, I didn't put a timer on it yet), was the "brute force nightmare" puzzle from Wikipedia.

In it's current form, it shows all solutions, which is a nice option. I hate it when I work through a puzzle only to find out the solution the paper gives, is just one of the many solutions that are valid. Puzzles with more than one solution, are NOT valid sudoku puzzles, in the opinion of many Sudoku fans.

I'll set it up with an option to the run the "Top 1465" puzzles, and get a time on that, and maybe the 50,000 "17's", as well.

It isn't the fastest solver I've seen, but it is quick. If you could add some expertise to speed it up, that would be great, iMalc. I have solve times for the well known 5 fastest solvers on the Sudoku Programmers Forum - but this program won't be in that category.
• 12-15-2009
This is an improved version of this brute force solver. No changes were made to the solving functions, themselves. Some features were added, but nothing except the faintest testing has been done with it.

Code:

```/* SudokuEZ.c - a concise sudoku brute force program, Author unknown. status: na This program was written using Turbo C. Users of newer compilers should: 1) include the windows.h file line, if you don't have conio.h 2) include the define gotoxy file line 3) change CLK_TCK to TICKS_PER_SEC All users should know that this program has not been tested, beyond a a very low level. We're just experimenting with it, at this time. */ //#include <windows.h>    //for older compilers, don't include this line //#define gotoxy Gotoxy    // "    "    "        "      "    "    " #include <stdio.h> #include <conio.h> #include <time.h>   int grid[9][9]; int benchmark(FILE *); void Gotoxy(int x, int y); void load(void); void printIt(void); void print_solution(void); int safe(int row, int col, int n); void solve(int row, int col, int format); /* format == 0, show solutions, format == 1, don't show solutions */ int benchmark(FILE* fp) {   clock_t start, stop;   int c, r, temp;   unsigned long puzzNum = 0;   if((fp = fopen("Top150.txt", "rt")) == NULL) {     perror("\n Error opening Top150.txt file - terminating program ");     return 1;   }   start = clock();   temp = 0;   while(temp != EOF) {     for(r = 0; r < 9; r++) {       for(c = 0; c < 9; c++) {         temp = fgetc(fp);         if(temp == '.') temp = 0;         else           temp = temp - '0';         grid[r][c] = temp;       }     }     temp = fgetc(fp); //pulls off the newline     if(temp == EOF) continue;     printIt();     gotoxy(1,16);     printf("  Working on puzzle number: %ld", ++puzzNum);     //if(puzzNum > 100) break;         //getch(); getch();     solve(0,0,1);   }   stop = clock();   gotoxy(1, 18);   //newer compiler? replace CLK_TCK with TICKS_PER_SEC   printf("  Elapsed time was: %.2f seconds", (stop-start)/CLK_TCK);   printf("\n\n\t\t    Benchmark complete - press enter when ready");        while((temp = getchar()) != '\n');   temp = getchar();   fclose(fp);   return 0; } /* Include this function, for newer compilers void Gotoxy(int x, int y) {   COORD coord;   coord.X = x;   coord.Y = y;   SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), coord); } */ int main() {   FILE *fp;   int i, j;   char ch;   for(i=0; i< 10; i++)     printf("\n\n\n\n\n");   do {     for(i=3; i< 21; i++) {       gotoxy(1,i);       printf("                                                                    ");      }     gotoxy(1,3);     printf("\t\t        Welcome to Sudoku Solver's Main Menu\n\n");     printf("    *press 'b' to benchmark this program\n\n");     printf("    *press 'l' to load a puzzle from this program\n\n");     printf("    *press 'e' to enter your own puzzle, or 'q' to quit [b/l/e/q]: ");     for(i=0; i < 9; i++) {       for(j = 0; j < 9; j++) {         grid[i][j] = 0;       }     }     ch=getchar();     if(ch == 'q') break;     for(i=3; i< 10; i++) {       gotoxy(1,i);       printf("                                                                    ");      }     if(ch == 'b') {       gotoxy(1,2);       printf("\t\t      Sudoku is Running a Benchmark Suite of Puzzles");       j = benchmark(fp);                if(j) return 1;     }     else if(ch == 'l')       load();     else if(ch == 'e') {       printf("enter your puzzle: \n");       for(i=0;i<9;i++) {         for(j=0;j<9;j++) {           printf("(%d, %d): ", i+1, j+1);           scanf("%d", &grid[i][j]);         }       }     }     if(ch != 'b') {       printIt();       solve(0,0,0);       gotoxy(1, 22);       printf("\t\t\t        Press enter when ready");       i = getchar();       gotoxy(1,22);       printf("\t\t\t                                    ");     }   }while(ch != 'q');   gotoxy(1, 22);   printf("\t\t    Program complete, press enter when ready");   while((i = getchar()) != '\n');   i = getchar();   return 0; } void load(void) {   int c, gar;     gotoxy(1,6);         printf("  There are four very hard puzzles. Choose 1, 2, 3 or 4: ");         scanf("%d", &c);         gar = getchar();   gotoxy(1,6);   printf("                                                          ");         if(c == 1)        {                         /*sudoku17.txt Game 9 Tough!.*/                         /*000000012 400090000 000000050 070200000 600000400 000108000                         018000000 000030700 502000000*/                 grid[0][7] = 1; grid[0][8] = 2; grid[1][0] = 4; grid[1][4] = 9; grid[2][7] = 5;                 grid[3][1] = 7; grid[3][3] = 2; grid[4][0] = 6; grid[4][6] = 4; grid[5][3] = 1;                 grid[5][5] = 8; grid[6][1] = 1; grid[6][2] = 8; grid[7][4] = 3; grid[7][6] = 7;                 grid[8][0] = 5; grid[8][2] = 2;         } /*This game ^^ is a great testbed - Very hard. Solution starts with 367 485 912*/         else if(c == 2)        {                         /*VH 2: "near worst case for brute force sudoku solver" - Wikipedia                         My solve time: 0.22 seconds */           grid[1][5] = 3; grid[1][7] = 8; grid[1][8] = 5;                 grid[2][2] = 1; grid[2][4] = 2;                 grid[3][3] = 5; grid[3][5] = 7;                 grid[4][2] = 4; grid[4][6] = 1;                 grid[5][1] = 9;                 grid[6][0] = 5; grid[6][7] = 7; grid[6][8] = 3;                 grid[7][2] = 2; grid[7][4] = 1;                 grid[8][4] = 4; grid[8][8] = 9;         }         else if(c == 3)        {                         /*VH 3: Sudoku17.txt #11 - one of my hardest to solve, Time: 3 seconds                         000000012 700060000 000000050        080200000 600000400 000109000                         019000000 000030800 502000000*/                 grid[0][7] = 1; grid[0][8] = 2;                 grid[1][0] = 7; grid[1][4] = 6;                 grid[2][7] = 5;                 grid[3][1] = 8; grid[3][3] = 2;                 grid[4][0] = 6; grid[4][6] = 4;                 grid[5][3] = 1; grid[5][5] = 9;                 grid[6][1] = 1; grid[6][2] = 9;                 grid[7][4] = 3; grid[7][6] = 8;                 grid[8][0] = 5; grid[8][2] = 2;         }         else if(c == 4)  {     /*VH 4: Sudoku17.txt #619 -     000000071 900000060 020000000 004070000 030000400     000910000 700600008 000300200 100000000 */                  grid[0][7] = 7; grid[0][8] = 1;           grid[1][0] = 9; grid[1][7] = 6;           grid[2][1] = 2;           grid[3][2] = 4; grid[3][4] = 7;           grid[4][1] = 3; grid[4][6] = 4;           grid[5][3] = 9; grid[5][4] = 1;           grid[6][0] = 7; grid[6][3] = 6; grid[6][8] = 8;           grid[7][3] = 3; grid[7][6] = 2;           grid[8][0] = 1;          }         gar++; } void printIt(void) {         int r, c;         gotoxy(2, 3);         for(r = 0; r < 9; r++)        {                 printf("\n  ");                 if(r % 3 == 0 && r > 1)                         printf("=======================\n  ");                 for(c = 0; c < 9; c++) {                         if(c % 3 == 0 && c > 1)                                 printf("|| ");                         if(grid[r][c])        {                                 //textcolor(14);                                 printf("%d ", grid[r][c]);  //was cprintf()                                 //textcolor(15);                         }                         else                                 printf("%d ", grid[r][c]);  //also cprintf()                 }         }   //textcolor(15);         //gar = getchar(); gar++; } void print_solution(void) {   static int nsol = 0;   int r, c;     printf("----- solution %d -----\n", ++nsol);     for (r = 0; r < 9; r++)   {     for (c = 0; c < 9; c++)     {       printf("%d", grid[r][c]);       if (c % 3 == 2) printf("  ");     }     printf("\n");     if (r % 3 == 2) printf("\n");   } } int safe(int row, int col, int n) {   int r, c, br, bc;     if (grid[row][col] == n) return 1;   if (grid[row][col] != 0) return 0;   for (c = 0; c < 9; c++)     if (grid[row][c] == n) return 0;   for (r = 0; r < 9; r++)     if (grid[r][col] == n) return 0;   br = row / 3;   bc = col / 3;   for (r = br * 3; r < (br + 1) * 3; r++)     for (c = bc * 3; c < (bc + 1) * 3; c++)       if (grid[r][c] == n) return 0;     return 1; } void solve(int row, int col, int format) {   int n, t;   unsigned long solNum = 0;   if (row == 9 && !format ) {     printIt();          //static grid printout     //print_solution(); //enables the rolling screen of solutions mode     solNum++;     printf("\n\n  Found %ld Solution%c", solNum, solNum > 1 ? 's': ' ');   }   else {     for (n = 1; n <= 9; n++) {       if (safe(row, col, n)) {               t = grid[row][col];         grid[row][col] = n;               if (col == 8)           solve(row + 1, 0, format);         else           solve(row, col + 1, format);         grid[row][col] = t;       }     }   } }```
Comments regarding "my solver", don't refer to this program. I'll post up the Top150.txt file (used in the benchmark function), in just a bit.

This solver isn't fast enough to bother with the Top 1465 puzzle file. This program FINDS the puzzle solutions rather quickly, but as iMalc noted yesterday, it then has to spend a lot of time (for a computer that is), finishing up.

I've used a small font size to save space:
Code:

``` 4...3.......6..8..........1....5..9..8....6...7.2........1.27..5.3....4.9........ 7.8...3.....2.1...5.........4.....263...8.......1...9..9.6....4....7.5........... 7.8...3.....6.1...5.........4.....263...8.......1...9..9.2....4....7.5........... 3.7.4...........918........4.....7.....16.......25..........38..9....5...2.6..... 5..7..6....38...........2..62.4............917............35.8.4.....1......9.... 4..7..6....38...........2..62.5............917............43.8.5.....1......9.... .4..1.2.......9.7..1..........43.6..8......5....2.....7.5..8......6..3..9........ 7.5.....2...4.1...3.........1.6..4..2...5...........9....37.....8....6...9.....8. ......41.9..3.....3...5.....48..7..........62.1.......6..2....5.7....8......9.... 7.5.....2...4.1...3.........1.6..4..2...5...........9....37.....9....8...8.....6. .8..1......5....3.......4.....6.5.7.89....2.....3.....2.....1.9..67........4..... 8.9...3.....7.1...5.........7.....263...9.......1...4..6.2....4....8.5........... 6.9.....8...7.1...4............6...4.2.....3..3....5...1.5...7.8...9..........2.. ......41.9..3.....3...2.....48..7..........52.1.......5..2....6.7....8......9.... 1...48....5....9....6...3.....57.2..8.3.........9............4167..........2..... 7.8...3.....6.1...4.........6.....253...8.......1...9..9.5....2....7.4........... 4.3.....2...6.1...8...........5..79.2...3.....1..........84.....9....6...7.....5. .1.62....5......43....9....7......8...5.....4...1..........36...9....2..8....7... 4.3.....2...6.1...8...........5..97.2...3.....1..........84.....9....6...7.....5. 8.5.....2...9.1...3.........6.7..4..2...5...........6....38.....1....9...4.....7. ....2..4..7...6....1.5.....2......8....3..7..4.9.........6..1.38...9..........5.. 8.5.....2...9.1...3.........6.7..4..2...5...........6....38.....4....7...1.....9. ....4...1.3.6.....8........1.9..5.........87....2......7....26.5...94.........3.. 3.7..4.2....1..8..9............3..9..5.8......4.6...........5.12...7..........6.. ...9.31..6.7....8.2.........5....4......6..2..1.......8...7.......3..5.....4....9 8.5.....2...4.1...3.........6.7..4..2...5...........9....38.....1....7...9.....6. 7.4.....2...8.1...3.........5.6..1..2...4...........9....37.....9....5...8.....6. 7.4.....2...8.1...3.........5.6..1..2...4...........9....37.....8....6...9.....5. ..1.....7...89..........6..26..3.......5...749...........1.4.5.83.............2.. 2...4.5...1.....3............6...8.2.7.3.9......1.....4...5.6.....7...9...8...... 8.5.....2...9.1...3.........6.7..4..2...5...........6....38.....1....7...4.....9. .8.....63....4.2............1.8.35..7.....9.....6.....2.9.7...........354........ .9.3...2.....7.5...1.......7.86..4.....9.2...5...........1...634...8............. ...9.31..5.7....8.2.........4....6......5..2..1.......8...7.......6..4.....3....9 5.8.....7...9.1...4............5...4.6.....3..9....6...2.3...1.7...8..........2.. .......71.2.8........5.3...7.9.6.......2..8..1.........3...25..6...1..4.......... ......41.6..3.....3...2.....49..8..........52.1.......5..6....7.8....9......3.... 5..6.3....2....98.......1...1..9.......3....67.......4....8.25.4..7.............. ......41.9..3.....3...5.....48..7..........52.1.......6..2....5.7....8......9.... 7.4.....2...8.1...3.........5.6..1..2...4...........5....37.....9....6...8.....9. 4.35...2.....16...7............895.....3..8..2...........4...7..9....6...1....... .5.4.9......6....12.....3..7.3...2.....5...9.1.........68....4.....8........7.... ......41.9..2.....3...5.....48..7..........62.1.......6..5....3.7....8......9.... 5.7....3.....61...1.8......62..4.......7...8...........1....6.43..5...........2.. 7.....48....6.1..........2....3..6.52...8..............53.....1.6.1.........4.7.. 6..1...8..53.............4....8...6..9....7....24.........7.3.9....2.5..1........ ...9.3.5.2.....7............59..1......4..6...43......4..67...........91....2.... .6..5.4.3.2.1...........7..4.3...6..7..5........2.........8..5.6...4...........1. 6.9.....8...3.1...4............6...4.2.....3..7....5...1.5...7.8...9..........2.. 4.3.....2...7.1...9...........5..18.2...3.....8..........94.....7....6...6.....5. 8.5.....2...4.1...3.........6.7..4..2...5...........6....38.....9....7...1.....9. ....3..715..4.2............2..6..4...38.7..............7..8..1.6..5..2........... 4.3.....2...7.1...9...........5..81.2...3.....8..........94.....7....6...6.....5. .......91.7..3....82..........1.5...3.....7.....9.......16...5...4.2....7.....8.. 48.3............71.2.......7.5....6....2..8.............1.76...3.....4......5.... 7.8.2...........913.........46..........3.7.....5......5.9.6......4...1.2.....8.. ..36......4.....8.9.....7..86.4...........1.5.2.......5...17...1...9...........2. 2.8.5.......7...4.3........5...2.9.......1......6......7.1.4.6.......3.2.1....... 8.5.....2...9.1...3.........6.7..4..2...5...........6....38.....4....6...9.....7. 4.35...2.....61...7............895.....3..8..2...........4...7..9....6...1....... ...3.9.7.8..4.....1........2..5..6...3.....4.....1....5.....8......2.1.....7....9 .5.1.8.7.4..3.....2.........1.7...8.9.....4............3.....1.....4.2......5.6.. .....1..8.9....3..2........5......84.7.63.......9.....1.4....5.....7.6.....2..... 85.....7.....41...3..........1...4.6.7.5...........2..742.6.......8...3.......... ..3...67.5.....3...4.......6..3......8......4...7....12......5.....98.......41... .4.3............78.......5.7..65....5...9.....1....2.....1.43..8.......6...2..... ....3...27..4......3.....9..6..2....8.....7........1..4..7.1......6...35.....8... 4.3.....2...6.1...8...........5..79.2...3.....7..........84.....9....6...1.....5. 3..8.1....5....6.9......4..5..7...8..4..6...........2.2..3.........9.1....7...... 4.3.....2...6.1...8...........5..97.2...3.....7..........84.....9....6...1.....5. 4.1.6....3.....2........8..15.2.....6......1....9......2.7.8..........43.7....... 26.7...........4.15........839.........5...6....1......7.....2.....49.......3.8.. 42.....36....3.8...........7.8.1...........54..3.......5.4.6...1.....7.....2..... ...6.37...51...........2.......1..846..7............5.14.58....3.....2........... .6..7.......8...2..1.............6.54..3...........7..2...6..4.8.31.........5.1.. ..1.....8...9..2.......3.......15.4..6....7..3............4..8572.6.....9........ 7.....4...2..7..8...3..8..9...5..3...6..2..9...1..7..6...3..9...3..4..6...9..1..5 5.6...3.....8.1...2.........9..6.7...4.7...........2.....1...493...5...........8. 3.7..4.2....1..5..9............3..9..5.8......4.6...........8.12...7..........6.. ...6..1.....2...4..59......6.......47....9.......5..8....1..7.6.82............3.. 2...6...8.743.........2....62......1...4..5..8...........5..34......1..........7. .......92.37.......4.......8...6.1.......43.......9...2...5...6...1..74....8..... 7.....48....6.1..........2....3..6.52...8..............63.....1.5.1.........4.7.. 56..2......3...9...............7..561......2...84........3.84..71..........9..... ......41.9..3.....3...2.....48..7..........62.1.......5..2....6.7....8......9.... ...6.37...51...........2.......1..546..7............8.14.58....3.....2........... 3..4.1....9....7...........6.41.........7.2.9......5......3..8.52..........8...6. 7...3........5.6....4....9.2.....7.1...9.8......4.....53....2.....1...8..6....... ...3..5...5..1..3...7..4..12.....4...6..9......1..6..28..7..2...9..8..5...5..9..7 6.....7.5.3.8................52.3.8.1.9.........4.....42...........9.1......7.6.. ......41.9..3.....3...5.....48..7..........52.1.......6..2....5.7....8......3.... ...6..9.23.87.....4............95..17......8...........2..6.5.....4...3..1....... 1.37....5...6.4...8...........81.....9....7...6.....9..2....4..5...3...........2. .4.7...6...39............57.......3.2...8.....19...57.6...4.....5.1......2...6.84 26.7...........4.15........839.........5...6....1......7.....2.....43.......9.8.. 4.21......5.....78...3......7..5...6......1.....4.........67.5.2.....4..3........ 3..1...6...1.47.......5....68.3...........4.1.2.......4.5...7.....2...8.......... 6.1....3....8..2..9.........47...5......7........6.....8.5.2...3.......1...4...9. .6..2...1...3...7..1.......3.49.....7.....2........5.8....586.........4.9........ 8.5.....2...4.1...3.........6.7..4..2...5...........6....38.....1....9...9.....7. .2.....8.....4.6......1.....3.2.74..1.....5.....8.....2..3...7.4.5......6........ ....7..438.....5...........2..5.1..........64...8......34...6.....2..1...7..6.... .2.3...6.....7.5...1.......7.86..4.....9.2...5...........1...394...8............. 5.3.9..........7.12........4...2..5..1.8......6.7........4.86.........3.9........ 5.3.9..........8.12........4...2..5..1.8......6.7........4.76.........3.9........ .2.3...6.....7.5...1.......7.86..4.....9.2...5...........1...934...8............. ......31.7..5.....2...4.....39..8..........62.1.......5..6....7.8....9......5.... ...7....6.29.......1....3..7..56..........24....8.....4......35....91...8........ ......31.6..5.....2...4.....39..8..........42.1.......5..6....7.8....9......5.... ......12....3..6.....8.9.......2..6.3.8......7...5.....15...4.....7....9.4....... ..9.7........4.6....1....8....1.9.3.54..........8......5....7.62..3...........2.. 1..46...5.2....7......9.....3.7.8..........91...2........3..84.6........5........ 5..2..3......8..9...2..4..66..1..9...1.....4...7..3..87..3..4...9..7..2...5..6..9 4.9...5.....8....27..3.........4.7...8.....6..1..........6..12.5...9...........3. .5..7..83..4....6.....5....83.6........9..1...........5.7...4.....3.2...1........ ..1....8....2..5.....6.........41.3.62....7..........927.8.........3...45........ .894............72.3.......1....5.6..4....9......1....5...6...7...3..8..2........ ...6..9.23.87.....4............59..17......8...........2..6.5.....4...3..1....... 7..63...........81....2....685..1......7..6...4..........8.4.5.2.....3........... 69....2.....7...4............73.4...5.....6.1...8........5..83.2...9........1.... 8.5.....2...9.1...3.........6.7..4..2...5...........1....38.....9....7...4.....6. ...7....2.8....1...9.......7.6....3.....91...2............5.84.3..6........4..5.. 69....2.....7...4............73.4...5.....9.1...8........5..83.2...6........1.... 56....4....72.................3...7861...............2....461..1...5......8....3. 4..6..3...1..2..6...8..7..19..8..5...4..5..1......2..75.....6...3..8..4......9..5 7..69..........35.......1..2.9.....7...3...4.8.........4.5..6......28....1....... 46.....29....3.5...........1.5.4...........723.........7.6.2.....4...1.....9..... .5.7.1...2.8....6...........4.3..5..9.2......6...8.....7.1..3......2..9.......... .135.........7.4...........1......892.4.6....7.........8.1.....6.....2.....9.3... 5..4..8......9..1...2..1..56..3..4...5..7......4.....83..6..7...6.....8...8..2..1 ...4.5.2.81..............7.3...9.1....5....4...........6..1.8....27........2..9.. .1..3..6.8..................63.9....7..8..4......1.5...9.....1.2..7........5..7.. 3..4.6....9....7...........6.41.........7.2.9......5......3..8.52..........8...1. ..9.2........4.6....1....8....1.9.3.54..........8......5....7.67..3...........2.. ...8...3...5...7.....1.........5.9..18.......3..4.......7..2..6....7.5...4.....1. 2.7.4.......6...3.9........4...2.8.......5......3......6.1.3.5.......2.9.1....... 1...6........2.7...53........98...........41.......6.742..........3.9......5...8. .1.65..4.8.......9.......3.15........76..........28......7..5..3..4...........2.. .7.3...6.....8.5...1.......8.96..4.....1.2...5...........7...324...9............. .6..2...1...3...7..1.......3.49.....7.....2........5.8....856.........4.9........ 8.......24...3........5..1...1...56.......9.....7........8.4..7.6....3...9.2..... .2.....9.....1.6..7...3....5.7...1.....2.4.8....9.....64.8.....3.....5........... 3..4...8.....5.2...........152.......7..1.......9...6..15...7..6..3.4............ ..8.17......5...3..........54.....2.63...........76.....6...8.72..4...........1.. .2.....9.....1.3..7...4....6.7...1.....2.5.8....9.....45.8.....3.....6........... .2.....74.98.1.............7..3.5..6....2.9..1..............83....6.7......4..... 6.....8.5.3.9................52.3.9.1.7.........4.....42...........8.1......7.6.. ...46..8.7.....9.....1.....4....53...8.6......2.......3.9.7...........215........ 8.5.....2...9.1...3.........6.7..4..2...5...........6....38.....4....7...9.....1. 6.81..........72.............3.5..615....4..........8.47....5.....63.....2....... ```

In test runs, the program averages one solution to these tough puzzles, every 1.4 seconds. That would be cut down a great deal if it didn't have all the returning to do from the solving functions.

Thanks to M-S-H for bringing this to the forum. It's a fun program. :)
• 12-15-2009
iMalc
Quote:

It's fast. I fed it four of my toughest (for computers), and it solved all four in just a few seconds. The only one that took more than 4 seconds (maybe 7, I didn't put a timer on it yet), was the "brute force nightmare" puzzle from Wikipedia.

In it's current form, it shows all solutions, which is a nice option. I hate it when I work through a puzzle only to find out the solution the paper gives, is just one of the many solutions that are valid. Puzzles with more than one solution, are NOT valid sudoku puzzles, in the opinion of many Sudoku fans.

I'll set it up with an option to the run the "Top 1465" puzzles, and get a time on that, and maybe the 50,000 "17's", as well.

It isn't the fastest solver I've seen, but it is quick. If you could add some expertise to speed it up, that would be great, iMalc. I have solve times for the well known 5 fastest solvers on the Sudoku Programmers Forum - but this program won't be in that category.

Ah okay. Myself and one of the other posters on here at one point shared ideas and we both got our solvers down to under 10 milliseconds for any board, so in relative terms a few seconds is slow, but in absolute terms it isn't too bad.

The two things that give you a huge gain are:
1. Rather than checking whether a given move is invalid according to all positions in each row column or block each time, store all the possible values that can go in each spot in a bitmask so that you already have enough information to check if it is valid very quickly. When you fill in a number you copy and update the whole board bitmask according to the same rules in your 'safe' function.
2. Next, now that you can see at a glance how many values are possible in each spot, you simply try them in the order of fewest possible values remaining to most possible values remaining. This minimises backtracking, which gives the most speed boost.

Mine's up on my site under Useful Classes (though I should reorganise things to put it elsewhere).
• 12-15-2009
I forgot to mention, that after the program finds one solution, it is still searching for all the other possible solutions to that puzzle - which is a significant extra burden.

I'm familiar with bit boards for Sudoku, but don't program using them, myself. When I want real speed, I use Brians BB_Sudoku.

This is the solve times of the 5 fastest solvers (so far), on the Sudoku Programmer's bb:
Code:

```                Top 1465 Sudocoo          0.578  fast_solv_9r2    0.421  Sudocoup        0.406 zerodoku        0.406 BB_Sudoku v0.1  0.224 All times in seconds```
BB_Sudoku uses a lot of fast look up tables, and of course, bit boards galore!

I will be posting the "Top1465.txt" file to Swoopshare and adding it's url here, so anyone who's interested can download it.
Edit: This is the link to the file:
http://www.swoopshare.com/file/48285...p1465.txt.html

Sounds like your solver might be ready to try for a spot in the top 5, iMalc. Good on ya!