c++ - 数独回溯算法

Question

首先，我要声明这是一项大学作业，所以我并不是要别人为我编写代码，我只需要指出正确的方向即可。 :)

好的，所以我需要编写一个算法来解决任意大小的任何(可解决的)数独游戏。我已经编写了一个递归函数，可以快速解决任何 9x9 板(~1ms)，但是当我做更大的板(16x16)很难解决它时，它会遇到困难。我已经进行了 20 分钟的测试，它可以'似乎无法解决。它可以解决简单的 16x16 拼图，甚至是空白的 16x16 板，所以我认为问题不是尺寸问题。我认为更可能是算法问题。

无论如何，这是我程序的基本逻辑..

• 我有一个 3D vector ，用于存储每个正方形的可能值
• 当一个值被放置在一个正方形中时，它会从它所在的周围正方形、行和列的可能值中移除

那么我的求解函数基本上是:

bool solve() {

    if (there are no unfilled squares)
        return true

    if (the board is unsolvable - there are empty squares that have no possible values)
        return false

    while (there are empty squares)
    {
        int squaresFilled = fillSquaresWithOnlyOneChoice(); //this method updates the possible results vector whenever it fills a square

        if (squaresFilled == 0)
            break;
    }

    //exhausted all of the 'easy' squares (squares with only one possible choice), need to make a guess

    while (there are empty squares that have choices left) {

        find the square with the least number of choices

        if (the square with the least number of choices has 0 choices)
            return false; //not solvable.

        remove that choice from the 3D vector (vector that has the choices for each square)
        make a copy of the board and the 3D choices vector

        fill the square with the choice

        if (solve())
            return true; //we're done

        restore the board and choices vector 
        //the guess didn't work so keep looping and make a new guess with the restored board and choices -- the choice we just made has been removed though so it won't get made again.

    }

    return false; //can't go any further
}

这有什么效率低下的地方吗？有什么办法可以让它更好地工作吗？我猜一个 16x16 的板需要这么长时间是因为它的决策树对于一个没有填充太多的板来说太大了。不过这很奇怪，因为 9x9 板的求解速度非常快。

任何想法或建议都绝对很棒。如果有任何我遗漏的信息，也请告诉我!

Answer 1

解决数独的快速算法是 Donald Knuth 的算法 X。您将解决数独问题表示为 exact cover问题，然后使用 Algorithm X用于解决 EC 问题。然后使用 DLX作为算法 X 的有效实现。

维基百科上有关于如何应用精确覆盖来解决数独的很好的解释。

我可以告诉你，DLX 非常快，可以快速解决数独问题，通常用在最快的算法中。

http://www.setbb.com/phpbb/index.php?mforum=sudoku是最好的数独程序员的好论坛。