数独回溯算法

Question

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

好吧，所以我需要编写一个算法来解决任意大小的任何（可解）数独板。我编写了一个递归函数，可以快速解决任何 9x9 板（约 1 毫秒），但是当我处理难以解决的较大板（16x16）时，它就很困难..我已经进行了 20 分钟的测试，但它可以'似乎没有解决它。它可以解决简单的 16x16 谜题，甚至可以解决空白的 16x16 板，所以我认为问题不是尺寸。我认为问题更可能是算法。

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

• 我有一个 3D 向量，用于存储每个正方形的可能值
• 当将一个值放入一个正方形中时，它将从周围正方形、行和列的可能值中删除那么

我的解决函数基本上是：

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。您将解决数独问题表示为精确覆盖问题，然后使用用于解决 EC 问题的算法 X。然后使用 DLX 作为算法 X 的有效实现。

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

我可以告诉您，DLX 求解数独的速度非常快，通常用于最快的算法。

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

Answer 2

在仅用一种选择填充方格和在棋盘上完全递归之间，您可以执行更高级的操作。假设“区域”是一行、一列或一个正方形区域（3x3 或 4x4）。

策略 1

如果一个区域中有 K 个方格只能取相同的 K 个数字（例如两个方格只能取 2 和 5，或者三个方格只能取 1、7 和 8），则该区域中的所有其他方格无法接受那些具体数字。您需要迭代每个区域以清除“已采用”的数字，这样您就可以找到一个只有一个逻辑选择的方格（例如，具有 2、4 和 5 的第三个方格逻辑上只能采用 4，或者具有 1、3、 7和8逻辑上只能取3)。

如果考虑以下示例，则必须通过迭代来解决此问题。一个区域有包含以下可能数字的方块：

A: 1 2 3
乙：2 3
C: 2 3 4 5
深：4 5
E: 4 5

该算法应检测到方格 D 和 E 包含数字 4 和 5，因此 4 和 5 被排除在该区域的其他方格之外。然后，算法检测到方格 B 和 C 包含数字 2 和 3，因此将它们从其他方格中排除。这使得方格 A 只剩下数字 1。

策略 2

如果一个数字出现在该区域中仅一个方格中，则从逻辑上讲，该方格保存该数字。

策略3

策略1和2只是策略3的特例，其中K个方格只有K个相同的数字。您可以拥有 K 个方格和一组 K 个数字，并且这些 K 个方格可以容纳这 K 个数字的任何子集。考虑以下区域示例：

A: 1 2
乙：2 3
C：1 3
D: 1 2 3 4

方格 A、B 和 C 只能容纳数字 1、2 和 3。这就是 K 代表 K。这意味着任何其他方格在逻辑上都不能容纳这些数字，这使得方格 D 中只剩下数字 4。

当 K = N - 1 时，策略 2 是策略 3 的特例。

策略 4

利用区域重叠。假设某个数字只能存在于该区域的某些方格中。如果所有这些方块都属于另一个重叠区域，那么该数字应该从该其他区域中的所有其他方块中排除。

策略 5

缓存结果。所有区域都应该有一个“脏”标志，表示该区域中的某些内容自上次处理该区域以来已发生变化。您不必处理未设置此标志的区域。

---

人类使用所有这些策略，并且真的讨厌猜测数字，因为回溯真的很痛苦。实际上，棋盘的难度是用解决该棋盘所需的最少猜测次数来衡量的。对于大多数“极端”主板来说，一个好的猜测就足够了。

Answer 3

我不知道你之前是否看过这个链接。
而且在效率上它可能无法与跳舞链接算法相媲美
因为它使用朴素的回溯形式。不管怎样，它有效。
看看它是否对你有用！

您也可以添加几行来解决“简单”的方块。
http://edwinchan.wordpress.com/ 2006/01/08/sudoku-solver-in-c-using-backtracking/

Answer 4

你的算法看起来不错。问题是你使用的是暴力方法，因此你的运行时间是（字符数）^（板的大小） - 所以对于 9x9 有 9^9=387420489 而对于 16x16 运行时间是 16^ 16=18446744073709551616。你可以看到差异。

尝试寻找动态编程方法

• 如果您是一年级/二年级学生，请坚持您的想法有（并检查正确性）。你的老师不会期望更多。

Answer 5

没有必要将只有一个可能数字的单元格视为特殊的。您已经首先访问了可能性最少的单元格。

另外：当您“从 3D 矢量中删除该选择”时，您还可以将其从同一 {row, columns,box} 上的其他单元格中删除。位掩码可能会很好地适应。 （但是回溯会变得有点困难）

Answer 6

正如 @ralu 提到的，解决数独最快的算法是使用 DLX。下面是我过去写的一个程序。它可以在1秒内解决4*4数独。

假设输入如下：

