C++ Sudoku Solver

[Bruceification73]

Hey, to all the geeks on Tom's that feel comfortable in their c++ programming abilities:

I need help writing a program that will solve Sudoku puzzles either from resource files or from user input, it doesn't matter which. The program can be structured using functions or classes with private data members. It needs to have at least one class either way. I don't need a working program until May 10, but I need better than what I have now by tuesday.

Here are a couple different programs I am trying that don't work and don't really meet the project requirements:

#include<stdio.h>
#include<conio.h>
#include<iostream>
#include<stdlib.h>
using namespace std;
 
int i,j,k,a[10][10],o,x[100],y[100];

void display();
int getnum();
void solve(int [],int [],int);
int check(int ,int );
 
void main()
{
//clrscr();
cout<<"\n\nEnter the elements of SUDOKU in rowwise.\n[ Enter '0' if element is absent. ]";
for(i=1;i<=9;i++)
for(j=1;j<=9;j++)
scanf("%d",&a[i][j]);
printf("\n\nEntered SUDOKU\n\n");
display();
printf("\nEnter any key for solution....\n");
getch();
o=getnum();
solve(x,y,1);
}
 
int getnum()
{
int c=0;
for(i=1;i<=9;i++)
{
for(j=1;j<=9;j++)
{
if(a[i][j]==0)
{
c++;
x[c]=i;
y[c]=j;
}
}
}
return(c);
}
 
