Jump to content
  • Advertisement
Sign in to follow this  
TKE Super Dave

Sudoku Solver

This topic is 4216 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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!=array[y][k])
               {
                  i++;
               }
               arrayCheck=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!=array[k][y])
               {
                  i++;
               }
               arrayCheck2=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!=array[g][h])
                  {
                     i++;
                  }
                  arrayCheck3=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!=array[g][h])
                  {
                     i++;
                  }
                  arrayCheck3=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!=array[g][h])
                  {
                     i++;
                  }
                  arrayCheck3=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[j]==0)
            {
               cout<<"Row: "<<i<<" Col: "<<j<<endl;
               for(int k=0; k<9; k++)
               {
                  if(arrayRow[k]!=0)
                  {   
                     for(int l=0; l<9; l++)
                     {
                        if(arrayCol[j][l]==arrayRow[k] && arrayCol[l]!=0)
                        {
                           array[j]=arrayCol[l];
                           //cout<<"Enters "<<array[j]<<endl;
                           arrayCol[j][l]=0;
                           //cout<<"Area in arrayCol "<<arrayCol[j][l]<<endl;
                           arrayRow[k]=0;
                           //cout<<"Area in arrayRow "<<arrayRow[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
Advertisement
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!=array[y][k])
{
i++;
}
arrayCheck=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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!