Thread: 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?

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';
}

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