void display()
{
for(i=1;i<=9;i++)
{
for(j=1;j<=9;j++)
{
if(a[i][j]!=0)
printf(" %d",a[i][j]);
else
printf(" ");
}
printf("\n\n");
}
}
 
 
void solve(int p[100],int q[100],int n)
{
for(k=1;k<=9;k++)
for(i=p[n];i<=p[n];i++)
for(j=q[n];j<=q[n];j++)
{
a[i][j]=k;
if(n<0)
solve(p,q,n++);
int ch=check(1,0);
if(ch!=0)
{
display();
getch();
exit(0);
}
}
 
int check(int n,int r)
{
int f=0,cont=0;
if(r==1)
{
for(k=1;k<=9;k++)
{
for(i=n;i<=n;i++)
for(j=1;j<=9;j++)
{
if(k==a[i][j])
f++;
}
if(f!=1)
return(0);
else
cont++;
f=0;
}
if(cont!=9)
return(0);
else if(n==9)
check(1,0);
else
check(n++,1);
}
else
{
for(k=1;k<=9;k++)
{
for(i=1;i<=9;i++)
for(j=n;j<=n;j++)
{
if(k==a[i][j])
f++;
}
if(f!=1)
return(0);
else
cont++;
f=0;
}
if(cont!=9)
return(0);
else if(n!=9)
check(n++,1);
}
}

(Sorry, it's poorly formatted, I know)

And:

#include <iostream>
using namespace std;

class CSudokuSolver
{
public :
  enum CELL_STATE { STATE_NOTSET=0, STATE_FIX, STATE_FIXTEMP, };
private :
  char CellValue[9][9];
  int IsValueOkAt(int iValue,int atX,int atY) const;
  int FixCellAt(int ix, int iy);
public :
  CSudokuSolver( );
  void SetValue(int ix,int iy, int iValue, CELL_STATE iState=STATE_FIX);
  int GetValue(int ix,int iy) const;
  CELL_STATE GetState(int ix,int iy) const;
  int Solve(); 
  static int Box3x3Start(int idx) { return 3*(idx/3); };
};

int CSudokuSolver::FixCellAt(int ix,int iy)
{
  if( GetState(ix,iy)==STATE_FIX ) { // do the next cell
    if( ix==8 && iy==8 ) return 1;// The last cell, done successfully
    if( ix<8 ) ix++; else { iy++; ix=0; }
    return FixCellAt(ix,iy);
  }
  else {
    int i,j,iv; // Try numbers from 1 to 9
    for(iv=1; iv<10; iv++) { //---- Reset the values to 0
      for(i=ix; i<9; i++) if( GetState(i,iy)!=STATE_FIX) SetValue(i,iy,0);
      for(i=iy+1; i<9; i++) {
        for(j=0; j<9; j++) if( GetState(j,i)!=STATE_FIX) SetValue(j,i,0);
      }
      if( IsValueOkAt(iv,ix,iy) ) {
        SetValue(ix,iy,iv,STATE_FIXTEMP);
        if( ix==8 && iy==8 ) return 1; // The last cell, done successfully
        i = ix;
        j = iy; 
        if( i<8 ) i++; else { j++; i=0; }
        if( FixCellAt(i,j) ) return 1;
      }
    }
    return 0; // Cannot find a value. Must change the previous cell.
  }
}

And one more, just for good measure:

#include <cstdio>
#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    using namespace std;
    ifstream getnum;
    int sudoku[9][9][10];
    int count1,count2,count3,count4,temp,test,trial;
    int remove[9][9];
	int ukodus[9][9][10];
    int guess[9][9];
    
    /*Get Numbers*/
    getnum.open("filenumbers.txt");
    for(count1=0;count1<9;count1++)
    {
       for(count2=0;count2<9;count2++)
       {
         getnum>>sudoku[count1][count2][9];
       }
    }
    
    /*Output Grid*/
    cout<<"You entered this grid: "<<endl;
    
    for(count1=0;count1<9;count1++)
    {
       for(count2=0;count2<9;count2++)
       {
       cout<<sudoku[count1][count2][9]<<" ";
       }
       cout<<endl;
    }
    
    /*Start Trial to eliminate after possibilites eliminated*/
  for(trial=0;trial<=20;trial++)
  {
    
    /*Store Possibilities*/
       for(count1=0;count1<=8;count1++)
       {
         for(count2=0;count2<=8;count2++)
         {
           if(sudoku[count1][count2][9]==0)
           {
             for(count3=0;count3<=8;count3++)
             {
               sudoku[count1][count2][count3]=count3+1;
             }
           }
           else 
           {
             for(count3=0;count3<=8;count3++)
             {
             sudoku[count1][count2][count3]=0;
             }
           }
          }   
       }
       
       /*eliminate by looking at rows and columns*/
      for(count1=0;count1<=8;count1++)
      {
        for(count2=0;count2<=8;count2++)
        {
          if(sudoku[count1][count2][9]!=0)
          {
            temp=sudoku[count1][count2][9];
            temp--;
            for(count3=0;count3<=8;count3++)
            {
              sudoku[count1][count3][temp]=0;
              sudoku[count3][count2][temp]=0;
            }
          }
        }
      }
    /*eliminate by looking at 3 by 3 squares (this part takes a while). Due to the fact that a 9x9 grid is made of 
      3x3 squares, a pattern between these grids was implemented in the for loops. However, each box of the 3x3 grids 
      must be delt with seperately because of differing patterns.*/
    for(count1=0;count1<=8;count1++)
      {
        for(count2=0;count2<=8;count2++)
        {
          if(sudoku[count1][count2][9]!=0)
          {
            temp=sudoku[count1][count2][9];
            temp--;
            
            if(count1%3==0)
            {
              if(count2%3==0)
              {
                sudoku[count1][count2+1][temp]=0;
                sudoku[count1][count2+2][temp]=0;
                sudoku[count1+1][count2][temp]=0;
                sudoku[count1+1][count2+1][temp]=0;
                sudoku[count1+1][count2+2][temp]=0;
                sudoku[count1+2][count2][temp]=0;
                sudoku[count1+2][count2+1][temp]=0;
                sudoku[count1+2][count2+2][temp]=0;
              }
            }
            if(count1%3==0)
            {
              if(count2%3==1)
              {
                sudoku[count1][count2+1][temp]=0;
                sudoku[count1][count2-1][temp]=0;
                sudoku[count1+1][count2][temp]=0;
                sudoku[count1+1][count2+1][temp]=0;
                sudoku[count1+1][count2-1][temp]=0;
                sudoku[count1+2][count2][temp]=0;
                sudoku[count1+2][count2+1][temp]=0;
                sudoku[count1+2][count2-1][temp]=0;
              }
            }
            if(count1%3==0)
            {
              if(count2%3==2)
              {
                sudoku[count1][count2-2][temp]=0;
                sudoku[count1][count2-1][temp]=0;
                sudoku[count1+1][count2][temp]=0;
                sudoku[count1+1][count2-1][temp]=0;
                sudoku[count1+1][count2-2][temp]=0;
                sudoku[count1+2][count2][temp]=0;
                sudoku[count1+2][count2-1][temp]=0;
                sudoku[count1+2][count2-2][temp]=0;
              }
            }
            if(count1%3==1)
            {
              if(count2%3==0)
              {
                sudoku[count1][count2+1][temp]=0;
                sudoku[count1][count2+2][temp]=0;
                sudoku[count1-1][count2][temp]=0;
                sudoku[count1-1][count2+1][temp]=0;
                sudoku[count1-1][count2+2][temp]=0;
                sudoku[count1+1][count2][temp]=0;
                sudoku[count1+1][count2+1][temp]=0;
                sudoku[count1+1][count2+2][temp]=0;
              }
            }
            if(count1%3==1)
            {
              if(count2%3==1)
              {
                sudoku[count1][count2+1][temp]=0;
                sudoku[count1][count2-1][temp]=0;
                sudoku[count1-1][count2][temp]=0;
                sudoku[count1-1][count2+1][temp]=0;
                sudoku[count1-1][count2-1][temp]=0;
                sudoku[count1+1][count2][temp]=0;
                sudoku[count1+1][count2+1][temp]=0;
                sudoku[count1+1][count2-1][temp]=0;
              }
            }
            if(count1%3==1)
            {
              if(count2%3==2)
              {
                sudoku[count1][count2-2][temp]=0;
                sudoku[count1][count2-1][temp]=0;
                sudoku[count1+1][count2][temp]=0;
                sudoku[count1+1][count2-1][temp]=0;
                sudoku[count1+1][count2-2][temp]=0;
                sudoku[count1-1][count2][temp]=0;
                sudoku[count1-1][count2-1][temp]=0;
                sudoku[count1-1][count2-2][temp]=0;
              }
            }
            if(count1%3==2)
            {
              if(count2%3==0)
              {
                sudoku[count1][count2+1][temp]=0;
                sudoku[count1][count2+2][temp]=0;
                sudoku[count1-1][count2][temp]=0;
                sudoku[count1-1][count2+1][temp]=0;
                sudoku[count1-1][count2+2][temp]=0;
                sudoku[count1-2][count2][temp]=0;
                sudoku[count1-2][count2+1][temp]=0;
                sudoku[count1-2][count2+2][temp]=0;
              }
            }
            if(count1%3==2)
            {
              if(count2%3==1)
              {
                sudoku[count1][count2-1][temp]=0;
                sudoku[count1][count2+1][temp]=0;
                sudoku[count1-1][count2][temp]=0;
                sudoku[count1-1][count2+1][temp]=0;
                sudoku[count1-1][count2-1][temp]=0;
                sudoku[count1-2][count2][temp]=0;
                sudoku[count1-2][count2+1][temp]=0;
                sudoku[count1-2][count2-1][temp]=0;
              }
            }
            if(count1%3==2)
            {
              if(count2%3==2)
              {
                sudoku[count1][count2-1][temp]=0;
                sudoku[count1][count2-2][temp]=0;
                sudoku[count1-1][count2][temp]=0;
                sudoku[count1-1][count2-1][temp]=0;
                sudoku[count1-1][count2-2][temp]=0;
                sudoku[count1-2][count2][temp]=0;
                sudoku[count1-2][count2-1][temp]=0;
                sudoku[count1-2][count2-2][temp]=0;
              }
            }
          }
        }
      }
      /*solving after possibilities are removed*/
      
      for(count1=0;count1<=8;count1++)
      {
        for(count2=0;count2<=8;count2++)
        {
          remove[count1][count2]=0;
        }
      }
      
      for(count1=0;count1<=8;count1++)
      {
        for(count2=0;count2<=8;count2++)
        {
           for(count3=0;count3<=8;count3++)
           {
              if(sudoku[count1][count2][count3]!=0)
              {
                remove[count1][count2]++;
              }
           }
        }
      }
      
      for(count1=0;count1<=8;count1++)
      {
        for(count2=0;count2<=8;count2++)
        {
           if(remove[count1][count2]==1)
           {
              for(count3=0;count3<=8;count3++)
              {
                 if(sudoku[count1][count2][count3]!=0)
                 {
                    sudoku[count1][count2][9]=sudoku[count1][count2][count3];                             
                 }
              }
           }
        }
      }
      
 }
      /*Store another array like this one for guessing*/
      for(count1=0;count1<=8;count1++)
      {
        for(count2=0;count2<=8;count2++)
        {
          for(count3=0;count3<=8;count3++)
          {
            ukodus[count1][count2][count3]=sudoku[count1][count2][count3];
          }
        }
      }  
      
      
      /*Let the guessing begin!! Begin with numbers that only have two possibilities and pick one*/
      for(count1=0;count1<=8;count1++)
      {
        for(count2=0;count2<=8;count2++)
        {
          if(remove[count1][count2]==2)
          {
            for(count3=0;count3<=8;count3++)
            {
              if(ukodus[count1][count2][count3]!=0)
              {
                ukodus[count1][count2][9]=ukodus[count1][count2][count3];
                guess[count1][count2]=ukodus[count1][count2][count3];
              }
            }
          }
         }
        }  
        /*if we guessed right, solve this and be done with it*/
        temp=1;
        for(count1=0;count1<=8;count1++)
        {
          for(count2=0;count2<=8;count2++)
          {
           if(udokus[count1][count2][9]==0)
             {
             temp=0;
             }
           }  
         }
         if(temp==1)
         {
            for(count1=0;count1<=8;count1++)
            {
              for(count2=0;count2<=8;count2++)
              {
                for(count3=0;count3<=8;count3++)
                {
                  sudoku[count1][count2][count3]=ukodus[count1][count2][count3];
                }
              }
             }  
          }
      /*If we guessed wrong restore to original*/
      if(temp==0)
      {
        for(count1=0;count1<=8;count1++)
        {
              for(count2=0;count2<=8;count2++)
              {
                for(count3=0;count3<=8;count3++)
                {
                  ukodus[count1][count2][count3]=sudoku[count1][count2][count3];
                }
              }  
          }
        }
        /*guess another number*/
        if(temp==0)
        {
          for(count1=0;count1<=8;count1++)
          {
              for(count2=0;count2<=8;count2++)
              {
                for(count3=0;count3<=8;count3++)
                {
                  ukodus[count1][count2][count3]=sudoku[count1][count2][count3];
                }
              }  
          }
        }  
        
      /*break if finished*/
      /*if(temp==1)
      {
        break;
      }*/
      
      
      
      /*Test Row d*/
       for(count2=0;count2<=8;count2++)
       {
         cout<<" Row: 4 Column: "<<count2+1<<endl;
         for(count3=0;count3<=9;count3++)
         {
           cout<<count3+1<<"="<<sudoku[3][count2][count3]<<",";
         }
         cout<<endl;
       }
       cout<<"Answer: "<<endl; 
       /*Output final grid*/
       for(count1=0;count1<9;count1++)
       {
         for(count2=0;count2<9;count2++)
         {
           cout<<sudoku[count1][count2][9]<<" ";
         }
           cout<<endl;
       }
       
    system("Pause");
    return 0;
}

Please help me either get the one with the class working or incorporate a class into the other ones and get them working (they seem to have fewer errors, but no class equals zero points)

And, before you ask, yes - the second one was copied off of the internet. I am not going to use it, but if the others won't work, I'll try modifying it enough to-where it isn't plagiarism anymore.

Any help/suggestions would be greatly appreciated.

Thanks, Kris

 

[kyeana]

I remember doing something like this is java a year or so ago in college, it was a pretty fun assignment.

What we did was use a recursive backtracking solution (aka a brute force solution). It was fairly simply to write once you understood what was going on, and didn't require any advanced knowledge of how to solve sudokus.

That second piece of code you posted seems to be using a backtracking solution.

The basics of solving a sudoku this was is:

1. start at the first empty cell, and put 1 in it.
2. Check the entire board, and see if there are any conflicts
3. If there are coflicts on the board, increase the number in the current cell by 1 (so change 1 to 2, 2 to 3, etc)
4. If the board is clean move, start at step one again.
5. If all nine possible numbers on a given cell cause a conflict in the board, then you set this cell back to empty, go back to the previous cell, and start again from step 3 (this is where the 'backtracking' comes in).

Once every cell have a number in it and there are no conflicts on the board, you have a solved sudoku.

I would recommend understanding this concept, and planning a way to solve it (in my opinion, recursion lends itself nicely to this solution). Once you have that, then start coding it, and post back if you run into any specific problems in your code (My forewarning - you should no that no one here is going to write your code for you, especially for school work)

Good luck

 

[Bruceification73]

All right, thank you for your input. How well is recursive backtracking implemented into a class? Is that fairly simple?

 

[kyeana]

It is, you just need to make sure you understand how all this works.

What you have to remember is that when using recursion, it is naturally 'unwinding'. In this sudoku problem for example, if you get through all 9 numbers on a given cell, and then let the current recursive call finish without calling another one, the you will end up right where you left off at the previous function (aka where you made this recursive call from).

This is why recursion makes a very natural solution for backtracking problems. Because of the nature of recursion, it can pretty much take care of the actual 'backtracking' part of the solution for you.

The main code used to solve this isn't very long at all. Just insure you make good use of helper methods (such as checking if the board has any conflicts in it, etc). It may help you to write up the actually backtracking solution in pseudo code first, and then write up the actual code complete with all the helper methods.

Good luck

 

[Bruceification73]

Update:

Well, I tried many different variations on the second and third ones, and decided to go with the third one, seeing as how it's the only one I can get to work. I have not yet implemented a class, but I can do that. Thank you, kyeana, for your recommendations, but I couldn't get the other one working.

Btw, I am in an advanced college programming class with almost no programming experience, so now you may understand why I couldn't get a simple recursive program working. Although I did not use your recommendation, I am selecting it as best answer because it was a good one, and because no one else even posted anything.

 

[Bruceification73]

WTF??? The best answer button is not working, I tried it like 8 times, and refreshed the page and everything. I will try again later.

 

[randomizer]

Best answer selected by randomizer.

 

[Bruceification73]

Thanks, randomizer.

 

[kyeana]

Ha, no worries If you do run in to any trouble you can always post back here for specific help.

Good luck

 

[Zenthar]

THAT post should be a reference for all people that would like help for school assignments. Thanks Bruceification73 for giving me back some faith in future coworkers.

 

[Bruceification73]

THAT post should be a reference for all people that would like help for school assignments. Thanks Bruceification73 for giving me back some faith in future coworkers.

Well, unfortunately I won't be working in Montreal any time soon, but thanks for your kind words. I am thinking of getting a summer job at a computer repair shop in town, but that's here in Colorado, U.S.

 

[Cool Ambivert]

Check this out...



#include <iostream.h>
#include <conio.h>
int array[9][9];
int outputArray[9][9];
int input_value(int x, int y, int value)
{
int i,j;
for (i = 0; i < 9; i++)
{
if (value == outputArray[y] || value == outputArray[x])
{
return 0;
}
}
if (x < 3)
{
if (y < 3)
{
for (i = 0; i < 3; i++)
{
for (j = 0; j < 3; j++)
{
if (value == outputArray[j])
{
return 0;
}
}
}
}
else if (y < 6)
{
for (i = 0; i < 3; i++)
{
for (j = 3; j < 6; j++)
{
if (value == outputArray[j])
{
return 0;
}
}
}
}
else
{
for (i = 0; i < 3; i++)
{
for (j = 6; j < 9; j++)
{
if (value == outputArray[j])
{
return 0;
}
}
}
}
}
else if (x < 6)
{
if (y < 3)
{
for (i = 3; i < 6; i++)
{
for (j = 0; j < 3; j++)
{
if (value == outputArray[j])
{
return 0;
}
}
}
}
else if (y < 6)
{
for (i = 3; i < 6; i++)
{
for (j = 3; j < 6; j++)
{
if (value == outputArray[j])
{
return 0;
}
}
}
}
else
{
for (i = 3; i < 6; i++)
{
for (j = 6; j < 9; j++)
{
if (value == outputArray[j])
{
return 0;
}
}
}
}
}
else
{
if (y < 3)
{
for (i = 6; i < 9; i++)
{
for (j = 0; j < 3; j++)
{
if (value == outputArray[j])
{
return 0;
}
}
}
}
else if (y < 6)
{
for (i = 6; i < 9; i++)
{
for (j = 3; j < 6; j++)
{
if (value == outputArray[j])
{
return 0;
}
}
}
}
else
{
for (i = 6; i < 9; i++)
{
for (j = 6; j < 9; j++)
{
if (value == outputArray[j])
{
return 0;
}
}
}
}
}
return value;
}
int backtrack(int x, int y)
{
int temp,i,j;
if (outputArray[x][y] == 0)
{
for (i = 1; i < 10; i++)
{
temp = input_value(x,y,i);
if (temp > 0)
{
outputArray[x][y] = temp;
if (x == 8 && y == 8)
{
return 1;
}
else if (x == 8)
{
if (backtrack(0,y+1))
return 1;
} else {
if (backtrack(x+1,y)) return 1 ;
}
}
}
if (i == 10) {
if (outputArray[x][y] != array[x][y]) outputArray[x][y] = 0;
return 0;
}
} else {
if (x == 8 && y == 8) {
return 1;
} else if (x == 8) {
if (backtrack(0,y+1)) return 1;
} else {
if (backtrack(x+1,y)) return 1;
}
}
return 0;
}
void main()
{
clrscr();
int i,j;
cout<<"Original outputArray\n";
for (i = 0; i < 9; i++)
{
for (j = 0; j < 9; j++)
{
cin>>array[j];
}
}
clrscr();
cout<<"Puzzle is \n";
for (i = 0; i < 9; i++) {
for (j = 0; j < 9; j++) {
outputArray[j] = array[j];
}
}
for (i = 0; i < 9; i++) {
for (j = 0; j < 9; j++) {
cout<<"\t"<<array[j];

}
cout<<"\n";
}
if (backtrack(0,0)) {
cout<<"Soln is :\n";
for (i = 0; i < 9; i++) {
for (j = 0; j < 9; j++) {
cout<<"\t"<< outputArray[j];
}
cout<<"\n";
}
} else
cout<<"No Soln\n";
getch();
}

 

[Dark Lord of Tech]

This topic has been closed by Area51reopened