c++ - 数独解算器由于某种原因不断卡住

Question

所以我不得不为高中的计算机项目编写一个程序，我想做一个数独求解器。 “解决”算法是这样实现的:-

1. 对于只有一个元素“适合”查看行、列、3x3 集的任何点，输入该数字。重复此操作，直到无法再完成为止。这可以在“singleLeft”函数中看到。
2. 如果某个数字“适合”某个点，但在关联的行、列或 3x3 集合中没有其他地方，则将该数字放入。这可以在“checkOnlyAllowed”函数中看到。
3. 如果我们还没有完成，请“猜测”- 取一些“适合”该点的数字，将其放在那里，然后使用此算法(递归)再次求解 - 如果它有效，我们完成。

到目前为止，我有这段代码:

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

(包含行号的代码:http://sprunge.us/AiUc?cpp)

现在我明白它不是很好的风格，但它来自一个深夜的编码 session ，而且我们在学校实验室使用了一个旧的编译器，所以我不得不做一些不同的事情(在那个编译器中，标准 header 具有“.h”扩展名，for 循环中声明的变量在外部 for 范围内，...)。

文件应包含棋盘中每个位置的空白分隔数字，从左上角到左到右，从上到下，空白点用“0”表示。

对于以下文件，它工作得相当好:

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

但是，这个给它带来了麻烦:

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 

如果我注释掉打印语句并跟踪进度，我可以看到它开始时在某些地方朝错误的方向前进。最终它会卡在最后，回溯永远不会回得足够远。我认为“checkOnlyAllowed”部分有问题...

您认为可能是什么问题？

此外 - 我知道我可以为“mAllowed”表使用位域，但我们在学校还没有正式了解按位运算。 :P

Answer 1

在第 170 行，您有一个 goto 跳出 for 循环，然后继续。这可能会给您带来一些奇怪的行为，继续错误的循环，这些行为可能取决于特定的编译器。

尝试将第 164-177 行替换为:

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             }