壹、步驟:
1.對每壹個空格,根據規則推斷它可能填入的數字,並存儲它的所有可能值;
2.根據可能值的個數,確定填寫的順序。比如說,有些空格只有壹種可能,那必然是正確的結果,首先填入。
3.將所有只有壹種可能的空格填寫完畢以後,回到步驟1,重新確定剩下空格的可能值;
4.當沒有只有壹種可能的空格時(即每個空格都有兩種以上可能),按照可能值個數從小到大的順序,使用深度(廣度)優先搜索,完成剩下空格。
二、例程:
#include?<windows.h>#include?<stdio.h>
#include?<time.h>
char?sd[81];
bool?isok?=?false;
//顯示數獨
void?show()
{
if?(isok)?puts("求解完成"); else?puts("初始化完成"); for?(int?i?=?0;?i?<?81;?i++) { putchar(sd[i]?+?'0'); if?((i?+?1)?%?9?==?0)?putchar('\n'); } putchar('\n');}
//讀取數獨
bool?Init()
{
FILE?*fp?=?fopen("in.txt",?"rb"); if?(fp?==?NULL)?return?false; fread(sd,?81,?1,?fp); fclose(fp); for?(int?i?=?0;?i?<?81;?i++) { if?(sd[i]?>=?'1'?&&?sd[i]?<=?'9')?sd[i]?-=?'0'; else?sd[i]?=?0; } show(); return?true;}
//遞歸解決數獨
void?force(int?k)
{
if?(isok)?return; if?(!sd[k]) { for?(int?m?=?1;?m?<=?9;?m++) {bool?mm?=?true;
for?(int?n?=?0;?n?<?9;?n++)
{
if?((m?==?sd[k/27*27+(k%9/3)*3+n+n/3*6])?||?(m?==?sd[9*n+k%9])?||?(m?==?sd[k/9*9+n]))
{
mm?=?false; break;}
}
if?(mm)
{
sd[k]?=?m;
if?(k?==?80)
{
isok?=?true; show(); return;}
force(k?+?1);
}
} sd[k]?=?0; } else { if?(k?==?80) {isok?=?true;
show();
return;
} force(k?+?1); }}
int?main()
{
system("CLS"); if?(Init()) { double?start?=?clock(); force(0); printf("耗時%.0fms",?clock()?-?start); } else?puts("初始化錯誤"); getchar();}