Sign in to follow this  
TKE Super Dave

Sudoku Solver

Recommended Posts

I'm attempting to write a solver for a sudoku in C++. However I'm having trouble with the rules for figuring out how to solve it. Currently what I have is that it reads in the array from a text file and then it figures out what it needs in the rows, columns, and 3x3 grids. Currently my rules are to check if the there is a blank space then check to see what number is needed in both the row and the column, if it is put it in the space and take that number out of the row and column list. However it doesn't seem to be taking out the number that I took from the rows and columns. Can someone help me figure out why or point me to an easier way to solving the sudoku? The sudoku I'm attempting to solve:
9 0 0 0 3 0 0 0 0
3 4 0 0 0 0 7 0 5
0 2 0 0 1 0 0 6 0
5 0 0 8 0 0 0 0 6
4 0 9 0 0 0 0 7 0
0 1 3 5 7 0 2 0 0
0 6 0 0 0 3 8 0 4
0 0 4 1 6 2 0 5 0
0 0 0 0 0 0 0 0 0
The code:
#include <iostream>
#include <fstream>
#include <string>
   using namespace std;
   void printArray(int array[][9], int row, int col);
   //void printArray(int array[][9], int row, int col);
   const int row = 9, col = 9;
   
    class Life
    {
    public:
      void  runLife(void);
      void  printLife (int [9][9]);
      void  escapeMaze(int [9][9]);
   };

    int main(void){
      Life life;
      life.runLife();
      return 0;
   }
	 
    void Life::runLife(void)
   {
    //sets up the array for the input
      
      int array[9][9] = {{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0}};
         
      int num =0;
      int m;
      int n;
   	
     //reads in the file
      ifstream inClientFile("hw3.dat", ios::in);
      
      if (!inClientFile)//file not found
      {
         cerr<<"file could not be opened"<<endl;
         exit(1);
      }
   
      //reads in the file
     
      for(n=0; n<col; n++)
      {    
         //cout<<"Column"<<n<<endl;
         for(m=0; m<row; m++)
         {
            //cout<<"Row"<<m<<endl;
            inClientFile>>num;
            //cout<<num<<endl;
            array[n][m]=num;//inClientFile.get();	
               //cout<<array[n][m]<<endl;
         } 
      }
      escapeMaze(array);
   	     
      printLife(array);
      
   }
	
	
    void Life::printLife(int array[9][9])
   {
         
      int i, j, x;
    
      
   //print out the last generation into a file
      ofstream outClientFile( "hw3 output.dat", ios::out);
      if (!outClientFile)
      {
         cerr<<"file could not be opened"<<endl;
         exit(1);
      }
      
      int q;
      int w;
      
     
   //Prints out the final array	
      for (q=0; q<row; q++)
      {
         for (w=0; w<col; w++)
            outClientFile << array[q][w] << " ";
         outClientFile << endl;
      }
           
      outClientFile << endl;
      outClientFile << endl;   
   }
   
 
    void Life::escapeMaze(int array[9][9])
   {
      
      int arrayRow[9][9];
      int arrayCol[9][9];
      int arrayMatrix[9][9];
   /* 
   *  What needs to go into the rows
   */   
      for(int y=0; y<col; y++)
      {
         int arrayCheck[]={1,2,3,4,5,6,7,8,9};
         for(int k=0; k<row; k++)
         {
            if(array[y][k]!=0)
            {
               int i=0;
               while(arrayCheck[i]!=array[y][k])
               {
                  i++;
               }
               arrayCheck[i]=0;
            }
         }
         
         for(int o=0; o<9; o++)
         {
            arrayRow[y][o]=arrayCheck[o];
            cout<<arrayRow[y][o];
         }
         cout<<endl;
      } 
      
      cout<<"Columns"<<endl;
   /*
   *  What needs to go into the columns
   */   
      for(int y=0; y<col; y++)
      {
         int arrayCheck2[]={1,2,3,4,5,6,7,8,9};
         for(int k=0; k<row; k++)
         {
            if(array[k][y]!=0)
            {
               int i=0;
               while(arrayCheck2[i]!=array[k][y])
               {
                  i++;
               }
               arrayCheck2[i]=0;
            }
         }
         
         for(int o=0; o<9; o++)
         {
            arrayCol[o][y]=arrayCheck2[o];
            cout<<arrayCol[o][y];
         }
         cout<<endl;
      }     
      cout<<"3 x 3's"<<endl;
   /*
   * What needs to go in the 3 x 3 Matrixs.
   */
      int num=0;
      int k=0;
      while(num<3)
      {  
         int arrayCheck3[]={1,2,3,4,5,6,7,8,9};
         for(int g=0; g<3; g++)
         {
            for(int h=0+k; h<3+k; h++)
            {
               if(array[g][h]!=0)
               {
                  int i=0;
                  while(arrayCheck3[i]!=array[g][h])
                  {
                     i++;
                  }
                  arrayCheck3[i]=0;
               } 
            }
         }
         for(int o=0; o<9; o++)
         {
            arrayMatrix[num][o]=arrayCheck3[o];
            cout<<arrayMatrix[num][o];
         }
         cout<<endl;
         num++;
         k=k+3;
      }
   
      k=0;
      while(num<6)
      {  
         int arrayCheck3[]={1,2,3,4,5,6,7,8,9};
         for(int g=3; g<6; g++)
         {
            for(int h=0+k; h<3+k; h++)
            {
               if(array[g][h]!=0)
               {
                  int i=0;
                  while(arrayCheck3[i]!=array[g][h])
                  {
                     i++;
                  }
                  arrayCheck3[i]=0;
               } 
            }
         }
         for(int o=0; o<9; o++)
         {
            arrayMatrix[num][o]=arrayCheck3[o];
            cout<<arrayMatrix[num][o];
         }
         cout<<endl;
         num++;
         k=k+3;
      } 
   	
   	
      k=0;
      while(num<9)
      {
         int arrayCheck3[]={1,2,3,4,5,6,7,8,9};
         for(int g=6; g<9; g++)
         {
            for(int h=0; h<3+k; h++)
            {
               if(array[g][h]!=0)
               {
                  int i=0;
                  while(arrayCheck3[i]!=array[g][h])
                  {
                     i++;
                  }
                  arrayCheck3[i]=0;
               } 
            }
         }
         for(int o=0; o<9; o++)
         {
            arrayMatrix[num][o]=arrayCheck3[o];
            cout<<arrayMatrix[num][o];
         }   
         cout<<endl;
         num++;
         k=k+3;
      } 
   /*
   * Actually solves the Sudoku
   */
      for(int i=0; i<9; i++)
      {
         for(int j=0; j<9; j++)
         {
            if(array[i][j]==0)
            {
               cout<<"Row: "<<i<<" Col: "<<j<<endl;
               for(int k=0; k<9; k++)
               {
                  if(arrayRow[i][k]!=0)
                  {   
                     for(int l=0; l<9; l++)
                     {
                        if(arrayCol[j][l]==arrayRow[i][k] && arrayCol[i][l]!=0)
                        {
                           array[i][j]=arrayCol[i][l];
                           //cout<<"Enters "<<array[i][j]<<endl;
                           arrayCol[j][l]=0;
                           //cout<<"Area in arrayCol "<<arrayCol[j][l]<<endl;
                           arrayRow[i][k]=0;
                           //cout<<"Area in arrayRow "<<arrayRow[i][k]<<endl;  
                        }
                     }
                  
                  }
               } 
            }
         }
      }	
      
   	
      for (int q=0; q<row; q++)
      {
         for (int w=0; w<col; w++)
            cout<< array[q][w] << " ";
         cout<< endl;
      }
   }

