文章/答案/技术大牛

发布

社区首页 >问答首页 >入门级递归数独求解器

问入门级递归数独求解器
EN

Code Review用户

提问于 2013-07-20 16:23:50

回答 2查看 2.6K关注 0票数 9

我被要求在我的应用程序中附加一个C++代码示例，以便在一家视频游戏公司担任入门级的C++程序员职位。我创建了一个简单而完整的控制台应用程序来解决Sudoku问题。如何改进我所拥有的代码？

请对算法、代码实践、演示或其他任何内容进行评论。这是我第一次尝试用我的代码设置单元测试。

另外，我感兴趣的是，您是否认为作为一个代码示例，它是否能很好地工作--也就是说，它是否显示了查看代码示例的人希望看到什么？

完整代码

#include <set>
#include <string>

#include <fstream>
#include <iostream>
#include <cassert>

// ======================================================================================

enum SolutionResult {

    // The position has been solved OK.
    SR_SOLVED,

    // The current position in invalid.
    // For that reason, it is useless to even attempt to solve it.
    SR_INVALID,

    // The current position is valid in its current state, but there 
    // exists no complete solution that would uphold the sudoku rules.
    SR_UNSOLVABLE

};

// ======================================================================================

class Sudoku {

protected:

    // 0 = Empty cell
    short values[9][9];

    // Returns whether all the rows are currently valid, 
    // i.e. whether no rows contain any duplicate values.
    bool checkValidRows() {

        for (short row = 0; row < 9; row++) {

            std::set<short> valuesInRow;
            for (short col = 0; col < 9; col++) {

                short val = this->values[row][col];
                if (!val) continue;

                if (valuesInRow.find(val) != valuesInRow.end()) {
                    return false;
                }

                valuesInRow.insert(val);

            }

        }

        return true;

    }

    // Returns whether all the columns are currently valid, 
    // i.e. whether no columns contain any duplicate values.
    bool checkValidCols() {

        for (short col = 0; col < 9; col++) {

            std::set<short> valuesInCol;
            for (short row = 0; row < 9; row++) {

                short val = this->values[row][col];
                if (!val) continue;

                if (valuesInCol.find(val) != valuesInCol.end()) {
                    return false;
                }

                valuesInCol.insert(val);

            }

        }

        return true;

    }

    // Returns whether all the partial squares are currently valid, 
    // i.e. whether no 3x3 square contains a duplicate value.
    bool checkValidSquares() {

        for (short squareX = 0; squareX < 3; squareX++) {
        for (short squareY = 0; squareY < 3; squareY++) {

            std::set<short> valuesInSquare;
            for (short m = 0; m < 3; m++) {
                for (short n = 0; n < 3; n++) {

                    short val = this->values[squareX*3+m][squareY*3+n];
                    if (val == 0) continue;
                    if (valuesInSquare.find(val) != valuesInSquare.end()) {
                        return false;
                    }
                    valuesInSquare.insert(val);

                }
            }

        }
        }

        return true;

    }

    // Returns whether the current position is valid, i.e., whether its rows, columns, 
    // and squares are all valid and do not contain a duplicate value.
    bool checkValid() {

        return this->checkValidRows() && this->checkValidCols() && this->checkValidSquares();

    }

public:

    Sudoku() {

        // Start with a blank position.
        for (short row = 0; row < 9; row++) {
        for (short col = 0; col < 9; col++) {

            this->values[row][col] = 0;

        }
        }

    }

    Sudoku (const short values[9][9]) {

        for (short row = 0; row < 9; row++) {
        for (short col = 0; col < 9; col++) {

            // Values that are not between [0 .. 9] 
            // are discarded and replaced with zeroes.
            short val = values[row][col];
            if (val >= 0 && val <= 9) {
                this->values[row][col] = val;
            } 
            else {
                this->values[row][col] = 0;
            }

        }
        }

    }

    // This is the solver method.
    // The way to solution is a standard backtrack exercise.
    // 
    // For the next empty space, we put the lowest possible value in, and recursively call the solver
    // to see whether it can complete all the other spaces in a valid manner – in which case, we are done.
    // In case that no possible value in the chosen space leads to a valid and complete solution, we clear 
    // the space entirely and declare the position as unsolvable. In recursion terms, this means that 
    // we need to attempt to put another value to the previous space, and so on.