--A----C-----O-I
-J--A-B-P-CGF-H-
--D--F-I-E----P-
-G-EL-H----M-J--
----E----C--G---
-I--K-GA-B---E-J
D-GP--J-F----A--
-E---C-B--DP--O-
E--F-M--D--L-K-A
-C--------O-I-L-
H-P-C--F-A--B---
---G-OD---J----H
K---J----H-A-P-L
--B--P--E--K--A-
-H--B--K--FI-C--
--F---C--D--H-N-


#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

const int INF=1<<30;
const int N=4;
const int MAXR=N*N*N*N*N*N+10;
const int MAXC=N*N*N*N*4+10;
const int SIZE=MAXR*MAXC/N/N;

int n,m;
int mat[MAXR][MAXC],r,c,ans;
int L[SIZE],R[SIZE],U[SIZE],D[SIZE],S[MAXC],C[SIZE],RH[SIZE],O[MAXC];
int a[MAXR];
char b[MAXR];
char s[N*N+10][N*N+10];
int head,cnt;

int node(int up,int down,int left,int right) {
    U[cnt]=up;D[cnt]=down;L[cnt]=left;R[cnt]=right;
    D[up]=U[down]=L[right]=R[left]=cnt;
    return cnt++;
}

void init() {
    cnt=0;
    head=node(0,0,0,0);
    for (int i=1;i<=c;i++) {
        C[i]=node(cnt,cnt,L[head],head);
        S[i]=0;
    }
    for (int i=1;i<=r;i++) {
        int rowh=-1;
        for (int j=1;j<=c;j++) if (mat[i][j]) {
            if (rowh==-1) {
                rowh=node(U[C[j]],C[j],cnt,cnt);
                RH[rowh]=i;
                C[rowh]=C[j];
                S[j]++;
            }
            else {
                int k=node(U[C[j]],C[j],L[rowh],rowh);
                RH[k]=i;
                C[k]=C[j];
                S[j]++;
            }
        }
    }
}

void remove(int col) {
    L[R[col]]=L[col];
    R[L[col]]=R[col];
    for (int i=D[col];i!=col;i=D[i])
        for (int j=R[i];j!=i;j=R[j]) {
            U[D[j]]=U[j];
            D[U[j]]=D[j];
            S[C[j]]--;
        }
}

void resume(int col) {
    for (int i=U[col];i!=col;i=U[i])
        for (int j=L[i];j!=i;j=L[j]) {
            S[C[j]]++;
            U[D[j]]=j;
            D[U[j]]=j;
        }
    L[R[col]]=col;
    R[L[col]]=col;
}

bool dfs(int k) {
    if (R[head]==head) {
        ans=k;
        return true;
    }
    int mins=INF,cur=0;
    for (int i=R[head];i!=head;i=R[i])
        if (S[i]<mins) {
            mins=S[i];
            cur=i;
        }
    remove(cur);
    for (int i=D[cur];i!=cur;i=D[i]) {
        O[k]=RH[i];
        for (int j=R[i];j!=i;j=R[j])
            remove(C[j]);
        if (dfs(k+1)) return true;
        for (int j=L[i];j!=i;j=L[j])
            resume(C[j]);
    }
    resume(cur);
    return false;
}

void makegraph() {
    r=0;
    for (int i=0;i<N*N;i++)
        for (int j=0;j<N*N;j++) {
            int t=(i/N)*N+(j/N);
            int p=i*N*N+j;
            if (s[i][j]=='-') {
                for (int k=1;k<=N*N;k++) {
                    r++;
                    mat[r][i*N*N+k]=1;
                    mat[r][N*N*N*N+j*N*N+k]=1;
                    mat[r][2*N*N*N*N+t*N*N+k]=1;
                    mat[r][3*N*N*N*N+p+1]=1;
                    a[r]=p;
                    b[r]='A'+k-1;
                }
            }
            else {
                int k=s[i][j]-'A'+1;
                r++;
                mat[r][i*N*N+k]=1;
                mat[r][N*N*N*N+j*N*N+k]=1;
                mat[r][2*N*N*N*N+t*N*N+k]=1;
                mat[r][3*N*N*N*N+p+1]=1;
                a[r]=p;
                b[r]=s[i][j];
            }
        }
}

int main() {
    freopen("sudoku.txt","r",stdin);
    freopen("sudoku_sol.txt","w",stdout);
        for (int i=0;i<N*N;i++)
            scanf("%s",s[i]);
        memset(mat,0,sizeof(mat));
        makegraph();
        c=N*N*N*N*4;

        init();
        ans=INF;
        dfs(0);
        for (int i=0;i<ans;i++)
            for (int j=i+1;j<ans;j++)
                if (a[O[i]]>a[O[j]]) swap(O[i],O[j]);

        for (int i=0;i<ans;i++) {
            printf("%c",b[O[i]]);
            if ((i+1)%(N*N)==0) printf("\n");
        }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

你可以尝试一下:)