Thread: Newbie with a Sudoku Solver program

  1. #1
    Registered User
    Join Date
    Mar 2006
    Location
    Pointe Claire, Canada
    Posts
    9

    Newbie with a Sudoku Solver program

    Hi C-folk,

    I'm new to C, and programming generally. My first non-trivial bit of code is a program to solve Sudoku puzzles. Much to my surprise and delight, my program works. However, I'm working completely alone here, and I'd love some feedback from more experienced coders. If anyone wants to take a peek and let me know if i've committed any grave errors that will haunt me in future projects that would be great. To whet your appetite, I used a goto and some do-whiles, which I understand good coders avoid for reasons I'm not fully aware of.

    The program seemed a little long to post here, so I put it up on my webpage:

    www3.sympatico.ca/tyler006/suds.txt

    If that's poor etiquette let me know and i'll post it directly to the forum.

    I'm particularly interested in ideas for getting data into the program, which I currently do by redirecting stdin, ie. 'suds <inputfile' from the command line. And I know it won't solve all problems yet, I haven't taught it to guess, and I need to work out a few more sophisticated solution routines to round it out.

    Thanks for your time and patience,

    Tyler

  2. #2
    Slave MadCow257's Avatar
    Join Date
    Jan 2005
    Posts
    735
    I don't understand how to input a puzzle I want it to solve

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > If that's poor etiquette let me know and i'll post it directly to the forum
    If it's less than a couple of hundred lines or so, then posting to the forum is perhaps a good idea. You can also attach it as a file if you want.

    Posting non-active links like that is just too much work.

  4. #4
    1ST » R. vd Kooij
    Join Date
    Mar 2006
    Location
    Netherlands
    Posts
    154
    Last edited by rkooij; 03-08-2006 at 07:42 AM.

  5. #5
    Registered User
    Join Date
    Mar 2006
    Location
    Pointe Claire, Canada
    Posts
    9
    Ok, I've pasted the program below. To input a puzzle you need to make a .txt file with the values entered by row, with no white space or line breaks - just numbers. Unknown values should be entered as 0. The result is a file that is exactly 81 characters long, the first 9 corresponding to the first row of the sudoku puzzle, the next 9 the second row, etc. I've attached an example, corresponding to the puzzle found here.

    With a prepared input file I just redirect it to standard input when I start suds:

    ./suds <sudokuinput.txt

    Hope that clears things up a bit. I know the input is awkward, I'd appreciate suggestions for how to improve it!

    Tyler


    Code:
    /* Sudoku solver 
       1. Read in the unsolved puzzle from a file, converting 
       to an array of binary flags. 
       
       2. Scan array, using known quantities to turn off flags 
       for related cells (by row, column, and 3x3 square)
    
       3. Locate cells that represent the only possibility for
       a number in their row/column/3x3, and update flags.
    
       4. Save partial solution, guess a missing number, and 
       find complete solution or return to saved solution and 
       guess again.  !!! Need to implement this step !!!
    
       5. Convert the binary flags into integers and print the
       solution.
    
       Written by Tyler Smith, 6 March, 2006 */
    
    #include <stdio.h>
    #include <math.h>
    
    /* Bit-flag constants. */
    
    #define ONE 1 /* 2^0 */
    #define TWO 2 /* 2^1, etc. */
    #define THREE 4
    #define FOUR 8
    #define FIVE 16
    #define SIX 32
    #define SEVEN 64
    #define EIGHT 128
    #define NINE 256
    #define UNKNOWN 511
    #define SOLVED 512
    
    int search (), excluder();
    void display ();
    
    /* The sudoku board is stored as a four dimensional board.
       The first two dimensions locate the row and column of
       the cell within the 3x3 grid, and the third and fourth
       dimensions locate the row and column of the 3x3 grid
       relative to the other grids. The array is an external
       variable, to avoid problems passing it back and forth 
       to the search function. */
    int sudoku[3][3][3][3];
    
    int main ()
    {
      extern int sudoku[3][3][3][3];
      int minrow, mincol, majrow, majcol, i; /*counters*/
      int inputvalue, outputvalue, changecount;
    
      changecount = 0;
    
      /* Populate the matrix */
      /* The input stream must be uninterupted integers, no newlines, no spaces */
      for (majrow = 0; majrow < 3; majrow++)
        for (minrow = 0; minrow < 3; minrow++)
          for (majcol = 0; majcol < 3; majcol++)
    	for (mincol = 0; mincol < 3; mincol++)
    	  {
    	    inputvalue = (getchar() - '0');
    	    if (inputvalue != 0)
    	      sudoku [minrow][mincol][majrow][majcol] = 
    		pow (2, (inputvalue-1));
    	    /* bit-flags correspond to 2 raised to (actual value - 1) */
    	    else if (inputvalue == 0)
    	      sudoku [minrow][mincol][majrow][majcol] = UNKNOWN;
    	    else goto end; /* bail if the input is bad */
    	  }
    
      do
        {
          changecount = search(); 
          
          if (changecount == 0) /* calls exclude when search() fails */
    	{
    	  changecount = excluder();
    	}
        }
      while (changecount != 0); /* continue calling search () until both
    			       search() and excluder () fail */
      
      display ();
    
      return 0;
    
     end:
      printf("Danger Will Robinison!\n");
      return 1;
    }
    
    int search ()
    {
      /*   printf ("Entered Search\n"); FOR DEBUGGING */
      extern int sudoku[3][3][3][3];
      int minrow, mincol, majrow, majcol; /*counters*/
      int tmpminrow, tmpmincol, tmpmajrow, tmpmajcol; /* temporary counters */
      int setvalue; /* store known value for flag-setting */
      int changes = 0; /* track the number of changes made */
    
      /* Search for known values, turn off related flags */
      for (majrow = 0; majrow < 3; majrow++)
        for (minrow = 0; minrow < 3; minrow++)
          for (majcol = 0; majcol < 3; majcol++)
    	for (mincol = 0; mincol < 3; mincol++)
    	  if ((sudoku [minrow][mincol][majrow][majcol] & SOLVED) == SOLVED)
    	    continue; /* If the solved flag is set move on */
    	  else if ((sudoku [minrow][mincol][majrow][majcol] != ONE) && 
    		   (sudoku [minrow][mincol][majrow][majcol] != TWO) && 
    		   (sudoku [minrow][mincol][majrow][majcol] != THREE) && 
    		   (sudoku [minrow][mincol][majrow][majcol] != FOUR) && 
    		   (sudoku [minrow][mincol][majrow][majcol] != FIVE) && 
    		   (sudoku [minrow][mincol][majrow][majcol] != SIX) && 
    		   (sudoku [minrow][mincol][majrow][majcol] != SEVEN) && 
    		   (sudoku [minrow][mincol][majrow][majcol] != EIGHT) && 
    		   (sudoku [minrow][mincol][majrow][majcol] != NINE))
    	    continue; /* If the value is unknown move on */
    	  else
    	    {
    	      setvalue = sudoku [minrow][mincol][majrow][majcol];
    	      /* Set flags for the mini-grid */
    	      for (tmpminrow = 0; tmpminrow < 3; tmpminrow++)
    		for (tmpmincol = 0; tmpmincol < 3; tmpmincol++)
    		  if (tmpminrow == minrow && tmpmincol == mincol) continue;
    		  else 
    		    sudoku [tmpminrow][tmpmincol][majrow][majcol] = 
    		      ~setvalue & sudoku [tmpminrow][tmpmincol][majrow][majcol];
    
    	      /* Set flags for major row */
    	      for (tmpmajcol = 0; tmpmajcol < 3; tmpmajcol++)
    		for (tmpmincol = 0; tmpmincol < 3; tmpmincol++)
    		  if (tmpmajcol == majcol && tmpmincol == mincol) continue;
    		  else 
    		    sudoku [minrow][tmpmincol][majrow][tmpmajcol] = 
    		      ~setvalue & sudoku [minrow][tmpmincol][majrow][tmpmajcol];
    
    	      /* Set flags for major col */
    	      for (tmpmajrow = 0; tmpmajrow < 3; tmpmajrow++)
    		for (tmpminrow = 0; tmpminrow < 3; tmpminrow++)
    		  if (tmpmajrow == majrow && tmpminrow == minrow) continue;
    		  else 
    		    sudoku [tmpminrow][mincol][tmpmajrow][majcol] = 
    		      ~setvalue & sudoku [tmpminrow][mincol][tmpmajrow][majcol];
    
    	      /* Set solved flag so procedure isn't repeated */
    	      sudoku [minrow][mincol][majrow][majcol] = 
    		sudoku [minrow][mincol][majrow][majcol] | SOLVED;
    	      changes++;
    	    }
      /*   printf("Changes %d\n",changes); FOR DEBUGGING */
      return changes;
    
    }
    	    
        
    int excluder ()
    {
      /*   printf ("Entered excluder\n"); FOR DEBUGGING */
      extern int sudoku[3][3][3][3];
      int minrow, mincol, majrow, majcol, i; /*counters*/
      int changes = 0, index;
      int possibles [9] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
      
      /* Exclude by rows */
      for (majrow = 0; majrow < 3; majrow++)
        for (minrow = 0; minrow < 3; minrow++)
          {
    	for (majcol = 0; majcol < 3; majcol++)
    	  for (mincol = 0; mincol < 3; mincol++)
    	    {
    	      if ((sudoku [minrow][mincol][majrow][majcol] & SOLVED) == 0)
    		for (i = 0; i < 9; i++)
    		  {
    		    index = (int)pow(2,i);
    		    if((sudoku [minrow][mincol][majrow][majcol] & index) == index)
    		      possibles[i]++;
    		  }
    	    }
    	     
    
    	for (majcol = 0; majcol < 3; majcol++)
    	  for (mincol = 0; mincol < 3; mincol++)
    	    {
    	      if ((sudoku [minrow][mincol][majrow][majcol] & SOLVED) == 0)
    		for (i = 0; i < 9; i++)
    		  if (possibles[i] == 1 &&
    		      (sudoku [minrow][mincol][majrow][majcol] & (int)pow(2,i)) 
    		      == (int)pow(2,i))
    		    {
    		      sudoku [minrow][mincol][majrow][majcol] = (int)pow(2,i);
    		      changes++;
    		    }
    	    }
    	for (i = 0; i < 9; i++) possibles[i] = 0;
          }
    
      /* Exclude by columns */
      for (majcol = 0; majcol < 3; majcol++)
        for (mincol = 0; mincol < 3; mincol++)
          {
    	for (majrow = 0; majrow < 3; majrow++)
    	  for (minrow = 0; minrow < 3; minrow++)
    	    {
    	      if ((sudoku [minrow][mincol][majrow][majcol] & SOLVED) == 0)
    		for (i = 0; i < 9; i++)
    		  {
    		    index = (int)pow(2,i);
    		    if((sudoku [minrow][mincol][majrow][majcol] & index) == index)
    		      possibles[i]++;
    		  }
    	    }
    	     
    
    	for (majrow = 0; majrow < 3; majrow++)
    	  for (minrow = 0; minrow < 3; minrow++)
    	    {
    	      if ((sudoku [minrow][mincol][majrow][majcol] & SOLVED) == 0)
    		for (i = 0; i < 9; i++)
    		  if (possibles[i] == 1 &&
    		      (sudoku [minrow][mincol][majrow][majcol] & (int)pow(2,i)) 
    		      == (int)pow(2,i))
    		    {
    		      sudoku [minrow][mincol][majrow][majcol] = (int)pow(2,i);
    		      changes++;
    		    }
    	    }
    	for (i = 0; i < 9; i++) possibles[i] = 0;
          }
    
      /* Exclude by 3x3 grids */
      for (majcol = 0; majcol < 3; majcol++)
        for (majrow = 0; majrow < 3; majrow++)
          {
    	for (mincol = 0; mincol < 3; mincol++)
    	  for (minrow = 0; minrow < 3; minrow++)
    	    {
    	      if ((sudoku [minrow][mincol][majrow][majcol] & SOLVED) == 0)
    		for (i = 0; i < 9; i++)
    		  {
    		    index = (int)pow(2,i);
    		    if((sudoku [minrow][mincol][majrow][majcol] & index) == index)
    		      possibles[i]++;
    		  }
    	    }
    
    	for (mincol = 0; mincol < 3; mincol++)
    	  for (minrow = 0; minrow < 3; minrow++)
    	    {
    	      if ((sudoku [minrow][mincol][majrow][majcol] & SOLVED) == 0)
    		for (i = 0; i < 9; i++)
    		  if (possibles[i] == 1 &&
    		      (sudoku [minrow][mincol][majrow][majcol] & (int)pow(2,i)) 
    		      == (int)pow(2,i))
    		    {
    		      sudoku [minrow][mincol][majrow][majcol] = (int)pow(2,i);
    		      changes++;
    		    }
    	    }
    	for (i = 0; i < 9; i++) possibles[i] = 0;
          }
      /* End Exclude by minigrids */
    
    /*   printf("Changes %d\n", changes); FOR DEBUGGING */
      return changes;
    }
    
    void display()
    {
      /* Print the solved array */
      int minrow, mincol, majrow, majcol; /*counters*/
      int solution [3][3][3][3];
      extern sudoku [3][3][3][3];
    
      for (majrow = 0; majrow < 3; majrow++)
        {
          for (minrow = 0; minrow < 3; minrow++)
    	{      
    	  for (majcol = 0; majcol < 3; majcol++)
    	    {
    	      for (mincol = 0; mincol < 3; mincol++)
    		{
    		  switch (sudoku [minrow][mincol][majrow][majcol] - SOLVED)
    		    {
    		    case ONE : solution [minrow][mincol][majrow][majcol] = 1; break;
    		    case TWO : solution [minrow][mincol][majrow][majcol] = 2; break;
    		    case THREE : solution [minrow][mincol][majrow][majcol] = 3; break;
    		    case FOUR : solution [minrow][mincol][majrow][majcol] = 4; break;
    		    case FIVE : solution [minrow][mincol][majrow][majcol] = 5; break;
    		    case SIX : solution [minrow][mincol][majrow][majcol] = 6; break;
    		    case SEVEN : solution [minrow][mincol][majrow][majcol] = 7; break;
    		    case EIGHT : solution [minrow][mincol][majrow][majcol] = 8; break;
    		    case NINE : solution [minrow][mincol][majrow][majcol] = 9; break;
    		    default : solution [minrow][mincol][majrow][majcol] = 0; break;
    		    }
    
    		  printf("%4d",solution [minrow][mincol][majrow][majcol]);
    		}
    	      printf("   ");
    	    }
    	  printf("\n");
    	}
          printf("\n\n");
        }
    }

  6. #6
    Registered User
    Join Date
    Mar 2004
    Posts
    494
    4. Save partial solution, guess a missing number, and
    find complete solution or return to saved solution and
    guess again. !!! Need to implement this step !!!
    so is your program solving the puzzle by guessing? if this is the case, then you will never be able to solve the puzzle and it will take a lot of time to solve it by just pure chance. The site that you posted has a more logical way to solve the puzzle, you need to take into consideration the rest of the numbers already in the puzzle in order to solve it.
    When no one helps you out. Call google();

  7. #7
    Registered User
    Join Date
    Mar 2006
    Location
    Pointe Claire, Canada
    Posts
    9
    No, it doen't guess. Step 4, the guessing part, is not yet implemented, hence the note !!Need to implement this step!!.

    It solves the problem by scanning for cells with known values, then using those values to turn off flags for those values in other cells in the same row, column, or 3x3 grid. (eg. if cell 1,1 is 9 it turns off the 9 flag for all other cells in row one, column one, and the upper left 3x3 grid). When it finds a cell with only one flag left, it marks it as SOLVED. This process repeats until no more changes are made after a complete scan of the board. This is done in the search() function.

    After search() fails to make any changes exlcuder() is called. This will scan all un-SOLVED cells in a row, and record the possible values for these cells. If a value is only possible for one cell in a row (ie. of four unknown cells in row 1 only one of them can contain the value "6") then that cell is set to the value and marked SOLVED. This process is repeated for all rows, all columns, and the nine 3x3 sections making up the entire board.

    After excluder() is called, search() begins again. After both functions fail to produce any changes the resulting board is displayed. For easy, medium, and some hard boards this is the completed solution. However, it is not possible to solve all sudokus without guessing. I am still working on some more complicated algorithms for finding answers logically, but ultimately there must be a guessing component for the hardest puzzles.

    As I said, the program does work for the sample problem. It's very fast - the solution takes less than a second on my machine. I included that particular example because you can see the answer on the website and verify that my program gives the same result.

    Cheers,

    Tyler

  8. #8
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    but ultimately there must be a guessing component for the hardest puzzles.
    No, that's wrong. Sudoku puzzles can all be solved by logical thinking. If it can't, then it isn't a sudoku puzzle.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  9. #9
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    http://sudoku.com/rule.htm

    You might want to find a free sudoku program and then examine its source code to see how to solve sudoku puzzles.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  10. #10
    Registered User
    Join Date
    Mar 2006
    Location
    Pointe Claire, Canada
    Posts
    9
    Quote Originally Posted by dwks
    No, that's wrong. Sudoku puzzles can all be solved by logical thinking. If it can't, then it isn't a sudoku puzzle.
    I had not heard that before. I hope it's true, as it would be more satisfying to come up with a better solution algorithm than to devise a guessing scheme.

    tb

  11. #11
    Registered User
    Join Date
    Mar 2004
    Posts
    494
    Quote Originally Posted by TylerBill
    I had not heard that before. I hope it's true, as it would be more satisfying to come up with a better solution algorithm than to devise a guessing scheme.

    tb
    i told you that the site you posted already explains how sudoku is solved, im guessing you didnt look at it. read this

    http://www.sudoku.com/howtosolve.htm

    and you will understand that there is no guessing involved
    When no one helps you out. Call google();

  12. #12
    Registered User
    Join Date
    Mar 2006
    Location
    Pointe Claire, Canada
    Posts
    9
    Yes, I know. I did read the page, before I posted the link to that site. It doesn't claim that guessing is *never* needed, only lists a number of approaches one might take before guessing becomes necessary. If guessing never becomes necessary that's good news.

    I'm not here, believe it or not, to argue the fine points of sudoku puzzles. I was interested in suggestions regarding improving the code I've written to solve those puzzles. If that sort of general feedback is not the sort of thing that you do in this forum, I apologise.

    TB

  13. #13
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    [edit]
    Ok it does compile as a C program, not as C++...so point 2 is invalid but I think point 1 is still valid though not a showstopper[/edit]

    <snipped>

    1. Why are you declaring extern on your sudoku variable, is there another file you didn't include here? I am not sure you understand what extern is for, based on use here.

    2. your pow() functions are ambigous, you need to make the first parameter a float or double. I changed the 2's to 2.0's, otherwise the compile doesn't know what to convert them to (double or float, though either would be fine, but tha'ts compiler's for you)

    3. it doesn't solve sudokus. I tried it with this one
    00800300700100000004209000000080000500901060030000 7000000060910000000200800400700
    4. There seems to be a lot of duplicate code that could have been "functionized."

    5. And while this last point is a matter of personal taste(...maybe), I really don't like your 4d arrays, they are very non-intuitive when compared with the layout of a sudoku, though logically, I do understand why you did it this way. They also lead to some really deep nesting, all of which makes your code hard to read.
    Last edited by Darryl; 03-08-2006 at 06:43 PM.

  14. #14
    Registered User
    Join Date
    Mar 2006
    Location
    Pointe Claire, Canada
    Posts
    9
    Quote Originally Posted by Darryl
    1. Why are you declaring extern on your sudoku variable, is there another file you didn't include here? I am not sure you understand what extern is for, based on use here.
    I probably don't then. I thought I needed to declare sudoku an extern so I could access it from any function without having to actually pass it to the function. I wanted to avoid passing it, since that's complicated for a 4-d array. Is declaring the variable outside of the main function enough to allow all functions to access it then?

    3. it doesn't solve sudokus. I tried it with this one
    Well, it doesn't solve ALL sudokus . I still need to add more sophisticated solver functions or some sort of trial and error function to get at nastier problems like the one you tried. I started with the most obvious methods, and will add functions to deal with the left-over situations. Your puzzle is mostly left-overs at this point, I'm afraid. At the moment it works on all the 'easy' and 'medium' puzzles I've tried, and about half of the 'hard' ones.

    4. There seems to be a lot of duplicate code that could have been "functionized."
    I agree. But a lot of the repitition involves searching through the 4d array by looping through different dimensions, ie. /*Exclude by rows*/ nests the column loops within the row loops, while /*Exclude by columns*/ does the opposite. Now that you mention it though, I can probably find ways to functionize at least some of that.

    5. And while this last point is a matter of personal taste(...maybe), I really don't like your 4d arrays, they are very non-intuitive when compared with the layout of a sudoku, though logically, I do understand why you did it this way. They also lead to some really deep nesting, all of which makes your code hard to read.
    That's a good point. The array makes sense to me, but it sure makes for ugly code. Perhaps it would be better style to use a vector array (which I could then pass to the functions) and figure out the formula to index the cells I'm after? That would probably drastically reduce the amount of code... I'll give that a shot.

    Thanks for your comments, it's very helpful feedback for me. I know my program isn't anything special, but the fact that it worked at all was a bit of a shock to me, as it's a fair bit more complex than anything else I've tried so far.

    Cheers,

    Tyler

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, 08:30 PM
  2. Sudoku Puzzle Solver?
    By Apocalypse in forum C Programming
    Replies: 7
    Last Post: 03-12-2006, 02:10 PM
  3. newbie looking for hints on first audio program...
    By BrownB in forum Game Programming
    Replies: 2
    Last Post: 07-13-2005, 07:25 AM
  4. Newbie program - improvements?
    By -JM in forum C++ Programming
    Replies: 9
    Last Post: 06-26-2005, 06:53 PM
  5. newbie : compiling a C++ program in linux
    By gemini_shooter in forum C++ Programming
    Replies: 5
    Last Post: 06-23-2005, 02:45 PM