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

---

Quote:

---

Originally Posted by supahamster

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

---

---

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

Code:

---

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

---

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)

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.

he knows:

Quote:

---

Originally Posted by supahamster

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.

---

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.

Hi,

Perhaps

Code:

---

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

        }

---

should be:

Code:

---

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

---

Quote:

---

Originally Posted by supahamster

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?

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

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.

Code:

---

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

Code:

---

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

---

Quote:

---

Originally Posted by 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

---

I will repeat a previous post to you:

Quote:

---

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

Hi,

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

Code:

---

    if (x = true)

---

will always set x to true.

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

Code:

---

    if (true == x)

---

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

Alan

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.

Quote:

---

Originally Posted by 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.

---

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:

Code:

---

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.

Quote:

---

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

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.

Quote:

---

Originally Posted by 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),

---

That's the problem. Very few human beings can "spot" errors without debugging the program, unless the error is so glaringly obvious. There are too many loops, variables, paths the code can take, etc. to make it even possible for anything but an extraordinary human being to try and figure out "by sight".

A trained programmer can look at just a few lines of code that they did not write (around 50, if that many) and tell if there is something logically wrong with it. If you're attempting to just "look" at the code and spot logical errors without stepping through the code, then you're better than most of the programmers that I know.

Programmers used to "hand debug", where they would step through the code with pencil and paper. This worked somewhat, but it is still error prone, as again, we're mere human beings -- we get tired, lose our place in the code, forget to write down stuff, etc. That's why interactive debuggers were developed, so as to eliminate the possiblity of these things happening when debugging a program.

Quote:

---

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?

---

We did. Single step through the program.

Again, you wrote the program, therefore you should know exactly what each step, loop, assignment, etc. is supposed to do at every step of execution. You know what is supposed to go in as input, and what is supposed to come out at the other end as the result, and hopefully you wrote the code using these suppositions. Now that you wrote the code and it is not doing what you want it to do, you inspect where the program starts to break down.

"What happens after this loop I wrote? Are the values correct? What is the value of this variable? It was supposed to be x, but it's y. It must be this loop -- yep, there is the problem". These are the questions that you should be asking yourself when debugging a program.

Quote:

---

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.

---

So now you know the end result, run the debugger and see why that last if() statement is not true.

Also, instead of telling us what to cut, paste, copy, etc. to get a working program, post the entire program that you are now using. It is less likely to have issues if we get the code from you without having to edit anything.

Regards,

Paul McKenzie

Quote:

---

Originally Posted by alanjhd08

Hi,

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

Code:

---

    if (x = true)

---

will always set x to true.

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

Code:

---

    if (true == x)

---

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

Alan

---

Supa, please take note of this post I've quoted above, it contains the answer to your problem regarding the nested for loops always returning false. The code you posted contains the following lines

Code:

---