    SolutionResult solve() {

        // Check that the situation is valid.
        if (!this->checkValid()) return SR_INVALID;

        // For the next empty space:
        for (short row = 0; row < 9; row++) {
        for (short col = 0; col < 9; col++) {

            if (this->values[row][col] > 0) continue;

            // Put an arbitrary value into the space:
            for (short val = 1; val <= 9; val++) {

                this->values[row][col] = val;

                // Recursively call the solver and see whether it can complete all 
                // the other spaces in the same manner. In case that it can, we're done.
                if (this->solve() == SR_SOLVED) {
                    return SR_SOLVED;
                }

            }

            // We tried all the possible values, and none has lead to a complete and 
            // valid solution. Clear the space, and return that the position is unsolvable.
            this->values[row][col] = 0;
            return SR_UNSOLVABLE;

        }
        }

        // There are no more empty spaces. 
        // We're done.
        return SR_SOLVED;

    }

    // Formatted output.
    friend std::ostream& operator<< (std::ostream &os, const Sudoku& s) {

        for (short row = 0; row < 9; row++) {

            os << std::endl;
            for (short col = 0; col < 9; col++) {

                os << ' ';
                if (s.values[row][col] > 0) {
                    os << s.values[row][col];
                } else {
                    os << '.';
                }

                if (col == 2 || col == 5) {
                    os << " |";
                }

            }

            if (row == 2 || row == 5) {
                os << std::endl << " ------+-------+------";
            }

        }

        os << std::endl;
        return os;

    }

    //
    static void runUnitTests();

};

// ======================================================================================

int main (int argc, char* argv[])
{
    short pos[9][9] = {
        {0, 0, 4, 0, 0, 0, 0, 0, 0},
        {6, 0, 2, 1, 0, 0, 0, 0, 0},
        {1, 0, 8, 3, 4, 2, 5, 6, 7},
        {0, 0, 9, 7, 0, 0, 4, 2, 3},
        {4, 0, 6, 8, 0, 0, 0, 0, 1},
        {7, 1, 3, 9, 2, 0, 8, 0, 0},
        {0, 0, 0, 5, 3, 0, 2, 8, 4},
        {0, 0, 0, 4, 1, 0, 6, 0, 0},
        {3, 0, 0, 0, 0, 6, 1, 0, 0}
    };

    // Let's test the entire unit.
    Sudoku::runUnitTests();

    // Let's solve the particular position above:

    Sudoku s (pos);
    std::cout << s << std::endl;
    std::cout << "Solver starts, please wait..." << std::endl;

    switch (s.solve()) {

    case SR_SOLVED:
        std::cout << "Solution: " << std:: endl;
        std::cout << s << std::endl;
        break;

    case SR_INVALID:
        std::cout << "The position is not valid." << std:: endl;
        break;

    case SR_UNSOLVABLE:
        std::cout << "The position cannot be solved." << std:: endl;
        break;

    }

    std::cout << "Press any key to exit...";
    getchar();
    return 0;
}

// ======================================================================================

