[SOLVED] Sudoku solver keeps getting stuck for some reason...

Question

So I had to write a program for a computer project for high school and I thought of doing a sudoko solver. The 'solve' algorithm is implemented like this:-

1. For any points where only one element 'fits' looking at rows, columns, 3x3 set, put that number in. Do this repeatedly till it can't be done anymore. This is seen in the 'singleLeft' function.
2. If a number 'fits' in some point but nowhere else in the associated row, column or 3x3 set, put that number in. This can be seen in the 'checkOnlyAllowed' function.
3. If we're not done yet, do a 'guess' - take some number that 'fits' in the point, put it in there and then solve again using this algorithm (recurse) - if it works, we're done.

So far, I have this code:

#include <iostream>
#include <fstream>
#include <cstdlib>

using namespace std;

//Prints a message and exits the application.
void error(const char msg[])
{
    cout << "An error occurred!" << endl;
    cout << "Description: " << msg << endl;

    exit(0);
}

//A representation of a sudoku board. Can be read from a file or from memory.
class Sudoku
{
    protected:
        //For a point x, y and a number n in the board, mAllowed[x][y][n]
        //is 1 if n is allowed in that point, 0 if not.
        int mAllowed[9][9][10];
        int filledIn;

    public:
        /*
         * For mBoard[i][j], the location is (i,j) in the below map:
         *
         * (0,0) (0,1) (0,2)  (0,3) (0,4) (0,5)  (0,6) (0,7) (0,8) 
         * (1,0) (1,1) (1,2)  (1,3) (1,4) (1,5)  (1,6) (1,7) (1,8) 
         * (2,0) (2,1) (2,2)  (2,3) (2,4) (2,5)  (2,6) (2,7) (2,8) 
         *   
         * (3,0) (3,1) (3,2)  (3,3) (3,4) (3,5)  (3,6) (3,7) (3,8) 
         * (4,0) (4,1) (4,2)  (4,3) (4,4) (4,5)  (4,6) (4,7) (4,8) 
         * (5,0) (5,1) (5,2)  (5,3) (5,4) (5,5)  (5,6) (5,7) (5,8) 
         *    
         * (6,0) (6,1) (6,2)  (6,3) (6,4) (6,5)  (6,6) (6,7) (6,8) 
         * (7,0) (7,1) (7,2)  (7,3) (7,4) (7,5)  (7,6) (7,7) (7,8) 
         * (8,0) (8,1) (8,2)  (8,3) (8,4) (8,5)  (8,6) (8,7) (8,8) 
         *
         */

        int mBoard[9][9];

        //Read in from file with given name.
        Sudoku(char filename[])
        {
            filledIn = 0;

            int i, j, k;

            //Fill the board with 0s.
            for (i = 0; i < 9; ++i)
                for (j = 0; j < 9; ++j)
                    mBoard[i][j] = 0;

            //Set every number to 'allowed' initially.
            for (i = 0; i < 9; ++i)
                for (j = 0; j < 9; ++j)
                    for (k = 1; k <= 9; ++k)
                        mAllowed[i][j][k] = 1;

            //Read in from the file.
            ifstream file(filename);
            if (!file)
                error("File doesn't exist!");
            for (i = 0; i < 9; ++i)
                for (j = 0; j < 9; ++j)
                    if (file)
                    {
                        int m;
                        file >> m;
                        if (m)
                            set(i, j, m);
                    }
                    else
                        error("Not enough entries in file!");
        }

        //Solve the board!
        int solve()
        {
            int prevFilledIn;

            do
            {
                prevFilledIn = filledIn;
                singleLeft();
                checkOnlyAllowed();
            } while (filledIn - prevFilledIn > 3);

            if (filledIn < 81)
                guess();
            return filledIn == 81;
        }

