Sudoku solving algorithm

[supahamster]

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.

{
	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];
			}
		}
	}
}

[D_Drmmr]

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

Array indices are zero-based in C++. You should have:

int smatrix[9][9][9];
for (int x = 0; x < 9; ++x) {
	for (int y = 0; y < 9; ++y) {
		for (int z = 0; z < 9; ++z) {
			smatrix[x][y][z] = 0;
		}
	}
}

[supahamster]

I know this. I just made it start at 1 for my own purposes, and it is uniform throughout. The only disadvantage is a little bit of wasted space, but that is not the problem, because as I said before, I make this "mistake" uniformly.

Also, for some reason what I have right now will correctly get the grid for the number "1" but not for any other. You can check this by doing the following:
download the full file (attached)
In int main(), within the for loop, there are two lines, "dispmatrix();" and "dispothermatrix();" one of which is commented. Switch the comment from one to the other, then compile and run. It will display the grids and you can look at them to find the problem.

Again, 0s mean that the number CAN be there, and 1s mean that they CAN'T. (sorry XD)

[OReubens]

Nice idea... but it will only solve sudoku's where you always have at least one cell with only 1 possible value.

Some of the more advanced sudoku's require you to make several "what if" type decisions to come to the conclusion that the "what if" decisions were wrong, or are proven to be right.

[Amleto]

he knows:

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.

[supahamster]

This isn't very helpful so far... Which either means the code I have is fine, or that people just aren't finding it, either of which mean I have to go back and do MORE troubleshooting.

