sudoku

This is a discussion on sudoku within the C++ Programming forums, part of the General Programming Boards category; Thanks for the kind words, manav. Element.usha: Do your possibles list only the possibles for each square, for all these: ...

  1. #16
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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?
    Last edited by Adak; 02-15-2008 at 06:23 AM.

  2. #17
    Registered User
    Join Date
    Nov 2007
    Posts
    73
    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]<<" ";
    	}
    }

  3. #18
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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';
    }
    Last edited by Adak; 02-15-2008 at 03:45 PM.

  4. #19
    Registered User
    Join Date
    Nov 2007
    Posts
    73
    thanxxx dude... got the solution ... just tell me whether the code is completely generalised in every respect

  5. #20
    Registered User bobknows's Avatar
    Join Date
    Jan 2011
    Location
    SD
    Posts
    87
    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

  6. #21
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    How many threads do we need about sudoku?

  7. #22
    Banned ಠ_ಠ's Avatar
    Join Date
    Mar 2009
    Posts
    687
    Quote Originally Posted by Bubba View Post
    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
    ╔╗╔══╦╗
    ║║║╔╗║║
    ║╚╣╚╝║╚╗
    ╚═╩══╩═╝

  8. #23
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    Sorry, I did not realize how old this thread was before responding. Closed for obvious reasons.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sudoku 4 by 4 combination lister?
    By iskate4 in forum C++ Programming
    Replies: 2
    Last Post: 02-19-2009, 12:56 PM
  2. malloc, structures, arrays and sudoku!!
    By AmbliKai in forum C Programming
    Replies: 13
    Last Post: 10-15-2008, 03:05 AM
  3. sudoku - arrays
    By rocketman50 in forum C++ Programming
    Replies: 2
    Last Post: 03-21-2008, 09:20 AM
  4. Help for a sudoku Solver
    By axilleask in forum C Programming
    Replies: 3
    Last Post: 11-26-2007, 03:28 PM
  5. Sudoku - the new addiction
    By axon in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 11-07-2005, 10:39 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21