        //Given a point i, j, this looks for places where this point
        //disallows a number and sets the 'mAllowed' table accordingly.
        void fixAllowed(int i, int j)
        {
            int n = mBoard[i][j], k;

            for (k = 0; k < 9; ++k)
                mAllowed[i][k][n] = 0;
            for (k = 0; k < 9; ++k)
                mAllowed[k][j][n] = 0;

            //Look in 3x3 sets too. First, set each coordinate to the
            //highest multiple of 3 below itself. This takes us to the
            //top-left corner of the 3x3 set this point was in. Then,
            //add vectorially all points (x,y) where x and y each are
            //one of 0, 1 or 2 to visit each point in this set.
            int x = (i / 3) * 3;
            int y = (j / 3) * 3;

            for (k = 0; k < 3; ++k)
                for (int l = 0; l < 3; ++l)
                    mAllowed[x + k][y + l][n] = 0;

            mAllowed[i][j][n] = 1;
        }

        //Sets a point i, j to n.
        void set(int i, int j, int n)
        {
            mBoard[i][j] = n;
            fixAllowed(i, j);
            ++filledIn;
        }

        //Try using 'single' on a point, ie, only one number can fit in this
        //point, so put it in and return 1. If more than one number can fit,
        //return 0.
        int trySinglePoint(int i, int j)
        {
            int c = 0, m;
            for (m = 1; m <= 9; ++m)
                c += mAllowed[i][j][m];

            if (c == 1)
            {
                for (m = 1; m <= 9; ++m)
                    if (mAllowed[i][j][m])
                        set(i, j, m);
                //printBoard();
                return 1;
            }
            return 0;
        }

        //Try to solve by checking for spots that have only one number remaining.
        void singleLeft()
        {
            for (;;)
            {
                for (int i = 0; i < 9; ++i)
                    for (int j = 0; j < 9; ++j)
                        if (!mBoard[i][j])
                            if (trySinglePoint(i, j))
                                goto logic_worked;

                //If we reached here, board is either full or unsolvable by this logic, so
                //our job is done.
                return;
logic_worked:
                continue;
            }
        }

        //Within rows, columns or sets, whether this number is 'allowed' in spots
        //other than i, j.
        int onlyInRow(int n, int i, int j)
        {
            for (int k = 0; k < 9; ++k)
                if (k != j && mAllowed[i][k][n])
                    return 0;
            return 1;
        }
        int onlyInColumn(int n, int i, int j)
        {
            for (int k = 0; k < 9; ++k)
                if (k != i && mAllowed[k][j][n])
                    return 0;
            return 1;
        }
        int onlyInSet(int n, int i, int j)
        {
            int x = (i / 3) * 3;
            int y = (j / 3) * 3;

            for (int k = 0; k < 3; ++k)
                for (int l = 0; l < 3; ++l)
                    if (!(x + k == i && y + l == j) && mAllowed[x + k][y + l][n])
                        return 0;
            return 1;
        }
        //If a number is 'allowed' in only one spot within a row, column or set, it's
        //guaranteed to have to be there.
        void checkOnlyAllowed()
        {
            for (int i = 0; i < 9; ++i)
                for (int j = 0; j < 9; ++j)
                    if (!mBoard[i][j])
                        for (int m = 1; m <= 9; ++m)
                            if (mAllowed[i][j][m])
                                if (onlyInRow(m, i, j) || onlyInColumn(m, i, j) || onlyInSet(m, i, j))
                                    set(i, j, m);
        }

        //Copy from a given board.
        void copyBoard(int board[9][9])
        {
            filledIn = 0;
            for (int i = 0; i < 9; ++i)
                for (int j = 0; j < 9; ++j)
                {
                    if (board[i][j] > 0)
                        ++filledIn;
                    mBoard[i][j] = board[i][j];
                }
        }

        //Try to solve by 'guessing'.
        void guess()
        {
            for (int i = 0; i < 9; ++i)
                for (int j = 0; j < 9; ++j)
                    for (int n = 1; n <= 9; ++n)
                        if (!mBoard[i][j])
                            if (mAllowed[i][j][n] == 1)
                            {
                                //Do a direct copy so that it gets the 'mAllowed'
                                //table too.
                                Sudoku s = *this;

                                //Try solving with this number at this spot.
                                s.set(i, j, n);
                                if (s.solve())
                                {
                                    //It was able to do it! Copy and report success!
                                    copyBoard(s.mBoard);
                                    return;
                                }
                            }
        }

