sudoku

Thanks for the kind words, manav. :)

Element.usha: Do your possibles list only the possibles for each square, for all these: row, column, and box?

thank you adak .......

the program:::

Code:

---


#include<iostream.h>
#include<stdio.h>

int input_sdk(void);
int chk_pos(int i,int j,int n);
int get_pos(void);
void print(void);
int must_be(void);
int ord_pair(void);
void reset_ord_i(int ,int ,int );
void reset_ord_j(int ,int ,int );
void reset_pos(void);
int a[10][10][10]={0};

int main()
{
        int suc1,suc2;
        input_sdk();
        for(int cnt=0;cnt<=100;cnt++)
        {
        do{
                reset_pos();
                get_pos();
                suc1=must_be();
        }while(suc1==1);
        suc2=ord_pair();
        print();
        }
        print();
        return 0;
}

int input_sdk(void)
{
        int rown,coln,n;
        cout<<"enter rown coln n :0 to exit:";
        do{
                cin>>rown>>coln>>n;
                if(rown>9 || coln>9 || n>9 || n<1)
                        cout<<"invalid input";
                else
                        a[rown-1][coln-1][0]=n;
        }while(n!=0 && rown!=0);
        return 0;
}

int get_pos(void)
{
        int i,j,k;
        for(i=0;i<9;i++)
        {
                for(j=0;j<9;j++)
                {
                        k=1;
                        if(a[i][j][0]==0)
                        {
                                for(int num=1;num<=9;num++)
                                {
                                        if(chk_pos(i,j,num)!=0)
                                                a[i][j][k++]=num;
                                }
                        }
                }
        }
        return 0;
}

int must_be(void)
{
        int i,j,success=0;
        for(i=0;i<9;i++)
                for(j=0;j<9;j++)
                        if(a[i][j][0]==0)
                        {
                                if(a[i][j][2]==0)
                                {
                                        a[i][j][0]=a[i][j][1];
                                        success=1;
                                }
                        }
        return (success);
}
int ord_pair(void)
{
        int i,j,k,pos,success=0;
        for(i=0;i<9;i++)
        {
                pos=-1;
                for(j=0;j<9;j++)
                {
                        if(pos==-1 && a[i][j][3]==0)
                                pos=j;
                        else if(a[i][j][3]==0 && pos!=-1)
                        {
                                if(a[i][pos][1]==a[i][j][1] && a[i][pos][2]==a[i][pos][2])
                                {
                                        reset_ord_i(i,a[i][j][1],a[i][j][2]);
                                        must_be();
                                        success=1;
                                }
                        }
                }
        }
        for(j=0;j<9;j++)
        {
                pos=-1;
                for(i=0;i<9;i++)
                {
                        if(pos==-1 && a[i][j][3]==0)
                                pos=i;
                        else if(a[i][j][3]==0 && pos!=-1)
                        {
                                if(a[i][pos][1]==a[i][j][1] && a[i][pos][2]==a[i][pos][2])
                                {
                                        reset_ord_j(j,a[i][j][1],a[i][j][2]);
                                        must_be();
                                        success=1;
                                }
                        }
                }
        }
        return success;
}
int chk_pos(int i,int j,int n)
{
        int suc=0;
        for(int col=0;col<9;col++)
                if(a[i][col][0]==n)
                {
                        suc=1;break;
                }
        for(int row=0;row<9;row++)
                if(a[row][j][0]==n)
                {
                        suc=1;break;
                }
        i=i/3;j=j/3;
        for(row=3*i;row<3*(i+1);row++)
                for(col=3*j;col<3*(j+1);col++)
                        if(a[row][col][0]==n)
                                suc=1;
        if(suc==0)
                return n;
        else
                return 0;
}

void reset_pos(void)
{
        int i,j,k;
        for(i=0;i<9;i++)
                for(j=0;j<9;j++)
                        for(k=1;k<=9;k++)
                                a[i][j][k]=0;
}