void Sudoku::runUnitTests() {

    short dataZeroes[9][9] = {
        {0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0}
    };

    short dataValidPos1[9][9] = {
        {5, 3, 4, 6, 7, 8, 9, 1, 2},
        {6, 7, 2, 1, 9, 5, 3, 4, 8},
        {1, 9, 8, 3, 4, 2, 5, 6, 7},
        {8, 5, 9, 7, 6, 1, 4, 2, 3},
        {4, 2, 6, 8, 5, 3, 7, 9, 1},
        {7, 1, 3, 9, 2, 4, 8, 5, 6},
        {9, 6, 1, 5, 3, 7, 2, 8, 4},
        {2, 8, 7, 4, 1, 9, 6, 3, 5},
        {3, 4, 5, 2, 8, 6, 1, 7, 9}
    };

    short dataValidPos2[9][9] = {
        {0, 0, 0, 0, 0, 0, 0, 0, 0},
        {6, 0, 2, 1, 0, 0, 0, 0, 0},
        {1, 0, 8, 3, 4, 2, 5, 6, 7},
        {0, 0, 9, 7, 0, 0, 4, 2, 3},
        {4, 0, 6, 8, 0, 0, 0, 0, 1},
        {7, 1, 3, 9, 2, 0, 8, 0, 0},
        {0, 0, 0, 5, 3, 0, 2, 8, 4},
        {0, 0, 0, 4, 1, 0, 6, 0, 0},
        {3, 0, 0, 0, 0, 6, 1, 0, 0}
    };

    short dataInvalidRows[9][9] = {
        {5, 3, 4, 6, 7, 8, 9, 1, 5},
        {6, 7, 2, 1, 9, 5, 3, 4, 8},
        {1, 9, 8, 3, 4, 2, 0, 6, 7},
        {8, 5, 9, 7, 6, 1, 4, 2, 3},
        {4, 2, 6, 8, 5, 3, 7, 9, 1},
        {7, 1, 3, 9, 2, 4, 8, 5, 6},
        {9, 6, 1, 5, 3, 7, 2, 8, 4},
        {2, 8, 7, 4, 1, 9, 6, 3, 0},
        {3, 4, 5, 2, 8, 6, 1, 7, 9}
    };

    short dataInvalidCols[9][9] = {
        {5, 3, 4, 6, 7, 8, 9, 1, 2},
        {6, 7, 2, 1, 9, 0, 3, 4, 8},
        {1, 9, 8, 3, 4, 2, 5, 6, 7},
        {8, 5, 9, 7, 6, 1, 4, 2, 3},
        {4, 2, 6, 8, 5, 3, 7, 9, 1},
        {7, 1, 3, 9, 2, 4, 8, 5, 6},
        {9, 6, 1, 5, 3, 7, 2, 8, 4},
        {2, 8, 7, 4, 1, 9, 6, 3, 5},
        {5, 4, 0, 2, 8, 6, 1, 7, 9}
    };

    short dataInvalidSquares[9][9] = {
        {5, 3, 4, 6, 7, 8, 9, 1, 2},
        {6, 5, 2, 1, 9, 0, 3, 4, 8},
        {1, 9, 8, 3, 4, 2, 5, 6, 7},
        {8, 0, 9, 7, 6, 1, 4, 2, 3},
        {4, 2, 6, 8, 5, 3, 7, 9, 1},
        {7, 1, 3, 9, 2, 4, 8, 5, 6},
        {9, 6, 1, 5, 3, 7, 2, 8, 4},
        {2, 8, 7, 4, 1, 9, 6, 3, 5},
        {3, 4, 5, 2, 8, 6, 1, 7, 9}
    };

    Sudoku zeroes (dataZeroes);
    Sudoku validPos1 (dataValidPos1);
    Sudoku validPos2 (dataValidPos2);
    Sudoku invalidRows (dataInvalidRows);
    Sudoku invalidCols (dataInvalidCols);
    Sudoku invalidSquares (dataInvalidSquares);

    std::cout << "Unit tests start..." << std::endl;

    assert(zeroes.checkValidRows());
    assert(zeroes.checkValidCols());
    assert(zeroes.checkValidSquares());
    assert(zeroes.checkValid());
    assert(zeroes.solve() == SR_SOLVED);

    assert(validPos1.checkValidRows());
    assert(validPos1.checkValidCols());
    assert(validPos1.checkValidSquares());
    assert(validPos1.checkValid());
    assert(validPos1.solve() == SR_SOLVED);

    assert(validPos2.checkValidRows());
    assert(validPos2.checkValidCols());
    assert(validPos2.checkValidSquares());
    assert(validPos2.checkValid());
    assert(validPos2.solve() == SR_SOLVED);
    assert(validPos2.values[0][0] == 5);
    assert(validPos2.values[0][1] == 3);
    assert(validPos2.values[0][2] == 4);
    assert(validPos2.values[0][3] == 6);
    assert(validPos2.values[0][4] == 7);
    assert(validPos2.values[0][5] == 8);
    assert(validPos2.values[0][6] == 9);
    assert(validPos2.values[0][7] == 1);
    assert(validPos2.values[0][8] == 2);

    assert(!invalidRows.checkValidRows());
    assert( invalidRows.checkValidCols());
    assert( invalidRows.checkValidSquares());
    assert(!invalidRows.checkValid());
    assert( invalidRows.solve() == SR_INVALID);

    assert( invalidCols.checkValidRows());
    assert(!invalidCols.checkValidCols());
    assert( invalidCols.checkValidSquares());
    assert(!invalidCols.checkValid());
    assert( invalidCols.solve() == SR_INVALID);

    assert( invalidSquares.checkValidRows());
    assert( invalidSquares.checkValidCols());
    assert(!invalidSquares.checkValidSquares());
    assert(!invalidSquares.checkValid());
    assert( invalidSquares.solve() == SR_INVALID);

    std::cout << "All unit tests OK." << std::endl;

}

c++

recursion

sudoku

回答 2

Code Review用户

回答已采纳

发布于 2013-07-20 18:50:08