if (correctnum = false)
                                        {

---

= is an assignment operator.

I found that, after I fixed the syntax error (blame Game Maker for that one, they allow you to do something like "if(x=2)" in their scripting), the function almost works correctly. To be more specific, the horizontal and vertical checks work fine, but not the square check. I know this because I did 3 things:
1. I did the sudoku by hand to find what numbers go where.
2. I used 'dispothermatrix()' to look at smatrix, and I did by hand what I want the program to do (I myself looked at rows, columns, and boxes, to find 0s that were standing alone) and I found that all of these were the correct numbers as checked by the sudoku I had completed.
3. Within 'if (correctnum==true)' I added something that would tell me the coordinates and the numbers of the spots that passed the tests, and which test it passed (horizontal, vertical, or square). Some of these matched my hand-solved sudoku, some didn't. I found that the ones that did match were the ones that passed either the horizontal or the vertical tests, and the ones that didn't match were the ones that passed the square test.

Thus, my problem should be in the square test. However, as far as checking every spot in the square, the programming is exactly the same as the one to set smatrix, which works fine. Also, as far as the test, it is the same as the horizontal and vertical tests.

The code to set the squares in smatrix (working)

Code:

---

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;

---

The code to check horizontal (working)

Code:

---

if (correctnum == false)
{
        correctnum = true;
        lastpassed="horizontal";

        for(int n=1;n<10;n++)
                if(x!=n)
                        if(smatrix[n][y][z]==0)
                                correctnum=false;

---

The code to check squares (not working)

Code:

---

int cx=x-((x-1)%3),
        cy=y-((y-1)%3);
if (correctnum == false)
{
        correctnum = true;
        lastpassed="square";

        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;

---

For example, compile and run the attachment. Note the first 4 lines after the initially displayed sudoku.

Quote:

---

1 at (8,3) passed: square
1 at (9,3) passed: square
cheat!!!! (8,3) = (9,3)
cheat!!!! (9,3) = (8,3)

---

This should not have passed the third test for the square, but it did.
Can someone tell me why this is not working, while the others are?

Thanks

Quote:

---

Originally Posted by supahamster

Can someone tell me why this is not working, while the others are?

---

Code:

---

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)

---

What is the value of cx, cy, and z when those lines are executed? What is the value of that position in the matrix? What do you expect them to be? What are their actual values when you debug the program?

Also on a side note, one and two letter variable names such as "e", "z" "cx", etc. makes the program harder to understand and to debug, making it more prohibitive for anyone to help. Make your variables have meaningful names so that even you will understand what they are supposed to denote when you look at your program 6 months from now.

I'm glad you found a solution to some of your problems. However, the issue stays the same -- you need to carefully debug the program using the debugger -- it still sounds like you're just writing something, and then hoping that it works. You wrote that loop expecting some values, but you didn't state anything about what values you're getting there, or your observations as to what is wrong in that loop.

Regards,

Paul McKenzie

Solved it! And I hate how simple it was.

Code:

---

if(cx+e != x && cy+i != y)

---

Had to be:

Code:

---

if(cx+e != y && cy+i != x)

---

I think this is because I was never completely clear with myself about which direction was x and which was y. I will make sure not to do THAT again...

Anyways, thanks Paul. I'm glad I found this and not someone else. By the way, did you know this was the problem all along? If so, thanks for not saying it, and if not...whatever.

If anyone wants to see the working program, simply make the change I have indicated (it is on line 322).

Also, I have serious doubts about programs such as yours that assume that arrays start at index 1 in C++.

In C++, arrays start at index 0, and you are to assume that the first position is index 0, not 1. By writing a program that assumes that the first position is index 1, you open yourself up for memory overwrite bugs, and other hard to diagnose problems.

I've been doing this a long time, and more often than not, any program that I've seen written that assumes or tries to fake out C++ into starting arrays at index 1 instead of 0 always ends up with some sort of indexing bug.

Regards,

Paul McKenzie

Quote:

---

Originally Posted by supahamster

Solved it! And I hate how simple it was.

Code:

---

if(cx+e != x && cy+i != y)

---

---

Maybe, but read my last post very carefully. Make sure you really are within bounds of your arrays, and not indexing one to many. Again, these are the perils of trying to simulate C++ arrays starting at index 1.

Regards,

Paul McKenzie

My problem was not with indexing, it was with switching x and y. If you notice in how I fixed the problem, I had to make the test if (cx==y...). There was no problem with the array indexes; if you note a previous post I made, I was uniform with my 'mistake' as to arrays, thus it was not my problem. Had my loops, arrays, etc. started at 0 instead of 1, I would have faced the same problem. The reason I had the arrays start at 1 was for my own conceptualizing purposes, so it would be easier to write the program. The next step for me now is to rewrite the program, condensing and cleaning up, for example making the arrays start at 0 instead of 1.
I was unaware of the potential problems you listed, but I did know that it is not ideal to have the arrays how I have them now, and I was planning on changing it before you said anything.

Quote:

---

Originally Posted by supahamster

Had my loops, arrays, etc. started at 0 instead of 1, I would have faced the same problem. The reason I had the arrays start at 1 was for my own conceptualizing purposes, so it would be easier to write the program.

---

The problem I am speaking of has nothing to do with the logic of the program. It has everything to do with overwriting the boundaries of an array. If you have an array declared as this:

Code:

---

int x[10];

---

And then you base a lot of code starting with the array index at 1, this may or may not work, regardless of how flawless the logic may be:

Code:

---

for (int i = 1; i <=10; ++i )
  x[i] = 0;

---

This code can seem to "work", or it can crash as soon as i becomes 10 and "x[i] = 0" is executed. This is a simple error, but pretend if it wasn't just "10", but some computed value in that loop that becomes hard to spot by sight.

This is exactly how assuming indices starting at 1 cause problems. You are fooled into thinking "finally the program works", but really, it is on shaky ground due to the memory access violation, not because of a flaw in the logic.

In C++, this is called undefined behaviour.

Regards,

Paul McKenzie

This can only be a problem, however, if the matrix is declared one way and then you try to access outside of its declaration. As you may notice, my declarations are currently

Code:

---

matrix[10][10]

---

When they only need to be 9x9. Thus, I have accounted for the possibility of a program crash because of this, and avoided it. Also, as I said earlier, I plan to clean this up, which includes making everything 0-based. What I was worrying about was the logic of the program, not optimizing it or anything else. When debugging, I find it easier to be able to skip the step of adding 1 in my head. For example in a 0-based system, the point (1,2) will actually be (2,3) on the visual board. Thus, I made it 1-based so that I could see more quickly what was where, and to work out the logic more easily.

However, why would the program be on shaky ground? All I am really doing is creating a matrix that is slightly larger than I need, and ignoring some of the values. Since everything is declared to accommodate the shift, I see no reason why this is more shaky than otherwise.

However, I do understand that it would be preferable to change for various reasons and I plan to do so.