        //Print the board (for debug purposes)
        void printBoard()
        {
            for (int i = 0; i < 9; ++i)
            {
                for (int j = 0; j < 9; ++j)
                    cout << mBoard[i][j] << " ";
                cout << endl;
            }
            cout << endl;
            char s[5];
            cin >> s;
        }

};

int main(int argc, char **argv)
{
    //char filename[42];
    //cout << "Enter filename: ";
    //cin >> filename;

    char *filename = argv[1];

    Sudoku s(filename);
    if (!s.solve())
        error("Couldn't solve!");

    cout << "Solved! Here's the solution:" << endl << endl;

    for (int i = 0; i < 9; ++i)
    {
        for (int j = 0; j < 9; ++j)
            cout << s.mBoard[i][j] << " ";
        cout << endl;
    }

    return 0;
}

(code including line numbers: http://sprunge.us/AiUc?cpp)

Now I understand that it isn't very good style, but it came out of a late-night coding session and also we use an older compiler in the school lab so I had to do some things differently (in that compiler, the standard headers have the '.h' extension, variables declared in for loops are in outside-for scope, ... ).

The file should contain whitespace-delimited digits for each spot in the board starting from the top-left going left to right and top to bottom, with empty spots signified by '0's.

For the following file, it works rather well:

5 3 0 0 7 0 0 0 0
6 0 0 1 9 5 0 0 0
0 9 8 0 0 0 0 6 0
8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6
0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 5
0 0 0 0 8 0 0 7 9

However, this one gives it trouble:

0 9 4 0 0 0 1 3 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 7 6 0 0 2 
0 8 0 0 1 0 0 0 0 
0 3 2 0 0 0 0 0 0 
0 0 0 2 0 0 0 6 0 
0 0 0 0 5 0 4 0 0 
0 0 0 0 0 8 0 0 7 
0 0 6 3 0 4 0 0 8 

If I comment out the print statements and track the progress I can see that it starts by heading out in the wrong direction at points. Eventually it gets stuck toward the end and the backtracking never gets far back enough. I think it's something wrong with the 'checkOnlyAllowed' part...

What do you think could be the problem?

Also - I know I could've used a bitfield for the 'mAllowed' table but we don't officially know about bitwise operations yet in school. :P

Answer 1

At line 170 you have a goto that is jumping out of a for loop, then continuing. This could give you some weird behavior with continuing the wrong loop, behavior that might depend on the specific compiler.

Try replacing lines 164-177 with:

164             for (;;)
165             {
166                 bool successfullyContributedToTheBoard = false;
167                 for (int i = 0; i < 9; ++i)
168                     for (int j = 0; j < 9; ++j)
169                         if (!mBoard[i][j])
170                             if (trySinglePoint(i, j))
171                                 successfullyContributedToTheBoard = true;
172                 if (!successfullyContributedToTheBoard)
173                     return;
174             }

Answer 2

I didn't look at your code but your strategy is exactly the same as the one I used to code a Sudoku solver. But I can't remember it being very slow. I got solutions in an instant. The maximum number of "guesses" the program had do make was 3 during my tests. That was for Sudoku problems which were supposed to be very hard. Three is not a big number with respect to back tracking and you can pick a cell which has only a few possibilities left (two or three) which limits the search space to about 20-30 states only (for hard Sudoku problems).

What I'm saying is, it's possible to use this strategy and solve Sudoku problems really fast. You only have to figure out how to optimize your code. Try to avoid redundant work. Try to remember things so you don't need to recalculate them again and again.

Answer 3

Funny story: One of my first programs was also a Sudoku solver. I used to implement a shitload of solving algorithms except guessing numbers and it worked fine for simple sudokus. But unfortunately there are sudokus out there, where one has to guess the number. I was a little pissed off, so I googled a bit and found an algorithm that was about 5 lines of code. 5! That day I learned, that elegant code is very nice.

I`m at work now, so all I can do to help you is to tell you... google for "backtracking" and "recursive calls" or similar.

5 lines of code!

Answer 4

Alright, I got it working! It seems that the i, j loop within 'guess' was unecessary - ie., it should only do a guess on one empty spot because its 'child processes' will handle the rest. Fixing this actually made the code simpler. Now it works really well, and actually its very quick!

Thanks for your help, everyone. ;-)