Share this post


Link to post
Share on other sites
I strongly encourage you to learn the principle of object oriented programming before you start implementing any (advanced) algorithms in C++.

What you have presented here is very difficult to follow because of unclear (unnecessary short) naming and the absence of the already mentioned object oriented code pattern.
It just takes too much time to find the section where errors may have accured if you have to follow through the whole program first.

Applying object oriented code practice will not only help you in debugging your code by making it more modular, it will also make it possible for you to separate the algorithms from the "glue" code, the rest of the program and that will help you immensely in concentrating on algorithm development and improvement.
Also very important: well constructed object oriented code will be easier to be reviewed by others, who might then help you in solving any occuring problems more efficiently.

Hope you take it as constructive criticism!

Share this post


Link to post
Share on other sites
I thought it was a object oriented in style. If it isn't I'd love for you to point out to me what I could do to change it and make it so, as apparently my past school professor has taught me wrong. Admittedly the rules and the finding out what numbers go where could be split up, however to make up for that I left comments as to where those sections where. The problem is in the section that is commented: Actually Solves Sudoku. I know that is where the problem lies, however I don't know what's causing it.

Share this post


Link to post
Share on other sites
Sorry, I couldn't find the source of your problem. It is hard to figure out what your code is doing. I don't think that is related to the principles of object oriented programming, but instead because it is complicated and not commented enough. It would be easier to figure out if you split the one big complicated function into several sub-functions.

