Sudoku solver

This is a discussion on Sudoku solver within the C Programming forums, part of the General Programming Boards category; So I found this sudoku solver and I understand the basics, but there are a few things that I quite ...

  1. #1
    Registered User
    Join Date
    Dec 2009
    Posts
    24

    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.
    Last edited by M-S-H; 12-13-2009 at 05:33 PM.

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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!

  3. #3
    Registered User
    Join Date
    Dec 2009
    Posts
    24
    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

  4. #4
    Registered User jeffcobb's Avatar
    Join Date
    Dec 2009
    Location
    Henderson, NV
    Posts
    875

    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

  5. #5
    Registered User jeffcobb's Avatar
    Join Date
    Dec 2009
    Location
    Henderson, NV
    Posts
    875
    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

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by iMalc View Post
    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.

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.
    Last edited by Adak; 12-15-2009 at 10:38 AM.

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by Adak View Post
    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).
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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!
    Last edited by Adak; 12-15-2009 at 02:33 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sudoku solver...
    By matsp in forum C++ Programming
    Replies: 24
    Last Post: 02-14-2011, 07:30 PM
  2. Help for a sudoku Solver
    By axilleask in forum C Programming
    Replies: 3
    Last Post: 11-26-2007, 03:28 PM
  3. Sudoku Puzzle Solver?
    By Apocalypse in forum C Programming
    Replies: 7
    Last Post: 03-12-2006, 01:10 PM
  4. Newbie with a Sudoku Solver program
    By TylerBill in forum C Programming
    Replies: 13
    Last Post: 03-08-2006, 06:27 PM
  5. Sudoku - the new addiction
    By axon in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 11-07-2005, 10:39 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21