void reset_ord_i(int i,int x,int y)
{
        int j,k,t;
        for(j=0;j<9;j++)
        {
                if(a[i][j][3]!=0)
                {
                        for(k=1;k<=9;k++)
                        {
                                if(a[i][j][k]==x || a[i][j][k]==y)
                                {
                                        t=k;
                                        while(a[i][j][t]!=0)
                                        {
                                                a[i][j][t]=a[i][j][t+1];
                                                t++;
                                        }
                                }
                        }
                }
        }
}
void reset_ord_j(int j,int x,int y)
{
        int i,k,t;
        for(i=0;i<9;i++)
        {
                if(a[i][j][3]!=0)
                {
                        for(k=1;k<=9;k++)
                        {
                                if(a[i][j][k]==x || a[i][j][k]==y)
                                {
                                        t=k;
                                        while(a[i][j][t]!=0)
                                        {
                                                a[i][j][t]=a[i][j][t+1];
                                                t++;
                                        }
                                }
                        }
                }
        }
}
void print(void)
{
        for(int i=0;i<9;i++)
        {
                for(int j=0;j<9;j++)
                {
                        if(a[i][j][0]==0)
                        {
                                int k=1;
                                cout<<"\t"<<i+1<<j+1<<"pos:";
                                while(a[i][j][k]!=0)
                                        cout<<a[i][j][k++];
                        }
                }
        }
        cout<<"\n\n";
        for(i=0;i<9;i++)
        {
                cout<<"\n";
                for(int j=0;j<9;j++)
                        cout<<a[i][j][0]<<" ";
        }
}

---

A few improvements. Mostly just to save time while de-bugging. Try them out.

Code:

---

/* SudokuEL.cpp, by ElemenT.usha
Status: checking possibles and promotion of "solo's", logic.
EZ game is shown as having two 6's in row 3, and two 2's in column 1.
*/
#include<iostream.h>
#include<stdio.h>

int input_sdk(void);
int chk_pos(int i,int j,int n);
int get_pos(void);
void print(void);
int must_be(void);
int ord_pair(void);
void reset_ord_i(int ,int ,int );
void reset_ord_j(int ,int ,int );
void reset_pos(void);
int a[10][10][10]={0};

int main()
{
  int suc1,suc2;
        input_sdk();
        for(int cnt=0;cnt<=100;cnt++)
        {
        do{
                reset_pos();
                get_pos();
                suc1=must_be();
        }while(suc1==1);
        suc2=ord_pair();
        print();
        }
        print();
  cout << "\n\n\t\t\tProgram Complete, Press Enter";
  suc2 = getchar();  //just to hold the window open for viewing
  putchar(suc2);    //stops a stupid warning

        return 0;
}

int input_sdk(void)
{
  int rown,coln,n;
  char load = 'y';
  //cout << "Load EZ puzzle y/n? ";
  //cin >> load;
  if (load == 'y' || load == 'Y')  {
      a[0][2][0]=8; a[1][1][0]=5; a[1][3][0]=1; a[1][6][0]=7; a[1][8][0]=9;
      a[2][1][0]=3; a[2][3][0]=9; a[2][4][0]=7; a[2][7][0]=4; a[2][8][0]=1;
      a[3][1][0]=1; a[3][3][0]=7; a[4][2][0]=5; a[4][3][0]=9; a[4][5][0]=8;
      a[4][6][0]=1; a[5][5][0]=2; a[5][7][0]=3; a[6][0][0]=8; a[6][1][0]=9;
      a[6][4][0]=4; a[6][6][0]=5; a[6][7][0]=2; a[7][0][0]=7; a[7][2][0]=4;
      a[7][5][0]=1; a[7][7][0]=8; a[8][6][0]=9;
  }
  else  {
          cout<<"enter rown coln n :0 to exit:";
          do{
                  cin>>rown>>coln>>n;
                  if(rown>9 || coln>9 || n>9 || n<1)
                          cout<<"invalid input";
                  else
                          a[rown-1][coln-1][0]=n;
          }while(n!=0 && rown!=0);
  }
        return 0;
}

int get_pos(void)
{
        int i,j,k;
        for(i=0;i<9;i++)
        {
                for(j=0;j<9;j++)
                {
                        k=1;
                        if(a[i][j][0]==0)
                        {
                                for(int num=1;num<=9;num++)
                                {
                                        if(chk_pos(i,j,num)!=0)
                                                a[i][j][k++]=num;
                                }
                        }
                }
        }
        return 0;
}