Also, some of the code can be simplified. Could this code:
               int i=0;
while(arrayCheck[i]!=array[y][k])
{
i++;
}
arrayCheck[i]=0;
be replaced with this?
               int i = array[y][k];
arrayCheck[i-1]=0;
Finally, your method for solving a suduko is not sufficient to solve anything but the simplest puzzle. For example, the number in the first row, second column could be 5, 7, or 8. You need to learn how to solve a suduko before writing a program to do it.

Share this post


Link to post
Share on other sites
So you want to find out what is wrong...

First, rewrite your program so that no function is more than 5 to 10 lines long. If it is longer, it should be calling a helper function.

Each function should have describable preconditions and postconditions -- ie, it should require certain things about the input (sometimes as simple as "the first pointer is a valid sodoko board), and guarantee certain things will be done by the end. You should have comments that describe this (they can be informal, but they must exist).

The name of the function should be, in pretty plane english, what the function does.

You can even add "checking" code that double-checks that the pre and post conditions are met -- ASSERTS, or heavier-weight checking code, can be used.

Once you have done this, you can sit down and walk through a program execution. At each short function, each function has a described job, and is short enough that you can actually see everything it is planning to do at once.

Next, don't pass around arrays. Pass around references and pointers to structures containing your arrays: the syntax is much clearer. As a bonus, your structs can initialize themselves to zero.

Finally, variables should be declaired as close to as possible to where they are initialized and used, and they should leave scope as soon as is reasonable. Doing this reduces the amount of state your program is lugging around. Excess state is bad.

Variables like "row" and "col" are bad. They aren't "row" and "col", they are "number of rows" and "number of columns". And, as a bonus, you used the name of your global constants as names to parameters to a function!

Share this post


Link to post
Share on other sites
Quote:
Original post by TKE Super Dave
I thought it was a object oriented in style. If it isn't I'd love for you to point out to me what I could do to change it and make it so, as apparently my past school professor has taught me wrong. Admittedly the rules and the finding out what numbers go where could be split up, however to make up for that I left comments as to where those sections where. The problem is in the section that is commented: Actually Solves Sudoku. I know that is where the problem lies, however I don't know what's causing it.

You have declared one class (Life) and are using one instance of it (life), but it could just has been three global functions instead, you aren't actually working on the object. Also the naming is obscure for me, Life, where does Life belong on a Sudoku game ;) ?
An (ideal) object holds data and provides ways to work on it.

As others have pointed out, you don't need to do it object oriented, but as I could see that that is what you've been trying to, I had to point out that you failed at that.

If I had to write object oriented code for a Sudoku solver, there are a few possible classes I would directly think of: Board, Cell and Solver (the Solver is up to debate, its functionality could be part of the Board class, but I tend to approach problems this way).
All of them would be actual physical objects on a real Sudoku game, Board being the board holding the cells, Cell being the elementary unit that the board consists of and the Solver being... well me trying to solve the game.
Depending on this classes I would have some possibly useful structures in mind like CellPosition (could be member of Cell, or an independent entity). Or what about Row, Column and Grid, this could be actual objects, but it might me more clever to keep them just as references to certain Cells on the Board, the way you accomplish this is up to you.

Now you can go more into detail, what are the properties of the Cell class, it should be the value of the cell and maybe the optional values that it could hold (I left out the position of the cell on the Board, because this is really up to your implementation). The optional values would be needed if you implement a more natural approached algorithm, going from the perspective of a human solver, who will most probably solve by excluding the impossible values untill the options of a cell shrinks to one value.

Go through all the possible Classes (on paper) and think about the details, the result will be a greater picture of the whole program structure before you even wrote a line of code. At this point you should see if your idea could work out and where it needs improvement, keeping thigs structured and simple is the key to solve more complicated or just complex problems.

I hope my little example of how to start designing code could look like is at least a bit helpful, it's quite late and I would need more time to give better examples and more carefully phrased explanations, but I just didn't want to leave my first post there without providing at least some tips how to make it better.

Apart from the OOP thing, your naming isn't good. I already mentioned the little bit misleading naming of your only class, but your code is full of very short variable names that don't really help me understand what they are good for.
I've seen names like "n, x, o" ect. Now read your code in a months or so and tell me what n means without going through all the code again - exactly, you wouldn't know.
Try to be as precise as possible when choosing a name for your variables/objects/functions, in the end it should almost read as plain english instead of a mathematical equatation.

A last thing I would like to say, but this one is actually not only directed at you only but the majority of the posts here, use the standard C++ library whenever possible! It will make your life easier, your code safer and more dynamic.
Of course, you can use a static array to hold your board data, but what if you want to solve a different sized board with a different range of possible values at some point? If you are certain that this will never happen, then there is no need to think about it, but in programming things are rarely static and it would come at almost no cost making it dynamic by using the SC++L.
And while talking about keeping thigs dynamic, you have to avoid using any magic numbers in your code.

[Edited by - kiome on March 8, 2007 11:29:03 PM]

Share this post


Link to post
Share on other sites
As far as solving it goes:

The simplest way to write a code to solve something like this is to think about a systematic way that YOU solve the puzzle that always works. There are several different functions that need to be put together to find the answers. Once you have it all written out on paper, all of the steps, you should very easily be able to code how your program does it.

Share this post


Link to post
Share on other sites
I assume you already know the backtracking algorithm for solving Sudoku puzzles.

To make things easier, I suggest you to use an int variable to be a Sudoku cell storing possible numbers. Therefore, a Sudoku grid can be represented by an 9x9 int array e.g. int grid[9][9].

A 9-bit variable is an arrangement of 9 bits, so it can replace the array storing 9 possible numbers in this way:

000000001 represents only 1 is possible,
000000010 represents only 2 is possible,
000000100 represents only 3 is possible, and so on.

Also, 000000101 represents 1 and 3 are possible numbers,
000000000 represents no possible numbers,
111111111 represents 1 to 9 are all possible, and so on.

With bitwise operators, comparison between two cells can be written in just one line: if (a & b). Variable a and b are compared if they contain the same possible number. If a equals 000000001 and b equals 000000101, then the result is true because both they contain 1 as a possible number. Moreover, you can use &= to add or remove numbers in a cell.

Share this post


Link to post
Share on other sites
Quote:
Original post by CadetUmfer
Here's an OCaml implementation. Weighs in at 19 lines.

There's also links to other implementations at the bottom.


For comparison, the OP's C++ is 300 lines of code! If this is an exercise in C++ then maybe that's ok but, if you want to solve Sudoku puzzles, you might want to pick a high-level language.

Here is a 200-line solution in F# that includes a multithreaded GUI.

Cheers,
Jon.

Share this post


Link to post
Share on other sites
Here is one I whipped up in 20 min or so quite a long time ago. Includes a lot of description on how it works at the beginning, as I sent it to a friend of mine. It's an iterative rather than recursive solution, though it could just as easily be recursive, and the change to recursive is extremely simple.


#include <cstdlib>
#include <iostream>
#include <utility>
#include <stack>


/******************************************************************************
Sudoku solver

How it works:

To start with, I set up a 9x9 sudoku board, where each cell in the board is a set
indicating which possible values the cell can hold given the rules of the game.
I seed the board with the starting puzzle, then execute the function
eliminateCandidates() which will iterate the board and eliminate from each cell's
set any value that it can not possibly hold. Once I have eliminated any invalid
candidates, I iterate the map again and check each cell. If a cell has been
reduced to only 1 possible candidate, I set the cell to that remaining
candidate and continue on, repeating this whole process as many times as
necessary to narrow the puzzle down as much as possible.

Many simple, unambiguous puzzles will already be solved at this stage, since in
those cases there is a clear progression of states with 1 possible candidate; but
other more difficult ones may not be, so I need to set up an algorithm to test
possible states in the case that no clear solution presents itself. Two
possibilities for this algorithm present themselves. I could implement a
recursive-based solution, wherein a solver function would call itself with
progressive possible solutions to the puzzle, or I could do an iterative,
stack-based solution that uses an STL stack of board states to emulate
recursion, without actually recursing. The latter is the process I elected to
implement.

I set up a stack of board states, then push the initial board state (processed
to eliminate candidates as described above) onto the stack. Then I enter a loop.
While the stack is _not empty_, I pop a state off of the stack and check it.
If the state is a completed puzzle, then I return true to indicate the puzzle
is solved, and set the global variable g_return to the solved state.

If the state is not a completed puzzle, then I need to iteratively test further
states. I start with a candidate count of 2 and try to find a cell that
has only 2 possible candidates. If I can not find one with 2, then I will attempt
to find one with 3 possible candidates. Again, if I can't find one, I will try
4, and so on up until the maximum number of candidates (9). As soon as a cell is
found, I will make copies of the board, one copy for each possible state of the
chosen cell. I will make the cell changes, process each board to further
eliminate candidates, and test it for being valid according to the rules of
sudoku. Invalid boards are discarded, and valid boards are pushed back onto the
stack for the next round.

And the loop repeats itself. A board is popped, checked for being complete, and
progressed if not. At some point, either the test function is going to find a
complete board, or the stack is going to be empty when the solver tries to pop
a state. If a complete board is found, the puzzle is solved, but if the stack
goes empty, that indicates that the initial puzzle was malformed and not
solvable.

This approach blends the logic that a human might use to solve a puzzle with the
exhaustive, brute-force method of searching possible game states. Attempting to
solve a sudoku purely on an exhaustive, brute-force method could take several
minutes, if not hours, trying every possible state, good or bad. By intelligently
eliminating candidates, and only testing possible states from known valid states,
I can reduce solve time from minutes/hours to under a second in most cases on
modern computers.

I have not tested this code for robustness as far as badly malformed boards, so
it might very well choke and die on some bad boards. The ones I have tested it
on failed elegantly, but it may be possible that there exists a board so ugly,
so horrendously _wrong_ that it may break this code and/or cause the universe
to implode. You just never know.

It is also interesting to note that some supposedly bogus puzzles are not
quite so bogus in the eyes of this solver. For instance, the 'empty' puzzle
in the file boguspuzzle1.txt, comprised of all 0s. This puzzle is solvable;
try running the solver on it and see. It generates 1 possible solution, though
there are of course a large number of solutions for an empty puzzle. The
solution generated is simply determined by the order in which the cells are
processed by the solver, in this case by means of a predictable iterative
scanner that finds the first acceptable candidate cell for visitation.
By randomizing the order in which the cells are visited for further
exploration, random arrangements of valid sudoku boards can be generated by
puzzle generators.

Other amgibuous puzzles with multiple solutions will also be solved, again with
the final solution being determined by the order in which the cells are
explored.


Josh

******************************************************************************/



// Create a class to represent a single cell in a game board
class CSudokuCell
{
public:
CSudokuCell()
{
clearValues();
m_final=-1;
};

~CSudokuCell()
{
};

char getValue()
{
// Get the value of the cell. Will be -1 if the cell has more than
// one possible candidate.
return m_final;
};

void setValue(char which)
{
// Set the value of the cell, and eliminate other possible
// candidates.
if(which<0 || which>=9) return;
m_final=which;
for(int i=0; i<9; ++i) m_candidates[i]=0;
};

void clearValues()
{
// Restore a cell to all possible candidates.
for(int i=0; i<9; ++i) m_candidates[i]=1;
m_final=-1;
};

void eliminateCandidateValue(char which)
{
// Eliminate a value from being a possible candidate.
if(which<0 || which>=9) return;
m_candidates[which]=0;
};

bool queryCandidateValue(char which)
{
// Find out if the given value is a possible candidate for the cell
if(which<0 || which>=9) return false;
return (m_candidates[which]==1);
};
int getNumCandidates()
{
// Count how many candidates in the cell's set of possible values
if(m_final!=-1) return 0;
int count=0;
for(int i=0; i<9; ++i) if (m_candidates[i]) ++count;
return count;
};

void setCandidateAsFinal()
{
// If a cell has 1 candidate, set it as the cell's value
if (getNumCandidates() != 1) return;
for(int i=0; i<9; ++i) if (m_candidates[i])
{
setValue(i);
return;
}
};




protected:
char m_candidates[9];
char m_final;
};


// Create a class to represent the game board
class CSudokuBoard
{
public:
CSudokuBoard()
{
};

~CSudokuBoard()
{
};

void setCell(int row, int col, char which)
{
// Set a cell's value
if(row<0 || row>=9 || col<0 || col>=9 || which<0 || which>=9) return;
m_cells[row][col].setValue(which);
};

void clearCell(int row, int col)
{
// Clear a cell to all possible values
if(row<0 || row>=9 || col<0 || col>=9) return;
m_cells[row][col].clearValues();
};

char getCell(int row, int col)
{
// Get the value of a cell
if(row<0 || row>=9 || col<0 || col>=9) return -1;

char final=m_cells[row][col].getValue();
return final;
};

int getNumCandidates(int row, int col)
{
// Get the number of candidates for a cell
if(row<0 || row>=9 || col<0 || col>=9) return 0;
return m_cells[row][col].getNumCandidates();
};

bool queryCandidate(int row, int col, int which)
{
// Check if a value is a possible candidate for a cell
if(row<0 || row>=9 || col<0 || col>=9 || which<0 || which>=9) return false;
return m_cells[row][col].queryCandidateValue(which);
};




bool validate()
{
// Validate a possibly partial board, checking rows, columns, and blocks
// for duplicated final values. Ignore cells with non-final candidate values
// Return true if the board is still valid, false if it is not.
// Works by simple checking each value in a row, column and block
// to see if another cell in the row, column or block is already
// the same value.
char cells[9];

// First, check rows
int row, col;

for(row=0; row<9; ++row)
{
// Clear out cells array
for(int i=0; i<9; ++i) cells[i]=0;
for(col=0; col<9; ++col)
{
char final=m_cells[row][col].getValue();
if(final != -1)
{
if(final<0 || final>=9) return false;
if(cells[final])
{
// Cell is already set, invalid
return false;
}
else
{
// Cell not set, set it
cells[final]=1;
}
}
}
}

// Now, check columns
for(col=0; col<9; ++col)
{
for(int i=0; i<9; ++i) cells[i]=0;
for(row=0; row<9; ++row)
{
char final=m_cells[row][col].getValue();
if(final != -1)
{
if(final<0 || final>=9) return false;
if(cells[final])
{
// Cell is already set, invalid board
return false;
}
else
{
cells[final]=1;
}
}
}
}

// Now, check blocks.
int br, bc;
for(br=0; br<3; ++br)
{
for(bc=0; bc<3; ++bc)
{
// Clear cells
for(int i=0; i<9; ++i) cells[i]=0;

for(row=0; row<3; ++row)
{
for(col=0; col<3; ++col)
{
int ri=br*3+row;
int ci=bc*3+col;
char final=m_cells[ri][ci].getValue();
if(final != -1)
{
if(final<0 || final>=9) return false;
if(cells[final])
{
// Cell already set, invalid board
return false;
}
else
{
cells[final]=1;
}
}
}
}
}
}


// If we get here, all rows, columns and blocks check out, and
// the board state is valid
return true;
};



void setSingleCandidateCells()
{
// Iterate the board, checking for cells with 1 possible candidate
// value, and setting those cells to final values
int row, col;
for(row=0; row<9; ++row)
{
for(col=0; col<9; ++col)
{
int num=m_cells[row][col].getNumCandidates();
if(num==1)
{
m_cells[row][col].setCandidateAsFinal();
}
}
}
};


void eliminateFromRow(int row, char which)
{
// Eliminate a cell value candidate from all non-final cells in a row
if(which<0 || which>=9) return;
if(row<0 || row>=9) return;

int col;
for(col=0; col<9; ++col)
{
if(m_cells[row][col].getValue()==-1)
{
m_cells[row][col].eliminateCandidateValue(which);
}
}
};


void eliminateFromCol(int col, char which)
{
// Eliminate a cell value candidate from all non-final cells in a column
if(which<0 || which>=9) return;
if(col<0 || col>=9) return;

int row;
for(row=0; row<9; ++row)
{
if(m_cells[row][col].getValue()==-1)
{
m_cells[row][col].eliminateCandidateValue(which);
}
}
};


void eliminateFromBlock(int br, int bc, char which)
{
// Eliminate a cell value candidate from all non-final cells in a block
if(br<0 || br>=3 || bc<0 || bc>=3) return;
if(which<0 || which>=9) return;

int row,col;
for(row=0; row<3; ++row)
{
for(col=0; col<3; ++col)
{
int ri=br*3+row;
int ci=bc*3+col;
if(m_cells[ri][ci].getValue()==-1)
{
m_cells[ri][ci].eliminateCandidateValue(which);
}
}
}
};




void eliminateCandidates()
{
// Iterate the cells of the board. On cells that are final, get that
// value and eliminate it as a candidate for other cells in that row,
// column and block.
int row,col;

for(row=0; row<9; ++row)
{
for(col=0; col<9; ++col)
{
char final=m_cells[row][col].getValue();
if(final !=-1)
{
eliminateFromRow(row, final);
eliminateFromCol(col,final);
eliminateFromBlock(row/3, col/3, final);
}
}
}
};



void process()
{
// Process a board, eliminating candidates, setting cells with 1 candidate
// as final, and continuing until no more cells with 1 candidate are found
while(hasSingleCandidateCells())
{
setSingleCandidateCells();
eliminateCandidates();

}
};

bool hasSingleCandidateCells()
{
// Check the board to see if it has at least 1 cell with only
// 1 possible candidate left in the set.
int row, col;
for(row=0; row<9; ++row)
{
for(col=0; col<9; ++col)
{
if(m_cells[row][col].getNumCandidates()==1)
{
return true;
}
}
}
return false;
};

std::pair<int, int> getCellWithNumCandidates(int num)
{
// Iterate the board and find a cell with the given number of
// possible candidates. Return the row/col coordinates of the
// cell as a std::pair, return the pair (-1,-1) if no cell with
// the given number of candidates is found.
std::pair<int, int> p(-1,-1);

int row, col;
for(row=0; row<9; ++row)
{
for(col=0; col<9; ++col)
{
if(m_cells[row][col].getNumCandidates()==num)
{
p.first=row;
p.second=col;
return p;
}
}
}

return p;
};


bool isComplete()
{
// Check the board to see if it is complete. If any cell has not
// been assigned a final value, the board is not complete.

int row, col;

for(row=0; row<9; ++row)
{
for(col=0; col<9; ++col)
{
if(m_cells[row][col].getValue()==-1) return false;
}
}

return true;
};


void print()
{
// Print out the board's current state.
int row, col;
for(row=0; row<9; ++row)
{
for(col=0; col<9; ++col)
{
int val = getCell(row,col) + 1;
std::cout << val << " ";
}
std::cout << std::endl;
}
std::cout << std::endl;
};

void printNumCandidates()
{
// Print out the current board state's number of candidates per
// cell. Each element in the printout represents the number of
// possible states a cell can have at that board's stage. Debugging
// purposes.

int row, col;
for(row=0; row<9; ++row)
{
for(col=0; col<9; ++col)
{
int c = m_cells[row][col].getNumCandidates();
std::cout << c << " ";
}
std::cout << std::endl;
}
std::cout << std::endl;
};


protected:
CSudokuCell m_cells[9][9];
};

/****************************************************************************/
// The solver



// Set up our global stack and final result
std::stack<CSudokuBoard> g_stack;
CSudokuBoard g_result;

void addBoardStates(int row, int col, CSudokuBoard b)
{
// Given a board state and a row/col pair, generate all the possible states
// the board can have from the possible candidates of the cell at row/col.
// If the cell at the coordinates can have 2 possible values, 2 new boards
// are generated, 1 for each possibility. Same for 3, 4, etc...
// Generated states are processed to eliminate invalid candidates, checked
// for validity, and pushed onto the global state stack.

if(row<0 || col<0 || row>=9 || col>=9) return;
int num = b.getNumCandidates(row, col);
if(num<=0) return;

int i;
for(i=0; i<9; ++i)
{
// Check to see if i is a possible state for the cell.
// If so, create a new board and set the cell value to i.
if (b.queryCandidate(row, col, i))
{
CSudokuBoard newboard = b;
newboard.setCell(row, col, i);
newboard.eliminateCandidates();
newboard.process();
if(newboard.validate())
{
// new board state is valid, push it on the stack
// otherwise ignore it and continue one
g_stack.push(newboard);
}
}
}

}


bool solveBoard(CSudokuBoard b)
{
// Solve an initial input board state.

// Clear the stack, in case the program has already solved a puzzle
while(!g_stack.empty())
{
g_stack.pop();
}

b.eliminateCandidates();
b.process();
if(!b.validate())
{
// Initial puzzle is bogus
return false;
}

if(b.isComplete())
{
// Puzzle is solved. Many simple puzzles in which there is always
// a clear, single viable candidate at each step of the process,
// will be solved at this point without having to proceed to
// exhaustive state exploration.
g_result = b;
return true;
}

// Puzzle is valid and not solved, push on the stack and begin the loop

g_stack.push(b);

CSudokuBoard work;
while(!g_stack.empty())
{
work=g_stack.top();
g_stack.pop();

if(work.isComplete())
{
g_result=work;
return true;
}
else
{
// Board is not complete
// Try to find a low-candidate-count cell to test

int cellcount;
for(cellcount=2; cellcount<=9; ++cellcount)
{
std::pair<int, int> p = work.getCellWithNumCandidates(cellcount);
if(p.first != -1)
{
// We have a cell with the lowest number of possible states
// Explore all of it's states as possible solutions.
addBoardStates(p.first, p.second,work);
break;
}
}

}
}

// If we get here, the stack is empty and we do not have a complete puzzle
return false;

}

void usage(const char *reason)
{
std::cout << "Error: " << reason << std::endl;
std::cout << "Sudoku solver" << std::endl << "Usage: sudokusolve <filename>" << std::endl;
std::cout << "Where <filename> is a text file holding the puzzle to solve, each element in the file separated by spaces, no commas. Unknown cells are represented by 0s in the text file. See one of the provided sample puzzles." << std::endl;
}

int main(int argc, char *argv[])
{
if (argc<=1)
{
usage("No input file given.");
system("PAUSE");
return EXIT_SUCCESS;
}

FILE *in = fopen(argv[1], "r");
if(!in)
{
usage("Invalid input file given.");
system("PAUSE");
return EXIT_SUCCESS;
}


CSudokuBoard board;

// Load the input file into board
int row,col;
for(row=0; row<9; ++row)
{
for(col=0; col<9; ++col)
{
int val;
fscanf(in, "%d", &val);
val -= 1;
if(val>=0)
{
board.setCell(row,col,(char)val);
}
else
{
board.clearCell(row,col);
}
}
}
fclose(in);
board.eliminateCandidates();


// Test the input board

if(board.validate())
{
std::cout << "Initial board is a valid starting state--" << std::endl;
board.print();
std::cout << "Processing board..." << std::endl;

// Solve it...
if(solveBoard(board))
{
// We have a solution
std::cout << "Board solved. Solution is--" << std::endl;
g_result.print();
}
else
{
// Board could not be solved
std::cout << "Board could not be solved. Check input for correctness" << std::endl;
}
}
else
{
// Whoops, we gave it a bogus starting puzzle
std::cout << "Initial board invalid, please check input" << std::endl;
}



return 0;
}


Share this post


Link to post
Share on other sites
"I whipped up in 20 min or so"

yeah right it took me 20 min to read :-)

Either way Im checking out the code. I hope it doesnt work to
flawless, cuz im having a heck of a time with 2 puzzle right now.

Share this post


Link to post
Share on other sites
Quote:
Original post by pascalosti
"I whipped up in 20 min or so"

yeah right it took me 20 min to read :-)

Either way Im checking out the code. I hope it doesnt work to
flawless, cuz im having a heck of a time with 2 puzzle right now.


Haha. Im gonna have to code up one myself! Maybe today.

OT: Another Vancouver Islander :D

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this