简单地看一下，我就可以看到代码中的一些问题。如果我过于直率，我很抱歉，但你最好听我说，而不是招聘者。

不按特定顺序：

用这种语言。更好地构造代码。考虑使用更多的类来代表董事会。不要写一个sudoku解决方案。让它成为一个很小的sudoku解决程序库，并包括一个使用该库的驱动程序。编写可重用的代码。
您有这个类的protected成员。这通常意味着该类被设计为基类。然而，基类应该有一个虚拟析构函数，但您的类不是。您可能希望将protected更改为private。
使您的解决方案处理板与多种解决方案。
在我看来，你对this的明确使用只会造成混乱。
您的代码不例外安全。例如，如果solve()抛出异常，则无法测试解决程序的状态。您应该在公共接口中有一个函数来查询求解器的状态。
避免过多的空格和注释。
使不变异状态const的成员函数。

例如：

bool checkValidCols() const { /* ... */ }

不要硬代码大小。从文件中读取您的游戏板。接受可变尺寸的板子.
当增量前是你想要的时候，你更喜欢前增量而不是后增量。您要说的是“增量i by one"，而不是”复制i，然后再将原始值增加1“。一般来说，这是一个好习惯，因为用户定义类型的后增量确实会产生额外的、不必要的副本。
不要重复你自己。checkValidRows和checkValidCols或多或少是同一个函数。如果您做了一些抽象，那么正方形检查也是如此。
考虑使用一维数组和/或使用一维或二维std::array或std::vector。
您发布的代码中存在缩进问题。
你的解题算法可能是我能想到的最慢的算法。做一个快速的谷歌搜索，做一些更聪明的事情。
您有非常长的函数是内联定义的。它给人的印象是，您只知道Java，而恰好是用C++编写的。将实现代码从类定义中移出，并将代码构造为文件。
使用单独的单元测试库，例如googletest。程序运行时不要总是运行单元测试。
删除“按任意键退出”部分。看起来很不专业。
考虑添加对板块的只读访问，这样以后类就可以作为GUI的后端使用。
如果您不打算使用参数，请不要将参数传递给main。
在您的default中添加一个switch以捕获错误。
使用断言确保调试过程中函数的前后条件和不变量。
执行错误处理，最好使用异常。使您的程序非常健壮；您不希望在游戏中使用CTD。
有许多小的单元测试，这些测试完全是一件事情。如果测试失败，您应该从它的名称中知道什么失败了。看看联机单元测试示例。
按字母顺序排列你的#includes。
考虑让您的解决程序多线程。
记住要包括其他重要的部分。主要是:文档化，并使用适当的构建系统(对于这样一个简单的应用程序来说，make就足够了)。在文档中，您可以包括对求解算法的讨论，包括对其效率的分析(渐近复杂性/作为最小值的大-O)。

票数 13

Code Review用户

发布于 2013-07-20 17:54:25

阅读这和这关于你的评论。您也不应该在函数中有额外的空格。
我不知道您的完整解决方案是使用单个文件还是单独的文件。多个文件是首选的，但如果声明和定义结构正确，那么单个文件也是可以的。关于声明，您不应该在头中有任何函数定义(考虑到您没有使用访问器和变异器)。尝试如下:类Sudoku {私有: //私有优于在这里受保护的短值9；//这些函数应该是const bool checkValidRows() const；bool checkValidCols() const；bool checkValidSquares() const；public: Sudoku()；Sudoku(const短值9)；SolutionResult解决()；SolutionResult()；友std:solve& operator<<( std::ostream&，Sudoku const&)；}；
您可以使用"2D“std::array代替。它给出了这些特征，但它看起来有点像嵌套结构(尽管可以使用typedef)：std::array、9>值；
solve()不应该是public，因为它不是接口的一部分。相反，将其设置为private和void，并让另一个public函数返回适当的SolutionResult。然后，您需要调用类中的某个位置的solve()，而不是main()。
对于一个严肃的应用程序，你不应该需要硬编码你的游戏板。即使把这些隐藏在课堂后面，也会很无聊，因为你每次都要解决同一个问题(除非你愿意自己去改变它)。相反，考虑让董事会随机的值，并确保它是一个有效的启动板。同样，这将在类内完成。这样就不需要第二个构造函数了。

票数 9

页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://codereview.stackexchange.com/questions/28746

复制

相似问题

问入门级递归数独求解器
EN

回答 2

Code Review用户

Code Review用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问入门级递归数独求解器EN

回答 2

Code Review用户

Code Review用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问入门级递归数独求解器
EN