If anyone spots anything that might be the problem (and it's not the for loops being 1-based not 0-based) PLEASE tell me. Thanks.

Follow the instructions in my previous post to see for yourself what is the problem. It's something about the setting of the 3-d grid, because the grid is incorrect when I have the program display it.

Not sure if I already said this, but it works for some numbers, but not others, which makes the whole thing even worse. A single number in this puzzle gets solved--the one in the lower-left area of the grid.

Thanks in advance if anyone can help.

[alanjhd08]

Hi,

Perhaps

	for(int n=1;n<10;n++)
	{
		smatrix[x][n][currentnum]=1;		//set horizontal & vertical
		smatrix[n][x][currentnum]=1;

	}

should be:

	for(int n=1;n<10;n++)
	{
		smatrix[x][n][currentnum]=1;		//set horizontal & vertical
		smatrix[n][y][currentnum]=1;
	}

[D_Drmmr]

If anyone spots anything that might be the problem (and it's not the for loops being 1-based not 0-based) PLEASE tell me. Thanks.

Follow the instructions in my previous post to see for yourself what is the problem. It's something about the setting of the 3-d grid, because the grid is incorrect when I have the program display it.

I don't believe you actually said what the problem is. Does the application crash? If so, did you step through it with a debugger? At which line does it crash?
Or is there a logical error in the program?

[supahamster]

I did say what the problem is; it's that smatrix is incorrect. And also, I am not on my home computer now, so I am unable to test if alanjhd08 is right, but that should do it.

I hope this will fix it. Thanks

[supahamster]

Sorry for the double-post, but I need to bump this because of the new information.

Okay. smatrix is now correct (at least I think it is--haven't tested completely, but it should be).

The new problem: THIS ALWAYS RETURNS FALSE

here's basically how it works now:
As far as I know, it should work, but it doesn't.

for each unique place in all 3 dimensions of smatrix:
     if the current spot is '0' meaning the it is a legit spot for the 'z' value

          boolean 'correctnum' is set to true
               it tests if the spot is the only one possible for its row
          if the previous returned false (meaning there are multiple possibilities in the row)
               correctnum is set back to true and it tests if the spot is the only one in its column
          if the previous returned false
               correctnum is set back to true and it tests the square

          if correctnum is still true, it sets z to tempmatrix[x][y], tests that, and if that is true
          it sets that value to matrix.

Thus if any of these return true, it skips to the end with the if statements.

^ I think the problem is here in the last bit

It needs to be this way because if the number passes ANY of the tests it is the correct number; it does not need to pass ALL of them.


I did not change the rest of the code. To substitute this into the program (attached to the first post), simply copy the code below into the bottom of the solve() function. It should replace everything below the line of
///////////////let the solving begin///////////

Sorry about the lack of comments on the code. I think I explained what I'm trying to accomplish well enough.

Thanks

	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 (correctnum = false)
					{
						correctnum = true;
						for(int n=1;n<10;n++)
						{
							if(x!=n)
							{
								if(smatrix[n][y][z]==0)
								{
									correctnum=false;
								}
							}
						}
					}

					int cx=x-((x-1)&#37;3),
						cy=y-((y-1)%3);
					if (correctnum = false)
					{
						correctnum = true;
						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(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];
			}
		}
	}

[Paul McKenzie]

Sorry for the double-post, but I need to bump this because of the new information.

Okay. smatrix is now correct (at least I think it is--haven't tested completely, but it should be).

The new problem: THIS ALWAYS RETURNS FALSE

I will repeat a previous post to you:

If so, did you step through it with a debugger?

Programming isn't just writing the program and running it, and then have one of us do the heavy lifting by debugging it for you. A major part of it is also learning to debug your programs. You've written the code, so it's up to you to determine where something goes wrong, why it goes wrong, what it should have done, etc. If this is a homework assignment, learning to debug for yourself is mandatory for students, even if it wasn't stated to you explicitly.

Since you're posting this in the Visual C++ forum (when actually it should be posted in the non-Visual C++ forum, since there is nothing Visual C++ specific about the code), you have access to one of the best debuggers ever developed for a compiler. There really is no excuse for not using it, or learning to use it. That is exactly what most here are doing when you give us a program, so maybe you should learn this for yourself.

Regards,

Paul McKenzie

[alanjhd08]

Hi,

And when you step through it with a debugger, note that lines like this:

    if (x = true)

will always set x to true.

This is a very common type of mistake. If you write

    if (true == x)

then you will get a compiler error if you accidentally leave out the second equals.

Alan

[supahamster]

I did not step through it with the debugger because to look at every loop I would have to click the button many times (to be exact 9x9x9x10 at the smallest, or more depending on the loop) and look at the value. I did use various tests, however, to check if it worked (wherever there is commented code, and plus a little that I may have deleted) and this is how I know that it doesn't work.
But in addition to that, what I have done is read through the code several times looking for syntax errors, etc. and I have fixed any that I know of. The reason I am posting this is because other people can spot things that the original programmer (myself in this case) cannot.
Also, the reason I wrote basically what I am trying to accomplish in English at the top of the lat post is exactly that reason; so that other people might notice if I'm telling the program to do something other than what I want it to do.
Also, no I am not taking a c++ class, but I do understand the importance of debugging, and I try to debug my own programs. What I have here is the result of various different attempts which I found not to work through my own debugging. I have been programming for just a few months in my spare time only, but I'm trying to improve in any way I can.

Also, I posted in this forum because I am using Visual C++, I don't know what makes a program unique to that though.

[Paul McKenzie]

I did not step through it with the debugger because to look at every loop I would have to click the button many times (to be exact 9x9x9x10 at the smallest, or more depending on the loop) and look at the value.

So how do other programmers, like some of the ones helping you here, debug programs that have thousands, if not millions of lines, hundreds, if not thousands of separate functions, hundreds of separate modules, etc? I have loops in my programs that execute thousands of times.

We all use the debugger -- again, there is no excuse to not use it.

There are ways to set breakpoints, conditional, hit count, you could have even written a small if() statement that did this:

if ( whatever_condition )
{
   int x = 0;
   x = x;
}

And have the whatever_condition be true when you get to one particular part in the loop and set a breakpoint in the if().

The bottom line that anyone you see helping you in this thread, it is more than likely that they are using the debugger.

Also, I posted in this forum because I am using Visual C++, I don't know what makes a program unique to that though.

The code you posted is generic C++. It is not Visual C++ specific in that it uses no MFC, ATL, Windows function calls, etc.

Regards,

Paul McKenzie

[supahamster]

As I stated in the previous post: I have looked through the code several times, and I cannot spot the problem. I think it may be a logical error, but as far as I can tell, there is none. Seeing as I am not in a c++ class and do not have anyone else to refer to (I ran this by my friend and he didn't spot any errors either), will anyone give me some suggestions as to how to go about debugging this, or tell me if there is a logical error in my method of solving?

Again: the program does not crash, but it never passes the last if statement of "if(correctnum==true)" even when I know there are several places on the grid where it should.

Thanks for the help and I hope to get better at debugging.