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

I don't understand how to input a puzzle I want it to solve

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

http://www3.sympatico.ca/tyler006/suds.txt

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

---

Quote:

---

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.

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

Quote:

---

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.

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.

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

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

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

[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

Quote:

---

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.

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?

Quote:

---

3. it doesn't solve sudokus. I tried it with this one

---

Well, it doesn't solve ALL sudokus :p . 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.

Quote:

---

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.

Quote:

---

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