Sudoku Brute Force Algorithm Help (recursion?)

[ridilla]

Hi all,

I'm writing a sudoku-solver program for an intro class in C. I'm not asking for anyone to do my homework, don't worry. The function that I'm struggling with ("solve") is one of many called in my main, so let me give you a little background.

The user first inputs 81 values, which are indexed in a 9x9 array ("puzzle[PSIZE][PSIZE]" where PSIZE = 9).

The next function called is "validate," which goes through the array and makes sure no value occurs twice in the same row, column or box, as per sudoku rules. If the puzzle is invalid, it returns 0 and main displays an error message, if valid, it returns the value and main continues.

The main then calls the "setSingles" function, which replaces blank cells with a value, if that value is the only one that can go there, then repeats until it can find no more cells with this characteristic.

Next, the main copies the "puzzle" array (after the single-value-cells have been replaced) to another array called "original". I'm not sure what to do with "original" yet, but it seems like a good idea to have it around.

Now we get to the "solve" function I'm stuck on. It's basically the "brute-force" element of my program. You'll notice that it returns the data-type "stats", which is a user-created data type that I've created. It includes the statistics on how many times a value that the brute-force-algorithm tries to put in a cell doesn't work, and how many times the function hast to backtrack. I'm not worrying about this yet, so you shouldn't either!

Here's a quick run-down on what it does:
It takes the "puzzle" array, finds the first 0 (empty cell), and inputs a 1 into that cell. It then calls the validate function, and if that function returns a 0 (aka the puzzle isn't valid), it starts a loop that increments that 1 and validates until it finds a value that works. After a valid value is inputted, it copies the newly-changed "puzzle" array to another array called "last", along with two variables "rowlocation" and "collocation" that indicate which index was changed. It then moves on to the next empty cell.

If it tries every value 1-9 in a cell, and none work (in my code, represented as if(puzzle[i][j] > PSIZE) ), it backtracks by going to the "last" array, incrementing the value that we previously changed by 1, then copying that to the puzzle array, and going back into the first loop. I've gotten this to work perfectly, I don't believe there's any problem with my code.

My issue is this: I don't know how write code which accommodates cases in which we need to backtrack more than once, moving back more than one array. An idea of mine was that you could simply copy the puzzle array to a different "last" (last1, last2, etc) array after every successful cell-replacement, but i realize this is a super inefficient fix, and also, I have no idea of knowing how many arrays I may need. Also, I could always go back to the original, and increment by 1 the first cell I find that's been changed (provided this doesn't invalidate the puzzle), but I kind of suspect that this won't always work, plus, I get the idea that I'm supposed to be able to backtrack, not just start at the beginning.

I think this gets into the issue of recursion, which I've read a little about, but don't really know much about.

Oh, one thing to note is that we haven't yet covered pointers in class, and thus, there should be no need for them for this program.

Any help? It would be greatly appreciated.

Stats
solve(int puzzle[PSIZE][PSIZE], int original[PSIZE][PSIZE], Stats stats)
{
   int i,
       j,
       value = 1,
       rowlocation,
       collocation,
       redo;

   int last[PSIZE][PSIZE];

   for(i = 0; i < PSIZE; i ++)
   {
      for(j = 0; j < PSIZE; j++)
      {
         if(puzzle[i][j] == 0)
         {
            puzzle[i][j] = value;

            redo = validate(puzzle);
            while(redo == 0)
            {
               puzzle[i][j]++;

               redo = validate(puzzle);

               if(puzzle[i][j] > PSIZE)
               {
                 last[rowlocation][collocation]++;
                 copy(last, puzzle);
                 redo = 0;
                }
            }
               rowlocation = i;
               collocation = j;

              copy(puzzle, last);

         }
      }
   }
   return(stats);
}