在 C++ 中解决数独问题
Sudoku solving in c++
我最近一直在用 C++ 开发数独游戏。我已经使用 SFML 制作了它的图形版本并且它工作得很好。但是，我需要实现一种算法来解决数独问题，而 not 是一种蛮力算法（因此回溯对我不起作用；/）。我已经阅读了很多解决它的方法，并且遇到了不同的算法名称（例如 Dancing Links），以及仅描述搜索如何工作而没有提供有关如何实现它的任何具体信息的算法C++。 （即为每个 "bucket" 分配一个 table 或可能的数字列表并搜索解决方案，还有人提到所谓的 A* 算法？）
所以这是我的问题，哪种算法相当容易实现并且不是回溯算法？在哪里可以找到关于如何在 C++ 中使用它的具体信息？提前致谢。
我的程序在二维数组上运行，但如果需要，我可以以某种方式将桶变成结构。
Peter Norvig 建议先使用消除（约束传播）过程再进行搜索。他的文章here提供了非常详尽的解释。
在约束传播中，您使用以下策略：
(1) If a square has only one possible value, then eliminate that value from the square's peers.
(2) If a unit has only one possible place for a value, then put the value there.
现在，很容易在 O(N) 时间内找到拼图中最初填满的方块。将它们全部排成一个队列。如果他们的邻居在传播约束后只有一个值，则将其添加到队列中。重复直到队列为空。
谜题现在要么已经解决，要么无法通过传播约束取得进一步进展。
如果难题没有解决，您可以使用更高级的算法，或者按照 Norvig 的建议，使用回溯法。由于回溯是在拼图的一个典型的小子集上执行的 space，您没有使用蛮力。
描述
我的数独以 32 位无符号整数的 2D 数组 9x9 形式存储，其中每一位都有自己的用途。低 10 位保留用于放置的数字（使用 9 位）接下来的 10 位保留用于可能的数字（可以放置在那里......尚未排除）最后一位告诉它一个固定的单元格和一个告诉是否存在错误（与另一个单元格冲突）。
正如您所想象的那样，我的代码归结为一堆二进制操作...它本身会带来一些问题但会解决其他问题...
求解器
如评论中所述，我为此使用规则和确定性方法（无回溯）。算法是这样的：
- 计算数独的校验和
- 应用规则
- 计算数独的校验和
- 而校验和与上一个循环不同 #2
- 检查错误
术语和约定
董事会地址为：
x = <0,9)
y = <0,9)
现在规则：
单例在 row/col/sqr
中必须是唯一的
所以如果我们得到的单元格只有一个放置的值，那么另一个这样的值就不可能出现在同一个 row/col/sqr 中，所以像这个例子一样清楚：
如果我们得到的单元格只剩下一个可能的数字，请放置它
这很简单，如果我们从其他规则中清除了足够多的可能数字，有时我们将只剩下一个选择。一旦检测到放置它，细胞就完成了...
相同的可能数字仅在单个 row/col 中用于单个正方形
如果找到其他方块，请清除 row/col，因为它们不能再放置此类数字。
在单个 row/col/sqr
中找到相同的一对
如果检测到清除其余部分。请注意这对必须完全相同（单元格中可能没有其他可能的数字）
这个规则可以扩展到 3 个三胞胎等，但从来没有机会这样做，因为基本规则以前解决过它们，而且它们的概率很低......
这里是小 C++/VCL 代码（规则 #4 尚未实现）：
//---------------------------------------------------------------------------
#ifndef _sudoku_h
#define _sudoku_h
//---------------------------------------------------------------------------
// set numbers
const DWORD _sudoku_1 =(1<< 0); // set numbers (used)
const DWORD _sudoku_a1 =(1<<10); // possible numbers (unused)
const DWORD _sudoku_fix =(1<<20); // read only?
const DWORD _sudoku_err =(1<<21); // error?
const DWORD _sudoku_2=(_sudoku_1<<1);
const DWORD _sudoku_3=(_sudoku_1<<2);
const DWORD _sudoku_4=(_sudoku_1<<3);
const DWORD _sudoku_5=(_sudoku_1<<4);
const DWORD _sudoku_6=(_sudoku_1<<5);
const DWORD _sudoku_7=(_sudoku_1<<6);
const DWORD _sudoku_8=(_sudoku_1<<7);
const DWORD _sudoku_9=(_sudoku_1<<8);
const DWORD _sudoku_n=_sudoku_1|_sudoku_2|_sudoku_3|_sudoku_4|_sudoku_5|_sudoku_6|_sudoku_7|_sudoku_8|_sudoku_9;
const DWORD _sudoku_a2=(_sudoku_a1<<1);
const DWORD _sudoku_a3=(_sudoku_a1<<2);
const DWORD _sudoku_a4=(_sudoku_a1<<3);
const DWORD _sudoku_a5=(_sudoku_a1<<4);
const DWORD _sudoku_a6=(_sudoku_a1<<5);
const DWORD _sudoku_a7=(_sudoku_a1<<6);
const DWORD _sudoku_a8=(_sudoku_a1<<7);
const DWORD _sudoku_a9=(_sudoku_a1<<8);
const DWORD _sudoku_an=_sudoku_a1|_sudoku_a2|_sudoku_a3|_sudoku_a4|_sudoku_a5|_sudoku_a6|_sudoku_a7|_sudoku_a8|_sudoku_a9;
//---------------------------------------------------------------------------
class sudoku
{
public:
DWORD map[9][9];
Graphics::TBitmap *bmp;
bool _redraw,_render_an;
int x0,y0; // grid start
int x1,y1; // grid end
int sz; // grid size
int yb; // y of buttons panel
int selx,sely,selb; // mouse selection
TShiftState sh0;
int _debug_N;
sudoku();
sudoku(sudoku& a) { *this=a; }
~sudoku();
sudoku* operator = (const sudoku *a) { *this=*a; return this; }
// sudoku* operator = (const sudoku &a) { ...copy... return this; }
// GUI/interface
void init(int *S); // init with linear mapped 1D array 0 is empty space, 1..9 is fixed cell
void draw();
void resize(int xs,int ys);
void mouse(int mx,int my,TShiftState sh);
void key(WORD key,TShiftState sh);
void load(AnsiString filename);
void save(AnsiString filename);
void set(int x,int y,DWORD m); // set map[x][y]|=m
void rst(int x,int y,DWORD m); // clear map[x][y]-=m
void xor(int x,int y,DWORD m); // xor map[x][y]^=m
// solver
void s_init(); // reset/init state from fixed cells only
void s_check(); // check for errors
void solve(); // solve the puzzle from scratch
};
//---------------------------------------------------------------------------
sudoku::sudoku()
{
int i,j;
_render_an=false;
_redraw=false;
selx=-1;
sely=-1;
selb=-1;
bmp=new Graphics::TBitmap;
for (i=0;i<9;i++)
for (j=0;j<9;j++)
map[i][j]=0;
}
//---------------------------------------------------------------------------
sudoku::~sudoku()
{
if (bmp) delete bmp; bmp=NULL;
}
//---------------------------------------------------------------------------
void sudoku::init(int *S)
{
int x,y,a;
for (a=0,y=0;y<9;y++)
for (x=0;x<9;x++,a++)
if (S[a]) map[x][y]=(_sudoku_1<<(S[a]-1))|_sudoku_fix;
else map[x][y]=0;
s_init();
_debug_N=0;
}
//---------------------------------------------------------------------------
void sudoku::draw()
{
if (bmp==NULL) return;
AnsiString s;
int i,j,k,x,y;
DWORD a;
// clear
bmp->Canvas->Brush->Color=clLtGray;
bmp->Canvas->Brush->Style=bsSolid;
bmp->Canvas->FillRect(Rect(0,0,bmp->Width,bmp->Height));
bmp->Canvas->Brush->Color=clWhite;
bmp->Canvas->FillRect(Rect(x0,y0,x1,y1));
// selection
if ((selx>=0)&&(selx<9))
if ((sely>=0)&&(sely<9))
{
x=x0+(selx*sz);
y=y0+(sely*sz);
bmp->Canvas->Brush->Color=clSilver;
bmp->Canvas->FillRect(Rect(x,y,x+sz,y+sz));
}
// buttons
bmp->Canvas->Pen ->Width=2;
bmp->Canvas->Brush->Color=clWhite;
bmp->Canvas->FillRect(Rect(x0,yb,x1,yb+sz));
if ((selb>=0)&&(selb<9))
{
x=x0+(selb*sz);
bmp->Canvas->Brush->Color=clDkGray;
bmp->Canvas->FillRect(Rect(x,yb,x+sz,yb+sz));
}
for (j=0,i=0;i<=9;i++,j+=sz)
{
bmp->Canvas->MoveTo(x0+j,yb);
bmp->Canvas->LineTo(x0+j,yb+sz);
}
bmp->Canvas->MoveTo(x0,yb);
bmp->Canvas->LineTo(x1,yb);
bmp->Canvas->MoveTo(x0,yb+sz);
bmp->Canvas->LineTo(x1,yb+sz);
// major grid
bmp->Canvas->Pen ->Color=clBlack;
for (j=0,i=0;i<=3;i++,j+=3*sz)
{
bmp->Canvas->MoveTo(x0,y0+j);
bmp->Canvas->LineTo(x1,y0+j);
bmp->Canvas->MoveTo(x0+j,y0);
bmp->Canvas->LineTo(x0+j,y1);
}
// minor grid
bmp->Canvas->Pen ->Width=1;
for (j=0,i=0;i<9;i++,j+=sz)
{
bmp->Canvas->MoveTo(x0,y0+j);
bmp->Canvas->LineTo(x1,y0+j);
bmp->Canvas->MoveTo(x0+j,y0);
bmp->Canvas->LineTo(x0+j,y1);
}
// big numbers
bmp->Canvas->Brush->Style=bsClear;
bmp->Canvas->Font->Height=sz-4;
for (i=0;i<9;i++)
for (j=0;j<9;j++)
{
a=map[i][j]; if (_render_an) a>>=10; a&=_sudoku_n; if (!a) continue;
if (DWORD(map[i][j]&_sudoku_err)!=0) bmp->Canvas->Font->Color=clRed;
else if (DWORD(map[i][j]&_sudoku_fix)!=0) bmp->Canvas->Font->Color=clBlack;
else bmp->Canvas->Font->Color=clBlue;
for (k=0;k<9;k++)
if (a==(_sudoku_1<<k))
{
s=k+1;
x=x0+(i*sz)+((sz-bmp->Canvas->TextWidth (s))>>1);
y=y0+(j*sz)+((sz-bmp->Canvas->TextHeight(s))>>1);
bmp->Canvas->TextOutA(x,y,s);
break;
}
}
// small numbers
bmp->Canvas->Brush->Style=bsClear;
i=(sz-4)/3;
const int dx[9]={-i,0,+i,-i,0,+i,-i,0,+i};
const int dy[9]={+i,+i,+i,0,0,0,-i,-i,-i};
bmp->Canvas->Font->Height=i;
for (i=0;i<9;i++)
for (j=0;j<9;j++)
{
a=map[i][j]; if (_render_an) a>>=10; a&=_sudoku_n; if (!a) continue;
for (k=0;k<9;k++) if (a==(_sudoku_1<<k)) { k=-1; break; } if (k<0) continue;
if (DWORD(map[i][j]&_sudoku_fix)!=0) bmp->Canvas->Font->Color=clBlack;
else if (DWORD(map[i][j]&_sudoku_err)!=0) bmp->Canvas->Font->Color=clRed;
else bmp->Canvas->Font->Color=clBlue;
for (k=0;k<9;k++)
if (DWORD(a&(_sudoku_1<<k))!=0)
{
s=k+1;
x=x0+(i*sz)+((sz-bmp->Canvas->TextWidth (s))>>1)+dx[k];
y=y0+(j*sz)+((sz-bmp->Canvas->TextHeight(s))>>1)+dy[k];
bmp->Canvas->TextOutA(x,y,s);
}
}
// info
x=5; y=5; i=20; y-=i;
bmp->Canvas->Font->Color=clBlack;
bmp->Canvas->TextOutA(x,y+=i,AnsiString().sprintf("N:%i",_debug_N));
bmp->Canvas->TextOutA(x,y+=i,AnsiString().sprintf("%ix%i",selx,sely));
if (_render_an) bmp->Canvas->TextOutA(x,y+=i,"an");
// button numbers
bmp->Canvas->Font->Height=sz-4;
a=0;
if ((selx>=0)&&(selx<9))
if ((sely>=0)&&(sely<9))
a=map[selx][sely]&_sudoku_n;
for (i=0;i<9;i++)
{
s=i+1;
x=x0+(i*sz)+((sz-bmp->Canvas->TextWidth (s))>>1);
y=yb +((sz-bmp->Canvas->TextHeight(s))>>1);
if (DWORD(a&(_sudoku_1<<i))!=0) bmp->Canvas->Font->Color=clBlack;
else bmp->Canvas->Font->Color=clLtGray;
bmp->Canvas->TextOutA(x,y,s);
}
bmp->Canvas->Brush->Style=bsSolid;
}
//---------------------------------------------------------------------------
void sudoku::resize(int xs,int ys)
{
bmp->SetSize(xs,ys);
_redraw=true;
int w=8;
x0=(xs-w-w )/ 9;
y0=(ys-w-w-w)/10;
sz=x0; if (sz>y0) sz=y0;
x0=(xs-( 9*sz))/2;
y0=(ys-(10*sz)-w)/2;
x1=x0+(9*sz);
y1=y0+(9*sz);
yb=y1+w;
}
//---------------------------------------------------------------------------
void sudoku::mouse(int mx,int my,TShiftState sh)
{
int q0=sh0.Contains(ssLeft);
int q1=sh .Contains(ssLeft);
if ((mx< x0)||(mx>=x1)) return;
if ((my>=y0)&&(my< y1))
if ((!q0)&&(q1))
{
selx=(mx-x0)/sz;
sely=(my-y0)/sz;
_redraw=true;
}
if ((my>=yb)&&(my< yb+sz))
{
selb=(mx-x0)/sz;
_redraw=true;
if ((!q0)&&(q1))
if ((selx>=0)&&(selx<9))
if ((sely>=0)&&(sely<9))
xor(selx,sely,_sudoku_1<<selb);
}
else{
_redraw|=selb!=-1;
selb=-1;
}
sh0=sh;
}
//---------------------------------------------------------------------------
void sudoku::key(WORD key,TShiftState sh)
{
// toggle (un)used number
int a=-1;
if ((key>='1')&&(key<='9')) a=key-'1'; // 0..9
if ((key>=97)&&(key<=105)) a=key-97; // num0..num9
if (a>=0)
if ((selx>=0)&&(selx<9))
if ((sely>=0)&&(sely<9))
{
if (_render_an) a+=10;
xor(selx,sely,_sudoku_1<<(a));
}
// navigate selection cell
if ((key>=37)&&(key<=40)) // arrows
{
if (key==37) { selx--; _redraw=true; }
if (key==39) { selx++; _redraw=true; }
if (key==38) { sely--; _redraw=true; }
if (key==40) { sely++; _redraw=true; }
if (selx<0) selx=0; if (selx>8) selx=8;
if (sely<0) sely=0; if (sely>8) sely=8;
}
if (key== 27) { _redraw=true; selx=-1; sely=-1; } // esc clear selection
if (key== 32) { solve(); } // space apply solving rules
if (key==112) { _redraw=true; _render_an=!_render_an; } // F1 used/unused numbers mode
if (key==113) { _redraw=true; save("map000.dat"); } // F2 save
if (key==116) { _redraw=true; load("map000.dat"); } // F5 load
if (key==119) { _redraw=true; s_init(); } // F8 restart
// debug
if (key==107) { _debug_N++; solve(); } // num+
if (key==109) { _debug_N--; solve(); } // num-
}
//---------------------------------------------------------------------------
void sudoku::load(AnsiString filename)
{
int hnd,x,y;
hnd=FileOpen(filename,fmOpenRead);
if (hnd<0) return;
for (x=0;x<9;x++)
for (y=0;y<9;y++)
FileRead(hnd,&map[x][y],sizeof(map[0][0]));
FileClose(hnd);
_redraw=true;
}
//---------------------------------------------------------------------------
void sudoku::save(AnsiString filename)
{
int hnd,x,y;
hnd=FileCreate(filename);
if (hnd<0) return;
for (x=0;x<9;x++)
for (y=0;y<9;y++)
FileWrite(hnd,&map[x][y],sizeof(map[0][0]));
FileClose(hnd);
}
//---------------------------------------------------------------------------
void sudoku::set(int x,int y,DWORD m)
{
if ((x<0)||(x>=9)||(y<0)||(y>=9)) return;
if (DWORD(map[x][y]&m)!=0) return;
if (DWORD(map[x][y]&_sudoku_fix)!=0) return;
map[x][y]|=m;
s_check();
_redraw=true;
}
//---------------------------------------------------------------------------
void sudoku::rst(int x,int y,DWORD m)
{
if ((x<0)||(x>=9)||(y<0)||(y>=9)) return;
if (DWORD(map[x][y]&m==0)) return;
if (DWORD(map[x][y]&_sudoku_fix)!=0) return;
map[x][y]|=m;
map[x][y]^=m;
s_check();
_redraw=true;
}
//---------------------------------------------------------------------------
void sudoku::xor(int x,int y,DWORD m)
{
if ((x<0)||(x>=9)||(y<0)||(y>=9)) return;
if (DWORD(map[selx][sely]&m)==0) set(selx,sely,m);
else rst(selx,sely,m);
}
//---------------------------------------------------------------------------
void sudoku::s_init()
{
int x,y;
DWORD a,b;
for (x=0;x<9;x++)
for (y=0;y<9;y++)
{
a=map[x][y];
if (DWORD(a&_sudoku_fix)==0) a =_sudoku_an;
else { a&=_sudoku_n|_sudoku_fix; a|=(a<<10)&_sudoku_an; }
map[x][y]=a;
}
s_check();
_redraw=true;
}
//---------------------------------------------------------------------------
void sudoku::s_check()
{
int x,y,_x,_y,xx,yy,k,n[10];
DWORD a,b,m[9][9];
// iterate xx,yy through adjacent cells to x,y (included)
#define row(y) for (yy=y,xx=0;xx<9;xx++)
#define col(x) for (xx=x,yy=0;yy<9;yy++)
#define sqr(x,y) for (_x=(x/3)*3,_y=(y/3)*3,xx=_x;xx<_x+3;xx++) for (yy=_y;yy<_y+3;yy++)
// init m[][] with singleton used numbers from map[][] and clear error
for (x=0;x<9;x++ ) for (y=0;y<9;y++ ){ m[x][y]=0; a=map[x][y]&_sudoku_n; map[x][y]&=0xFFFFFFFF^_sudoku_err; for (b=_sudoku_1,k=1;k<=9;k++,b<<=1) if (a==b) m[x][y]=k; }
// compute histogram n[] // check for error (count>1) and flag it for rendering
for (y=0;y<9;y++ ){ for (xx=0;xx<=9;xx++) n[xx]=0; row( y) n[m[xx][yy]]++; n[0]=0; row( y) if (n[m[xx][yy]]>1) map[xx][yy]|=_sudoku_err; }
for (x=0;x<9;x++ ) { for (xx=0;xx<=9;xx++) n[xx]=0; col(x ) n[m[xx][yy]]++; n[0]=0; col(x ) if (n[m[xx][yy]]>1) map[xx][yy]|=_sudoku_err; }
for (x=0;x<9;x+=3) for (y=0;y<9;y+=3){ for (xx=0;xx<=9;xx++) n[xx]=0; sqr(x,y) n[m[xx][yy]]++; n[0]=0; sqr(x,y) if (n[m[xx][yy]]>1) map[xx][yy]|=_sudoku_err; }
#undef row
#undef col
#undef sqr
}
//---------------------------------------------------------------------------
void sudoku::solve()
{
int k,n[9],nx[9],ny[9];
DWORD a,b;
int x,y,_x,_y,xx,yy;
DWORD checksum0,checksum;
// is a single bit set from _sudoku1.._sudoku_9?
#define single(a) for (b=_sudoku_1;b<=_sudoku_9;b<<=1) if (a==b)
// iterate xx,yy through adjacent cells to x,y (included)
#define row(y) for (yy=y,xx=0;xx<9;xx++)
#define col(x) for (xx=x,yy=0;yy<9;yy++)
#define sqr(x,y) for (_x=(x/3)*3,_y=(y/3)*3,xx=_x;xx<_x+3;xx++) for (yy=_y;yy<_y+3;yy++)
s_init();
// solve main loop
for (checksum0=0,_debug_N=0;;_debug_N++)
{
// compute checksum and stop if not changed
for (checksum=0,a=1,x=0;x<9;x++)
for (y=0;y<9;y++,a++)
checksum+=map[x][y]&(_sudoku_n|_sudoku_an)*a;
if (checksum==checksum0) break;
checksum0=checksum;
// #1 clear singleton used numbers in (un)used numbers of adjacent cells
for (x=0;x<9;x++)
for (y=0;y<9;y++)
{
a=map[x][y]&_sudoku_n;
single(a)
{
b=a<<10;
map[x][y]&=0xFFFFFFFF^_sudoku_an;
map[x][y]|=b;
b^=0xFFFFFFFF;
row( y) if (xx!=x) map[xx][yy]&=b;
col(x ) if (yy!=y) map[xx][yy]&=b;
sqr(x,y) if ((xx!=x)||(yy!=y)) map[xx][yy]&=b;
break;
}
}
// #2 find if just single occurence in adjacent cells
// clear histogram n[] compute histogram n[] // handle single occurence by clearing all other adjacent cells
for (y=0;y<9;y++ ){ for (xx=0;xx<9;xx++) n[xx]=0; row( y) { a=map[xx][yy]; a=(a|(a>>10))&_sudoku_n; for (b=0;b<9;b++) if (DWORD(a&(_sudoku_1<<b))!=0) { n[b]++; nx[b]=xx; ny[b]=yy; }} for (b=_sudoku_1|_sudoku_a1,k=0;k<9;k++,b<<=1) if (n[k]==1) row( y) if (DWORD(map[xx][yy]&_sudoku_fix)==0) if ((xx==nx[k])&&(yy==ny[k])) map[xx][yy]&=0xFFFFFFFF^(_sudoku_n|_sudoku_an)^b; else map[xx][yy]&=0xFFFFFFFF^b; }
for (x=0;x<9;x++ ) { for (xx=0;xx<9;xx++) n[xx]=0; col(x ) { a=map[xx][yy]; a=(a|(a>>10))&_sudoku_n; for (b=0;b<9;b++) if (DWORD(a&(_sudoku_1<<b))!=0) { n[b]++; nx[b]=xx; ny[b]=yy; }} for (b=_sudoku_1|_sudoku_a1,k=0;k<9;k++,b<<=1) if (n[k]==1) col(x ) if (DWORD(map[xx][yy]&_sudoku_fix)==0) if ((xx==nx[k])&&(yy==ny[k])) map[xx][yy]&=0xFFFFFFFF^(_sudoku_n|_sudoku_an)^b; else map[xx][yy]&=0xFFFFFFFF^b; }
for (x=0;x<9;x+=3) for (y=0;y<9;y+=3){ for (xx=0;xx<9;xx++) n[xx]=0; sqr(x,y) { a=map[xx][yy]; a=(a|(a>>10))&_sudoku_n; for (b=0;b<9;b++) if (DWORD(a&(_sudoku_1<<b))!=0) { n[b]++; nx[b]=xx; ny[b]=yy; }} for (b=_sudoku_1|_sudoku_a1,k=0;k<9;k++,b<<=1) if (n[k]==1) sqr(x,y) if (DWORD(map[xx][yy]&_sudoku_fix)==0) if ((xx==nx[k])&&(yy==ny[k])) map[xx][yy]&=0xFFFFFFFF^(_sudoku_n|_sudoku_an)^b; else map[xx][yy]&=0xFFFFFFFF^b; }
// #3 if the same number only in single row/col for single square clear the row/col for other squares
for (x=0;x<9;x+=3)
for (y=0;y<9;y+=3)
{
// nx[],ny[] = histogram of x,y per each number
for (xx=0;xx<9;xx++) { nx[xx]=0; ny[xx]=0; } sqr(x,y) for (a=map[xx][yy],b=_sudoku_1|_sudoku_a1,k=0;k<9;k++,b<<=1) if (DWORD(a&b)!=0) { nx[k]|=1<<xx; ny[k]|=1<<yy; }
// check row/col for exclusive occurence and clear the rest if found
for (yy=y;yy<y+3;yy++) for (b=_sudoku_1|_sudoku_a1,k=0;k<9;k++,b<<=1) if (ny[k]==1<<yy) for (xx=0;xx<9;xx++) if ((xx<x)||(xx>=x+3)) map[xx][yy]&=0xFFFFFFFF^b;
for (xx=x;xx<x+3;xx++) for (b=_sudoku_1|_sudoku_a1,k=0;k<9;k++,b<<=1) if (nx[k]==1<<xx) for (yy=0;yy<9;yy++) if ((yy<y)||(yy>=y+3)) map[xx][yy]&=0xFFFFFFFF^b;
}
// #4 same pair only found in single row/col/sqr (clear the rest)
// [***ToDo***]
// set singleton unused numbers as used
for (x=0;x<9;x++)
for (y=0;y<9;y++)
{
a=(map[x][y]>>10)&_sudoku_n;
single(a)
{
map[x][y]&=0xFFFFFFFF^_sudoku_n;
map[x][y]|=a;
break;
}
}
}
s_check();
_redraw=true;
#undef single
#undef row
#undef col
#undef sqr
}
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------
和用法：
//$$---- Form CPP ----
//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include "Unit1.h"
#include "sudoku.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
sudoku gam;
//---------------------------------------------------------------------------
void TForm1::draw()
{
if (gam._redraw) gam.draw();
Canvas->Draw(0,0,gam.bmp);
}
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner):TForm(Owner)
{
int S[9*9]=
{
8,0,0, 0,2,4, 0,0,3,
0,0,0, 0,0,0, 0,0,0,
0,4,0, 3,6,0, 0,0,0,
0,0,0, 0,0,0, 0,0,0,
4,6,0, 0,5,9, 0,0,8,
2,0,9, 0,0,8, 1,0,0,
3,0,0, 0,0,0, 6,0,0,
0,5,1, 7,0,0, 0,0,4,
0,9,0, 0,0,1, 3,0,0,
};
gam.init(S);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormPaint(TObject *Sender) { draw(); }
void __fastcall TForm1::FormResize(TObject *Sender) { gam.resize(ClientWidth,ClientHeight); }
void __fastcall TForm1::tim_updTimer(TObject *Sender) { if (gam._redraw) draw(); }
void __fastcall TForm1::FormKeyDown (TObject *Sender, WORD &Key, TShiftState Shift){ gam.key(Key,Shift); }
void __fastcall TForm1::FormMouseMove(TObject *Sender, TShiftState Shift, int X, int Y){ gam.mouse(X,Y,Shift); }
void __fastcall TForm1::FormMouseDown(TObject *Sender, TMouseButton Button, TShiftState Shift, int X, int Y){ gam.mouse(X,Y,Shift); }
void __fastcall TForm1::FormMouseUp (TObject *Sender, TMouseButton Button, TShiftState Shift, int X, int Y){ gam.mouse(X,Y,Shift); }
//---------------------------------------------------------------------------
它是我的 VCL 应用程序的代码（单个 form 和单个 timer ）所以只需将事件移植到您的环境并忽略休息。数独 class 使用 VCL 封装 GDI 所以这是需要移植的东西（只是线条矩形和文本）。
求解器完全包含在 sudoku::solve() 中，希望它的评论足够多（完全符合我上面描述的内容）。解决后的截图（space键）：
_debug_N (N:7) 保存求解所需的迭代次数。此外，我还没有做任何优化（看不到任何意义，因为求解器比我释放密钥更快地完成）。希望这对某人有所帮助。
还有很多其他规则需要实施：
我最近一直在用 C++ 开发数独游戏。我已经使用 SFML 制作了它的图形版本并且它工作得很好。但是，我需要实现一种算法来解决数独问题，而 not 是一种蛮力算法（因此回溯对我不起作用；/）。我已经阅读了很多解决它的方法，并且遇到了不同的算法名称（例如 Dancing Links），以及仅描述搜索如何工作而没有提供有关如何实现它的任何具体信息的算法C++。 （即为每个 "bucket" 分配一个 table 或可能的数字列表并搜索解决方案，还有人提到所谓的 A* 算法？）
所以这是我的问题，哪种算法相当容易实现并且不是回溯算法？在哪里可以找到关于如何在 C++ 中使用它的具体信息？提前致谢。 我的程序在二维数组上运行，但如果需要，我可以以某种方式将桶变成结构。
Peter Norvig 建议先使用消除（约束传播）过程再进行搜索。他的文章here提供了非常详尽的解释。
在约束传播中，您使用以下策略：
(1) If a square has only one possible value, then eliminate that value from the square's peers.
(2) If a unit has only one possible place for a value, then put the value there.
现在，很容易在 O(N) 时间内找到拼图中最初填满的方块。将它们全部排成一个队列。如果他们的邻居在传播约束后只有一个值，则将其添加到队列中。重复直到队列为空。
谜题现在要么已经解决，要么无法通过传播约束取得进一步进展。
如果难题没有解决，您可以使用更高级的算法，或者按照 Norvig 的建议，使用回溯法。由于回溯是在拼图的一个典型的小子集上执行的 space，您没有使用蛮力。
描述
我的数独以 32 位无符号整数的 2D 数组 9x9 形式存储，其中每一位都有自己的用途。低 10 位保留用于放置的数字（使用 9 位）接下来的 10 位保留用于可能的数字（可以放置在那里......尚未排除）最后一位告诉它一个固定的单元格和一个告诉是否存在错误（与另一个单元格冲突）。
正如您所想象的那样，我的代码归结为一堆二进制操作...它本身会带来一些问题但会解决其他问题...
求解器
如评论中所述，我为此使用规则和确定性方法（无回溯）。算法是这样的：
- 计算数独的校验和
- 应用规则
- 计算数独的校验和
- 而校验和与上一个循环不同 #2
- 检查错误
术语和约定
董事会地址为：
x = <0,9)
y = <0,9)
现在规则：
单例在 row/col/sqr
中必须是唯一的所以如果我们得到的单元格只有一个放置的值，那么另一个这样的值就不可能出现在同一个 row/col/sqr 中，所以像这个例子一样清楚：
如果我们得到的单元格只剩下一个可能的数字，请放置它
这很简单，如果我们从其他规则中清除了足够多的可能数字，有时我们将只剩下一个选择。一旦检测到放置它，细胞就完成了...
相同的可能数字仅在单个 row/col 中用于单个正方形
如果找到其他方块，请清除 row/col，因为它们不能再放置此类数字。
在单个 row/col/sqr
中找到相同的一对如果检测到清除其余部分。请注意这对必须完全相同（单元格中可能没有其他可能的数字）
这个规则可以扩展到 3 个三胞胎等，但从来没有机会这样做，因为基本规则以前解决过它们，而且它们的概率很低......
这里是小 C++/VCL 代码（规则 #4 尚未实现）：
//---------------------------------------------------------------------------
#ifndef _sudoku_h
#define _sudoku_h
//---------------------------------------------------------------------------
// set numbers
const DWORD _sudoku_1 =(1<< 0); // set numbers (used)
const DWORD _sudoku_a1 =(1<<10); // possible numbers (unused)
const DWORD _sudoku_fix =(1<<20); // read only?
const DWORD _sudoku_err =(1<<21); // error?
const DWORD _sudoku_2=(_sudoku_1<<1);
const DWORD _sudoku_3=(_sudoku_1<<2);
const DWORD _sudoku_4=(_sudoku_1<<3);
const DWORD _sudoku_5=(_sudoku_1<<4);
const DWORD _sudoku_6=(_sudoku_1<<5);
const DWORD _sudoku_7=(_sudoku_1<<6);
const DWORD _sudoku_8=(_sudoku_1<<7);
const DWORD _sudoku_9=(_sudoku_1<<8);
const DWORD _sudoku_n=_sudoku_1|_sudoku_2|_sudoku_3|_sudoku_4|_sudoku_5|_sudoku_6|_sudoku_7|_sudoku_8|_sudoku_9;
const DWORD _sudoku_a2=(_sudoku_a1<<1);
const DWORD _sudoku_a3=(_sudoku_a1<<2);
const DWORD _sudoku_a4=(_sudoku_a1<<3);
const DWORD _sudoku_a5=(_sudoku_a1<<4);
const DWORD _sudoku_a6=(_sudoku_a1<<5);
const DWORD _sudoku_a7=(_sudoku_a1<<6);
const DWORD _sudoku_a8=(_sudoku_a1<<7);
const DWORD _sudoku_a9=(_sudoku_a1<<8);
const DWORD _sudoku_an=_sudoku_a1|_sudoku_a2|_sudoku_a3|_sudoku_a4|_sudoku_a5|_sudoku_a6|_sudoku_a7|_sudoku_a8|_sudoku_a9;
//---------------------------------------------------------------------------
class sudoku
{
public:
DWORD map[9][9];
Graphics::TBitmap *bmp;
bool _redraw,_render_an;
int x0,y0; // grid start
int x1,y1; // grid end
int sz; // grid size
int yb; // y of buttons panel
int selx,sely,selb; // mouse selection
TShiftState sh0;
int _debug_N;
sudoku();
sudoku(sudoku& a) { *this=a; }
~sudoku();
sudoku* operator = (const sudoku *a) { *this=*a; return this; }
// sudoku* operator = (const sudoku &a) { ...copy... return this; }
// GUI/interface
void init(int *S); // init with linear mapped 1D array 0 is empty space, 1..9 is fixed cell
void draw();
void resize(int xs,int ys);
void mouse(int mx,int my,TShiftState sh);
void key(WORD key,TShiftState sh);
void load(AnsiString filename);
void save(AnsiString filename);
void set(int x,int y,DWORD m); // set map[x][y]|=m
void rst(int x,int y,DWORD m); // clear map[x][y]-=m
void xor(int x,int y,DWORD m); // xor map[x][y]^=m
// solver
void s_init(); // reset/init state from fixed cells only
void s_check(); // check for errors
void solve(); // solve the puzzle from scratch
};
//---------------------------------------------------------------------------
sudoku::sudoku()
{
int i,j;
_render_an=false;
_redraw=false;
selx=-1;
sely=-1;
selb=-1;
bmp=new Graphics::TBitmap;
for (i=0;i<9;i++)
for (j=0;j<9;j++)
map[i][j]=0;
}
//---------------------------------------------------------------------------
sudoku::~sudoku()
{
if (bmp) delete bmp; bmp=NULL;
}
//---------------------------------------------------------------------------
void sudoku::init(int *S)
{
int x,y,a;
for (a=0,y=0;y<9;y++)
for (x=0;x<9;x++,a++)
if (S[a]) map[x][y]=(_sudoku_1<<(S[a]-1))|_sudoku_fix;
else map[x][y]=0;
s_init();
_debug_N=0;
}
//---------------------------------------------------------------------------
void sudoku::draw()
{
if (bmp==NULL) return;
AnsiString s;
int i,j,k,x,y;
DWORD a;
// clear
bmp->Canvas->Brush->Color=clLtGray;
bmp->Canvas->Brush->Style=bsSolid;
bmp->Canvas->FillRect(Rect(0,0,bmp->Width,bmp->Height));
bmp->Canvas->Brush->Color=clWhite;
bmp->Canvas->FillRect(Rect(x0,y0,x1,y1));
// selection
if ((selx>=0)&&(selx<9))
if ((sely>=0)&&(sely<9))
{
x=x0+(selx*sz);
y=y0+(sely*sz);
bmp->Canvas->Brush->Color=clSilver;
bmp->Canvas->FillRect(Rect(x,y,x+sz,y+sz));
}
// buttons
bmp->Canvas->Pen ->Width=2;
bmp->Canvas->Brush->Color=clWhite;
bmp->Canvas->FillRect(Rect(x0,yb,x1,yb+sz));
if ((selb>=0)&&(selb<9))
{
x=x0+(selb*sz);
bmp->Canvas->Brush->Color=clDkGray;
bmp->Canvas->FillRect(Rect(x,yb,x+sz,yb+sz));
}
for (j=0,i=0;i<=9;i++,j+=sz)
{
bmp->Canvas->MoveTo(x0+j,yb);
bmp->Canvas->LineTo(x0+j,yb+sz);
}
bmp->Canvas->MoveTo(x0,yb);
bmp->Canvas->LineTo(x1,yb);
bmp->Canvas->MoveTo(x0,yb+sz);
bmp->Canvas->LineTo(x1,yb+sz);
// major grid
bmp->Canvas->Pen ->Color=clBlack;
for (j=0,i=0;i<=3;i++,j+=3*sz)
{
bmp->Canvas->MoveTo(x0,y0+j);
bmp->Canvas->LineTo(x1,y0+j);
bmp->Canvas->MoveTo(x0+j,y0);
bmp->Canvas->LineTo(x0+j,y1);
}
// minor grid
bmp->Canvas->Pen ->Width=1;
for (j=0,i=0;i<9;i++,j+=sz)
{
bmp->Canvas->MoveTo(x0,y0+j);
bmp->Canvas->LineTo(x1,y0+j);
bmp->Canvas->MoveTo(x0+j,y0);
bmp->Canvas->LineTo(x0+j,y1);
}
// big numbers
bmp->Canvas->Brush->Style=bsClear;
bmp->Canvas->Font->Height=sz-4;
for (i=0;i<9;i++)
for (j=0;j<9;j++)
{
a=map[i][j]; if (_render_an) a>>=10; a&=_sudoku_n; if (!a) continue;
if (DWORD(map[i][j]&_sudoku_err)!=0) bmp->Canvas->Font->Color=clRed;
else if (DWORD(map[i][j]&_sudoku_fix)!=0) bmp->Canvas->Font->Color=clBlack;
else bmp->Canvas->Font->Color=clBlue;
for (k=0;k<9;k++)
if (a==(_sudoku_1<<k))
{
s=k+1;
x=x0+(i*sz)+((sz-bmp->Canvas->TextWidth (s))>>1);
y=y0+(j*sz)+((sz-bmp->Canvas->TextHeight(s))>>1);
bmp->Canvas->TextOutA(x,y,s);
break;
}
}
// small numbers
bmp->Canvas->Brush->Style=bsClear;
i=(sz-4)/3;
const int dx[9]={-i,0,+i,-i,0,+i,-i,0,+i};
const int dy[9]={+i,+i,+i,0,0,0,-i,-i,-i};
bmp->Canvas->Font->Height=i;
for (i=0;i<9;i++)
for (j=0;j<9;j++)
{
a=map[i][j]; if (_render_an) a>>=10; a&=_sudoku_n; if (!a) continue;
for (k=0;k<9;k++) if (a==(_sudoku_1<<k)) { k=-1; break; } if (k<0) continue;
if (DWORD(map[i][j]&_sudoku_fix)!=0) bmp->Canvas->Font->Color=clBlack;
else if (DWORD(map[i][j]&_sudoku_err)!=0) bmp->Canvas->Font->Color=clRed;
else bmp->Canvas->Font->Color=clBlue;
for (k=0;k<9;k++)
if (DWORD(a&(_sudoku_1<<k))!=0)
{
s=k+1;
x=x0+(i*sz)+((sz-bmp->Canvas->TextWidth (s))>>1)+dx[k];
y=y0+(j*sz)+((sz-bmp->Canvas->TextHeight(s))>>1)+dy[k];
bmp->Canvas->TextOutA(x,y,s);
}
}
// info
x=5; y=5; i=20; y-=i;
bmp->Canvas->Font->Color=clBlack;
bmp->Canvas->TextOutA(x,y+=i,AnsiString().sprintf("N:%i",_debug_N));
bmp->Canvas->TextOutA(x,y+=i,AnsiString().sprintf("%ix%i",selx,sely));
if (_render_an) bmp->Canvas->TextOutA(x,y+=i,"an");
// button numbers
bmp->Canvas->Font->Height=sz-4;
a=0;
if ((selx>=0)&&(selx<9))
if ((sely>=0)&&(sely<9))
a=map[selx][sely]&_sudoku_n;
for (i=0;i<9;i++)
{
s=i+1;
x=x0+(i*sz)+((sz-bmp->Canvas->TextWidth (s))>>1);
y=yb +((sz-bmp->Canvas->TextHeight(s))>>1);
if (DWORD(a&(_sudoku_1<<i))!=0) bmp->Canvas->Font->Color=clBlack;
else bmp->Canvas->Font->Color=clLtGray;
bmp->Canvas->TextOutA(x,y,s);
}
bmp->Canvas->Brush->Style=bsSolid;
}
//---------------------------------------------------------------------------
void sudoku::resize(int xs,int ys)
{
bmp->SetSize(xs,ys);
_redraw=true;
int w=8;
x0=(xs-w-w )/ 9;
y0=(ys-w-w-w)/10;
sz=x0; if (sz>y0) sz=y0;
x0=(xs-( 9*sz))/2;
y0=(ys-(10*sz)-w)/2;
x1=x0+(9*sz);
y1=y0+(9*sz);
yb=y1+w;
}
//---------------------------------------------------------------------------
void sudoku::mouse(int mx,int my,TShiftState sh)
{
int q0=sh0.Contains(ssLeft);
int q1=sh .Contains(ssLeft);
if ((mx< x0)||(mx>=x1)) return;
if ((my>=y0)&&(my< y1))
if ((!q0)&&(q1))
{
selx=(mx-x0)/sz;
sely=(my-y0)/sz;
_redraw=true;
}
if ((my>=yb)&&(my< yb+sz))
{
selb=(mx-x0)/sz;
_redraw=true;
if ((!q0)&&(q1))
if ((selx>=0)&&(selx<9))
if ((sely>=0)&&(sely<9))
xor(selx,sely,_sudoku_1<<selb);
}
else{
_redraw|=selb!=-1;
selb=-1;
}
sh0=sh;
}
//---------------------------------------------------------------------------
void sudoku::key(WORD key,TShiftState sh)
{
// toggle (un)used number
int a=-1;
if ((key>='1')&&(key<='9')) a=key-'1'; // 0..9
if ((key>=97)&&(key<=105)) a=key-97; // num0..num9
if (a>=0)
if ((selx>=0)&&(selx<9))
if ((sely>=0)&&(sely<9))
{
if (_render_an) a+=10;
xor(selx,sely,_sudoku_1<<(a));
}
// navigate selection cell
if ((key>=37)&&(key<=40)) // arrows
{
if (key==37) { selx--; _redraw=true; }
if (key==39) { selx++; _redraw=true; }
if (key==38) { sely--; _redraw=true; }
if (key==40) { sely++; _redraw=true; }
if (selx<0) selx=0; if (selx>8) selx=8;
if (sely<0) sely=0; if (sely>8) sely=8;
}
if (key== 27) { _redraw=true; selx=-1; sely=-1; } // esc clear selection
if (key== 32) { solve(); } // space apply solving rules
if (key==112) { _redraw=true; _render_an=!_render_an; } // F1 used/unused numbers mode
if (key==113) { _redraw=true; save("map000.dat"); } // F2 save
if (key==116) { _redraw=true; load("map000.dat"); } // F5 load
if (key==119) { _redraw=true; s_init(); } // F8 restart
// debug
if (key==107) { _debug_N++; solve(); } // num+
if (key==109) { _debug_N--; solve(); } // num-
}
//---------------------------------------------------------------------------
void sudoku::load(AnsiString filename)
{
int hnd,x,y;
hnd=FileOpen(filename,fmOpenRead);
if (hnd<0) return;
for (x=0;x<9;x++)
for (y=0;y<9;y++)
FileRead(hnd,&map[x][y],sizeof(map[0][0]));
FileClose(hnd);
_redraw=true;
}
//---------------------------------------------------------------------------
void sudoku::save(AnsiString filename)
{
int hnd,x,y;
hnd=FileCreate(filename);
if (hnd<0) return;
for (x=0;x<9;x++)
for (y=0;y<9;y++)
FileWrite(hnd,&map[x][y],sizeof(map[0][0]));
FileClose(hnd);
}
//---------------------------------------------------------------------------
void sudoku::set(int x,int y,DWORD m)
{
if ((x<0)||(x>=9)||(y<0)||(y>=9)) return;
if (DWORD(map[x][y]&m)!=0) return;
if (DWORD(map[x][y]&_sudoku_fix)!=0) return;
map[x][y]|=m;
s_check();
_redraw=true;
}
//---------------------------------------------------------------------------
void sudoku::rst(int x,int y,DWORD m)
{
if ((x<0)||(x>=9)||(y<0)||(y>=9)) return;
if (DWORD(map[x][y]&m==0)) return;
if (DWORD(map[x][y]&_sudoku_fix)!=0) return;
map[x][y]|=m;
map[x][y]^=m;
s_check();
_redraw=true;
}
//---------------------------------------------------------------------------
void sudoku::xor(int x,int y,DWORD m)
{
if ((x<0)||(x>=9)||(y<0)||(y>=9)) return;
if (DWORD(map[selx][sely]&m)==0) set(selx,sely,m);
else rst(selx,sely,m);
}
//---------------------------------------------------------------------------
void sudoku::s_init()
{
int x,y;
DWORD a,b;
for (x=0;x<9;x++)
for (y=0;y<9;y++)
{
a=map[x][y];
if (DWORD(a&_sudoku_fix)==0) a =_sudoku_an;
else { a&=_sudoku_n|_sudoku_fix; a|=(a<<10)&_sudoku_an; }
map[x][y]=a;
}
s_check();
_redraw=true;
}
//---------------------------------------------------------------------------
void sudoku::s_check()
{
int x,y,_x,_y,xx,yy,k,n[10];
DWORD a,b,m[9][9];
// iterate xx,yy through adjacent cells to x,y (included)
#define row(y) for (yy=y,xx=0;xx<9;xx++)
#define col(x) for (xx=x,yy=0;yy<9;yy++)
#define sqr(x,y) for (_x=(x/3)*3,_y=(y/3)*3,xx=_x;xx<_x+3;xx++) for (yy=_y;yy<_y+3;yy++)
// init m[][] with singleton used numbers from map[][] and clear error
for (x=0;x<9;x++ ) for (y=0;y<9;y++ ){ m[x][y]=0; a=map[x][y]&_sudoku_n; map[x][y]&=0xFFFFFFFF^_sudoku_err; for (b=_sudoku_1,k=1;k<=9;k++,b<<=1) if (a==b) m[x][y]=k; }
// compute histogram n[] // check for error (count>1) and flag it for rendering
for (y=0;y<9;y++ ){ for (xx=0;xx<=9;xx++) n[xx]=0; row( y) n[m[xx][yy]]++; n[0]=0; row( y) if (n[m[xx][yy]]>1) map[xx][yy]|=_sudoku_err; }
for (x=0;x<9;x++ ) { for (xx=0;xx<=9;xx++) n[xx]=0; col(x ) n[m[xx][yy]]++; n[0]=0; col(x ) if (n[m[xx][yy]]>1) map[xx][yy]|=_sudoku_err; }
for (x=0;x<9;x+=3) for (y=0;y<9;y+=3){ for (xx=0;xx<=9;xx++) n[xx]=0; sqr(x,y) n[m[xx][yy]]++; n[0]=0; sqr(x,y) if (n[m[xx][yy]]>1) map[xx][yy]|=_sudoku_err; }
#undef row
#undef col
#undef sqr
}
//---------------------------------------------------------------------------
void sudoku::solve()
{
int k,n[9],nx[9],ny[9];
DWORD a,b;
int x,y,_x,_y,xx,yy;
DWORD checksum0,checksum;
// is a single bit set from _sudoku1.._sudoku_9?
#define single(a) for (b=_sudoku_1;b<=_sudoku_9;b<<=1) if (a==b)
// iterate xx,yy through adjacent cells to x,y (included)
#define row(y) for (yy=y,xx=0;xx<9;xx++)
#define col(x) for (xx=x,yy=0;yy<9;yy++)
#define sqr(x,y) for (_x=(x/3)*3,_y=(y/3)*3,xx=_x;xx<_x+3;xx++) for (yy=_y;yy<_y+3;yy++)
s_init();
// solve main loop
for (checksum0=0,_debug_N=0;;_debug_N++)
{
// compute checksum and stop if not changed
for (checksum=0,a=1,x=0;x<9;x++)
for (y=0;y<9;y++,a++)
checksum+=map[x][y]&(_sudoku_n|_sudoku_an)*a;
if (checksum==checksum0) break;
checksum0=checksum;
// #1 clear singleton used numbers in (un)used numbers of adjacent cells
for (x=0;x<9;x++)
for (y=0;y<9;y++)
{
a=map[x][y]&_sudoku_n;
single(a)
{
b=a<<10;
map[x][y]&=0xFFFFFFFF^_sudoku_an;
map[x][y]|=b;
b^=0xFFFFFFFF;
row( y) if (xx!=x) map[xx][yy]&=b;
col(x ) if (yy!=y) map[xx][yy]&=b;
sqr(x,y) if ((xx!=x)||(yy!=y)) map[xx][yy]&=b;
break;
}
}
// #2 find if just single occurence in adjacent cells
// clear histogram n[] compute histogram n[] // handle single occurence by clearing all other adjacent cells
for (y=0;y<9;y++ ){ for (xx=0;xx<9;xx++) n[xx]=0; row( y) { a=map[xx][yy]; a=(a|(a>>10))&_sudoku_n; for (b=0;b<9;b++) if (DWORD(a&(_sudoku_1<<b))!=0) { n[b]++; nx[b]=xx; ny[b]=yy; }} for (b=_sudoku_1|_sudoku_a1,k=0;k<9;k++,b<<=1) if (n[k]==1) row( y) if (DWORD(map[xx][yy]&_sudoku_fix)==0) if ((xx==nx[k])&&(yy==ny[k])) map[xx][yy]&=0xFFFFFFFF^(_sudoku_n|_sudoku_an)^b; else map[xx][yy]&=0xFFFFFFFF^b; }
for (x=0;x<9;x++ ) { for (xx=0;xx<9;xx++) n[xx]=0; col(x ) { a=map[xx][yy]; a=(a|(a>>10))&_sudoku_n; for (b=0;b<9;b++) if (DWORD(a&(_sudoku_1<<b))!=0) { n[b]++; nx[b]=xx; ny[b]=yy; }} for (b=_sudoku_1|_sudoku_a1,k=0;k<9;k++,b<<=1) if (n[k]==1) col(x ) if (DWORD(map[xx][yy]&_sudoku_fix)==0) if ((xx==nx[k])&&(yy==ny[k])) map[xx][yy]&=0xFFFFFFFF^(_sudoku_n|_sudoku_an)^b; else map[xx][yy]&=0xFFFFFFFF^b; }
for (x=0;x<9;x+=3) for (y=0;y<9;y+=3){ for (xx=0;xx<9;xx++) n[xx]=0; sqr(x,y) { a=map[xx][yy]; a=(a|(a>>10))&_sudoku_n; for (b=0;b<9;b++) if (DWORD(a&(_sudoku_1<<b))!=0) { n[b]++; nx[b]=xx; ny[b]=yy; }} for (b=_sudoku_1|_sudoku_a1,k=0;k<9;k++,b<<=1) if (n[k]==1) sqr(x,y) if (DWORD(map[xx][yy]&_sudoku_fix)==0) if ((xx==nx[k])&&(yy==ny[k])) map[xx][yy]&=0xFFFFFFFF^(_sudoku_n|_sudoku_an)^b; else map[xx][yy]&=0xFFFFFFFF^b; }
// #3 if the same number only in single row/col for single square clear the row/col for other squares
for (x=0;x<9;x+=3)
for (y=0;y<9;y+=3)
{
// nx[],ny[] = histogram of x,y per each number
for (xx=0;xx<9;xx++) { nx[xx]=0; ny[xx]=0; } sqr(x,y) for (a=map[xx][yy],b=_sudoku_1|_sudoku_a1,k=0;k<9;k++,b<<=1) if (DWORD(a&b)!=0) { nx[k]|=1<<xx; ny[k]|=1<<yy; }
// check row/col for exclusive occurence and clear the rest if found
for (yy=y;yy<y+3;yy++) for (b=_sudoku_1|_sudoku_a1,k=0;k<9;k++,b<<=1) if (ny[k]==1<<yy) for (xx=0;xx<9;xx++) if ((xx<x)||(xx>=x+3)) map[xx][yy]&=0xFFFFFFFF^b;
for (xx=x;xx<x+3;xx++) for (b=_sudoku_1|_sudoku_a1,k=0;k<9;k++,b<<=1) if (nx[k]==1<<xx) for (yy=0;yy<9;yy++) if ((yy<y)||(yy>=y+3)) map[xx][yy]&=0xFFFFFFFF^b;
}
// #4 same pair only found in single row/col/sqr (clear the rest)
// [***ToDo***]
// set singleton unused numbers as used
for (x=0;x<9;x++)
for (y=0;y<9;y++)
{
a=(map[x][y]>>10)&_sudoku_n;
single(a)
{
map[x][y]&=0xFFFFFFFF^_sudoku_n;
map[x][y]|=a;
break;
}
}
}
s_check();
_redraw=true;
#undef single
#undef row
#undef col
#undef sqr
}
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------
和用法：
//$$---- Form CPP ----
//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include "Unit1.h"
#include "sudoku.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
sudoku gam;
//---------------------------------------------------------------------------
void TForm1::draw()
{
if (gam._redraw) gam.draw();
Canvas->Draw(0,0,gam.bmp);
}
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner):TForm(Owner)
{
int S[9*9]=
{
8,0,0, 0,2,4, 0,0,3,
0,0,0, 0,0,0, 0,0,0,
0,4,0, 3,6,0, 0,0,0,
0,0,0, 0,0,0, 0,0,0,
4,6,0, 0,5,9, 0,0,8,
2,0,9, 0,0,8, 1,0,0,
3,0,0, 0,0,0, 6,0,0,
0,5,1, 7,0,0, 0,0,4,
0,9,0, 0,0,1, 3,0,0,
};
gam.init(S);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormPaint(TObject *Sender) { draw(); }
void __fastcall TForm1::FormResize(TObject *Sender) { gam.resize(ClientWidth,ClientHeight); }
void __fastcall TForm1::tim_updTimer(TObject *Sender) { if (gam._redraw) draw(); }
void __fastcall TForm1::FormKeyDown (TObject *Sender, WORD &Key, TShiftState Shift){ gam.key(Key,Shift); }
void __fastcall TForm1::FormMouseMove(TObject *Sender, TShiftState Shift, int X, int Y){ gam.mouse(X,Y,Shift); }
void __fastcall TForm1::FormMouseDown(TObject *Sender, TMouseButton Button, TShiftState Shift, int X, int Y){ gam.mouse(X,Y,Shift); }
void __fastcall TForm1::FormMouseUp (TObject *Sender, TMouseButton Button, TShiftState Shift, int X, int Y){ gam.mouse(X,Y,Shift); }
//---------------------------------------------------------------------------
它是我的 VCL 应用程序的代码（单个 form 和单个 timer ）所以只需将事件移植到您的环境并忽略休息。数独 class 使用 VCL 封装 GDI 所以这是需要移植的东西（只是线条矩形和文本）。
求解器完全包含在 sudoku::solve() 中，希望它的评论足够多（完全符合我上面描述的内容）。解决后的截图（space键）：
_debug_N (N:7) 保存求解所需的迭代次数。此外，我还没有做任何优化（看不到任何意义，因为求解器比我释放密钥更快地完成）。希望这对某人有所帮助。
还有很多其他规则需要实施：