int must_be(void)
{
        int i,j,success=0;
        for(i=0;i<9;i++)
                for(j=0;j<9;j++)
                        if(a[i][j][0]==0)
                        {
                                if(a[i][j][2]==0)
                                {
                                        a[i][j][0]=a[i][j][1];
                                        success=1;
                                }
                        }
        return (success);
}
int ord_pair(void)
{
        int i,j,k,pos,success=0;
        for(i=0;i<9;i++)
        {
                pos=-1;
                for(j=0;j<9;j++)
                {
                        if(pos==-1 && a[i][j][3]==0)
                                pos=j;
                        else if(a[i][j][3]==0 && pos!=-1)
                        {
                                if(a[i][pos][1]==a[i][j][1] && a[i][pos][2]==a[i][pos][2])
                                {
                                        reset_ord_i(i,a[i][j][1],a[i][j][2]);
                                        must_be();
                                        success=1;
                                }
                        }
                }
        }
        for(j=0;j<9;j++)
        {
                pos=-1;
                for(i=0;i<9;i++)
                {
                        if(pos==-1 && a[i][j][3]==0)
                                pos=i;
                        else if(a[i][j][3]==0 && pos!=-1)
                        {
                                if(a[i][pos][1]==a[i][j][1] && a[i][pos][2]==a[i][pos][2])
                                {
                                        reset_ord_j(j,a[i][j][1],a[i][j][2]);
                                        must_be();
                                        success=1;
                                }
                        }
                }
        }
        return success;
}
int chk_pos(int i,int j,int n)
{
        int suc=0;
        for(int col=0;col<9;col++)
                if(a[i][col][0]==n)
                {
                        suc=1;break;
                }
        for(int row=0;row<9;row++)
                if(a[row][j][0]==n)
                {
                        suc=1;break;
                }
        i=i/3;j=j/3;
        for(row=3*i;row<3*(i+1);row++)
                for(col=3*j;col<3*(j+1);col++)
                        if(a[row][col][0]==n)
                                suc=1;
        if(suc==0)
                return n;
        else
                return 0;
}

void reset_pos(void)
{
        int i,j,k;
        for(i=0;i<9;i++)
                for(j=0;j<9;j++)
                        for(k=1;k<=9;k++)
                                a[i][j][k]=0;
}

void reset_ord_i(int i,int x,int y)
{
        int j,k,t;
        for(j=0;j<9;j++)
        {
                if(a[i][j][3]!=0)
                {
                        for(k=1;k<=9;k++)
                        {
                                if(a[i][j][k]==x || a[i][j][k]==y)
                                {
                                        t=k;
                                        while(a[i][j][t]!=0)
                                        {
                                                a[i][j][t]=a[i][j][t+1];
                                                t++;
                                        }
                                }
                        }
                }
        }
}
void reset_ord_j(int j,int x,int y)
{
        int i,k,t;
        for(i=0;i<9;i++)
        {
                if(a[i][j][3]!=0)
                {
                        for(k=1;k<=9;k++)
                        {
                                if(a[i][j][k]==x || a[i][j][k]==y)
                                {
                                        t=k;
                                        while(a[i][j][t]!=0)
                                        {
                                                a[i][j][t]=a[i][j][t+1];
                                                t++;
                                        }
                                }
                        }
                }
        }
}
void print(void)
{
  int m = 0;
        for(int i=0;i<9;i++)
        {
                for(int j=0;j<9;j++)
                {
                        if(a[i][j][0]==0)
                        {
                                int k=1;
                                if(m++ &#37; 4 == 0)
                                  cout << "\n";
                                cout<<"\t"<<i+1<<j+1<<"pos:";
                                while(a[i][j][k]!=0)
                                        cout<<a[i][j][k++];
           
                        }
                }
        }
        cout<<"\n\n";
        for(i=0;i<9;i++)
        {
        if(i%3==0 && i > 1) {
          cout << "\n  ";
          cout << "---------------------";
        }
        cout<<"\n  ";
        for(int j=0;j<9;j++)  {
              if(j%3==0 && j > 1)
                    cout << "| ";
              cout<<a[i][j][0]<<" ";
        }
  }
  cout << '\n';
}

---

thanxxx dude... got the solution ... just tell me whether the code is completely generalised in every respect

how many different ways are there to code a sudoku solver???? i have seen the box, line. and row. the brute force, the better brute force and several other ways that i cant understand

How many threads do we need about sudoku?

Quote:

---

Originally Posted by Bubba

How many threads do we need about sudoku?

---

one for each idiot that tries to make a sudoku solver without any idea of which algorithms would be good at it (this includes my sudoku thread), and one more thread for everyone who knows what they're doing

so a little more than 5 billion then, which is around 3x as many as we currently have

Sorry, I did not realize how old this thread was before responding. Closed for obvious reasons.