数独回溯算法 [英] Sudoku backtracking algorithm

问题描述

首先，我要指出，这是一所大学的任务，所以我不能要求别人写的code对我来说我只需要指出了正确的方向。 ：）

First of all, I'll state that this is a university assignment so I'm not asking for someone to write the code for me I just need to be pointed in the right direction. :)

好了，我需要写一个算法来解决任意大小的任何（解）数独板。我写了一个递归函数，可以快速（〜1毫秒）解决任何9x9的板，但是当我要做大板（16×16），是很难解决它的斗争......我已经有一个测试会持续20分钟，它可以不像是会解决这个问题。它可以轻松解决难题16×16，甚至是空白的16×16板，所以我不认为这是有问题尺寸..它更可能是算法这是我认为这个问题。

Ok, so I need to write an algorithm to solve any (solvable) sudoku board of arbitrary size. I've written a recursive function that can solve any 9x9 board quickly (~1ms) but when I do larger boards (16x16) that are hard to solve it struggles.. I've had one test going for 20 minutes and it can't seem to solve it. It can solve easy 16x16 puzzles or even a blank 16x16 board so I don't think it's the dimensions that are the problem.. it's more likely to be the algorithm that is the problem I think.

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

Anyway, this is the basic logic of my program..

• 在我有一个三维矢量存储我的每平方
的可能值
• 当一个值置于一个方形然后将其从周围正方形，行和列的可能的值除去，它的中

然后我的解决功能基本上是：

Then my solve function is basically:

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
}

有什么效率低下这一点？有什么办法，我可以让它更好地工作？我猜测，一个16×16板这么久是因为决策树是如此之大，对于未填写一个很有板。这很奇怪，因为一个9x9的董事会将解决真快。

Is there anything inefficient about this? Is there any way I could get it to work better? I'm guessing that a 16x16 board takes so long is because the decision tree for it is so large for a board that isn't filled in very much. It's weird though, because a 9x9 board will solve really fast.

任何意见或建议将是绝对真棒。如果有我已经错过了任何信息，让我知道了！

Any ideas or suggestions would be absolutely awesome. If there's any information I've missed let me know too!

推荐答案

填充广场只有一个选择，在船上准备充分递归还有更高级的操作，你可以做之间。让我们说，地区，是一排，或一列，或者一个正方形的区域（3×3或4×4）。

Between filling the squares with only one choice and going full recursive on the board there are more advanced actions you can do. Lets take that "region" is one row, or one column, or one square region (3x3 or 4x4).

如果有K个方块的区域中，可以采取只有相同K个（例如两个正方形只能2的5，或三个正方形采取只能取1，7和8），然后在所有其它平方区域不能把这些具体的数字。您需要遍历各地区淘汰取的数字，所以你可以找到只有一个合乎逻辑的选择正方形（与2,4和5实例第三方形逻辑上只需要4，或1,3五四广场，图7和8在逻辑上可以采取仅3）。

If there are K squares in a region that can take only identical K numbers (for instance two squares that can take only 2 an 5, or three squares that can take only 1, 7 and 8) then all other squares in that region can't take those specific numbers. You need to iterate each region to weed out "taken" numbers, so you can find a square with only one logical choice (for instance third square with 2, 4 and 5 logically can take only 4, or fourth square with 1, 3, 7 and 8 logically can take only 3).

这已经到BI解决了迭代，如果你看看下面的例子。一个地区有正方形这​​个可能的数字：

This has to bi solved with iteration if you consider the following example. A region has squares with this possible numbers:

答：1 2 3
B：2- 3
C：2 3 4 5
D：4 5
E：4 5

A: 1 2 3
B: 2 3
C: 2 3 4 5
D: 4 5
E: 4 5

该算法应该检测平方D和E保持号4和5，所以图4和5被排除在该区域的其他正方形。然后，该算法检测到方块B和C保持号2和3中，并因此从其它方块中排除它们。这使得方的一种，只有号码1。

The algorithm should detect that squares D and E hold numbers 4 and 5, so 4 and 5 are excluded from other squares in the region. The algorithm then detects that squares B and C hold numbers 2 and 3, and so excludes them from other squares. This leaves square A with only number 1.

如果出现了一些在该地区只有一个平方那么在逻辑上是方认为，一些。

If a number occurs in the region in only one square then logically that square holds that number.

策略1和2是策略3只特殊情况下具有K个方格，仅退K相同的数字。可以的K正方形和一组K个的和那些ķ方块可以容纳这些K个的任何子集。考虑的区域的下面的示例：

Tactics 1 and 2 are only special cases of Tactic 3 having K squares with only K identical numbers. You can have K squares and a set of K numbers and those K squares can hold any subset of those K numbers. Consider the following example of a region:

答：1 2
B：2- 3
C：1 3
D：1 2 3 4

A: 1 2
B: 2 3
C: 1 3
D: 1 2 3 4

广场A，B和C可容纳只有数字1，2和3。这是K代表K.这意味着，任何其他方无法在逻辑上认为这些数字，这让方丁，只有4号

Squares A, B and C can hold only numbers 1, 2 and 3. That's K for K. That means that any other square can't logically hold these numbers, which leaves square D with only number 4.

战术二是战术3的特殊情况下，当K = N - 1

Tactic 2 is special case of Tactic 3 when K = N - 1.

充分利用区域重叠。假设一些数量可以只存在于该区域的特定正方形。如果所有这些方块属于另一个重叠区域则该数量应在此以外的区域排除在所有其它方块。

Take advantage of regions overlap. Suppose that some number can exist only in certain squares of the region. If all those squares belong to another overlapping region then that number should be excluded from all other squares in this other region.

缓存结果。所有地区应该有一个脏标志，表示该事在该地区已经从该地区被处理的最后一次修改。你不必使用该标志未设置处理区域。

Cache results. All regions should have a "dirty" flag that denotes that something in the region has changed from the last time the region is processed. You don't have to process the region with this flag not set.

人类使用所有这些战术，真的很讨厌猜一个数字，因为回溯是一个真正的痛苦。实际上，一个板的难度测量猜测的最小数目人们必须使解决板。对于大多数​​极端板一个很好的猜测是不够的。

Human beings use all those tactics, and really hate to guess a number, because backtracking is a real pain. Actually, the difficulty of a board is measured with the minimum number of guesses one has to make to solve the board. For most "extreme" boards one good guess is enough.

这篇关于数独回溯算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！