首先，我将说明这是一项大学任务，所以我不是要求别人为我编写代码，我只需要指向正确的方向。 :)
好的，所以我需要编写一个算法来解决任意大小的任何（可解决的）数独板。我已经编写了一个递归功能，可以快速解决任何9x9电路板（约1ms）但是当我做大型电路板（16x16）很难解决时，它会挣扎......我已经进行了一次20分钟的测试，它可以'似乎解决了它。它可以解决简单的16x16谜题甚至是一个空白的16x16板，所以我不认为这是问题的尺寸..它更可能是我认为的问题算法。
无论如何，这是我的程序的基本逻辑..
然后我的解决功能基本上是：
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电路板的解决速度非常快。
任何想法或建议都绝对令人敬畏。如果有任何我错过的信息也让我知道！
在只用一个选项填充正方形并在板上完全递归之间，您可以执行更多高级操作。让我们认为“区域”是一行，或一列，或一个正方形区域（3x3或4x4）。
如果一个区域中有K个正方形只能采用相同的K数（例如两个正方形只能采用2个5个，或者三个正方形只需要1,7和8个），那么该区域中的所有其他正方形都可以'拿这些具体数字。您需要迭代每个区域以清除“采用”数字，因此您可以找到只有一个逻辑选择的正方形（例如，第三个方格，其中2,4和5逻辑上只能采用4个，或者第四个方形采用1,3， 7和8逻辑上只能占用3）。
如果您考虑以下示例，则必须通过迭代求解。一个区域有这个可能数字的正方形：
答：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，因此将它们从其他正方形中排除。这留下了方形A，只有1号。
如果一个数字仅出现在一个正方形的区域中，则逻辑上该正方形保存该数字。
战术1和2只是Tactic 3的特殊情况，其中K个方格只有K个相同的数字。您可以拥有K个正方形和一组K个数字，这些K个正方形可以包含这些K个数字的任何子集。考虑以下区域示例：
答：1 2 B：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的特例。
利用区域重叠。假设某些数字只能存在于该区域的某些方格中。如果所有这些方块都属于另一个重叠区域，那么该数字应该从该另一个区域中的所有其他方格中排除。
缓存结果。所有区域都应该有一个“脏”标志，表示该区域中的某些内容已经从上次处理该区域时发生了变化。您不必处理未设置此标志的区域。
人类使用所有这些策略，并且非常讨厌猜测一个数字，因为回溯是一种真正的痛苦。实际上，电路板的难度是用解决电路板所需的最小猜测次数来衡量的。对于大多数“极端”板，一个好的猜测就足够了。
用于解决数独的快速算法是Donald Knuth的算法X.你代表解决数独作为exact cover问题，然后使用Algorithm X解决EC问题。然后使用DLX作为算法X的有效实现。
维基百科有很好的解释如何应用精确的封面来解决数独。
我可以告诉你，DLX在解决数独游戏方面非常快，常用于最快的算法。
http://www.setbb.com/phpbb/index.php?mforum=sudoku是伟大的论坛，可能是最好的数独程序员。
我不知道你以前是否看过这个链接。此外，它可能无法与舞蹈链接算法相媲美，因为它使用了幼稚的回溯形式。无论如何它是有效的。看看它对你有用！
也可以添加几行来解决'简单'方块。 http://edwinchan.wordpress.com/2006/01/08/sudoku-solver-in-c-using-backtracking/
你的算法看起来很好。问题是你使用的是蛮力方法，因此你的运行时间是（字符数）^（板的大小） - 所以对于9x9，有9 ^ 9 = 387420489，对于16x16，运行时间是16 ^ 16 = 18446744073709551616。你可以看到差异。
试着找一个Dynamic programing approach
没有必要只用一个可能的数字来处理细胞。您已经首先访问了具有最少可能性的单元格。
另外：当您“从3D矢量中删除该选项”时，您也可以将其从同一{row，columns，box}上的其他单元格中删除。 Bitmasks可能很适合。 （但回溯会变得有点困难）
正如@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;
}
你可以尝试:)