CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 15 of 25

Threaded View

  1. #1
    Join Date
    Apr 2009
    Posts
    21

    Sudoku solving algorithm

    I wrote something to solve sudoku puzzles as practice in c++.
    The basic idea is that there is a secondary matrix (called smatrix) that is 3-dimensional. I think of it as layers of 2-dimensional sudoku's stacked on top of one another. In each layer, it has the sudoku board stored, only with 1's and 0's. A zero means that the number can be there, and a one means it can't (because I wasn't thinking when I made it, and I don't want to go back and switch them). Thus, each layer stores the possible places that [layer index] can go.
    From there, it finds places that can only be one digit, and it puts that digit there and starts over.
    I think that my problem is with the defining of smatrix, but I have looked over it several times and as far as I can tell it should work.
    Also--I know that this is not a complete solving algorithm. I have a lot more work to go, but this should solve easy puzzles.

    The code for the solving algorithm is posted below, and the full .cpp file is attached.
    Thanks.

    Code:
    {
    	for(int x=1;x<10;x++)
    	{
    		for(int y=1;y<10;y++)
    		{
    			for(int z=1;z<10;z++)
    			{
    				smatrix[x][y][z]=0;		//temporary grid = 0
    			}
    		}
    	}
    	//set the temporary grid for open possibilities
    	for(int x=1;x<10;x++)
    	{
    		for(int y=1;y<10;y++)
    		{
    			if(matrix[x][y]!=0)
    			{
    				for(int z=1;z<10;z++)
    				{
    					smatrix[x][y][z]=1;
    				}
    			}
    
    			int currentnum=matrix[x][y];
    			if(currentnum!=0)
    			{
    				for(int n=1;n<10;n++)
    				{
    					smatrix[x][n][currentnum]=1;		//set horizontal & vertical
    					smatrix[n][x][currentnum]=1;
    				}
    
    				//set squares
    				int cx=x-((x-1)%3),
    					cy=y-((y-1)%3);
    				for(int e=0;e<3;e++)
    				{
    					for(int i=0;i<3;i++)
    					{
    						smatrix[cx+e][cy+i][currentnum]=1;
    					}
    				}
    			}
    		}
    	}
    	/////////////////////////LET TEH SOLVIN BEGINNNNNNN//////////////////////////
    	for(int z=1;z<10;z++)
    	{
    		for(int x=1;x<10;x++)
    		{
    			for(int y=1;y<10;y++)
    			{
    				if(smatrix[x][y][z]==0)
    				{
    					bool correctnum=true;
    					for(int n=1;n<10;n++)
    					{
    						if(y!=n)
    						{
    							if(smatrix[x][n][z]==0)
    							{
    								correctnum=false;
    								//if(z==1&&x==1&&y==6)
    								//cout<<"FAIL IN TEH HORIZ"<<endl;
    							}
    						}
    						if(x!=n)
    						{
    							if(smatrix[n][y][z]==0)
    							{
    								correctnum=false;
    								//if(z==1&&x==1&&y==6)
    								//cout<<"FAIL IN TEH VERT"<<endl;
    							}
    						}
    					}
    
    					int cx=x-((x-1)%3),
    						cy=y-((y-1)%3);
    					for(int e=0;e<3;e++)
    					{
    						for(int i=0;i<3;i++)
    						{
    							if(cx+e != x && cy+i != y)
    							{
    								if(smatrix[cx+e][cy+i][z]==0)
    								{
    									correctnum=false;
    									//if(z==1&&x==1&&y==6)
    									//cout<<"FAIL IN TEH SQUAR"<<endl;
    								}
    							}
    						}
    					}
    
    					if(correctnum==true)
    					{
    						tempmatrix[x][y]=z;
    						//cout<<"yep"<<endl;
    					}
    				}
    			}
    		}
    	}
    
    	check();
    	if(cheat==true)
    		return(0);
    	else
    	{
    		for(int x=1;x<10;x++)
    		{
    			for(int y=1;y<10;y++)
    			{
    				matrix[x][y]=tempmatrix[x][y];
    			}
    		}
    	}
    }
    Attached Files Attached Files

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured