知識+ 數獨程式

//===================================================================
// 20090407 知識 +
// http://tw.knowledge.yahoo.com/question/question?qid=1609040705045
// 發問者 : http://tw.knowledge.yahoo.com/my/my?show=AC00680853
//===================================================================

#include <iostream>

using namespace std;

int lookup(int[][9]);
int fillin(int[][9]);
int determine(int[][9]);
int paste(int[][9], int[][9]);

int block[9][9];

const int turnI=28;
const int turnII=53;

void _ClearBoard(void);
void _ShowBoard(int[][9]);
void _ShowRule(void);
void _DefaultBoard(void);
int typein(int);
int check(int, int, int);
int result(int[][9]);

int main()
{
int chkI, chkII;
int ret = 1;
while(ret)
{
_ClearBoard();
cout << endl;
cout << "******** SUDOKU 數獨 ********" << endl;
cout << "想瞭解9*9數獨的規則請按0，想要自己輸入題目請按1，指定程設題目請按2:" << endl;
cin >> chkI;
if (chkI == 0)
{
_ShowRule();
continue;
}
if (chkI == 1)
{
cout << "請輸入28個數字及其位置:" << endl;
if (typein(turnI)==0) continue;
}
else if (chkI == 2)
{
_DefaultBoard();
_ShowBoard(block);
}
else continue;

cout << "想自己玩請按1，讓電腦解請按2，結束遊戲請按0:" << endl;
cin >> chkII;
if (chkII == 0) break;
if (chkII == 2)
{
cout << endl;
cout << "電腦計算中，可能需要一點時間，請稍候......" << endl;
determine(block);
result(block);
}
if (chkII == 1)
if (typein(turnII))
cout << "恭喜你解玩了這一題!!:" << endl;
cout << endl;
cout << "想要再玩一次請按1，結束遊戲請按0:" << endl;
cin >> ret;
cout << endl;
}
return 0;
}
//======================================
void _ClearBoard()
{
for (int i=0;i<9;i++)
for (int j=0;j<9;j++)
block[i][j]=0;
}
//--------------------------
void _DefaultBoard()
{
_ClearBoard();
block[0][0]=2;block[0][1]=1;block[0][5]=6;block[0][8]=5;
block[1][5]=7;block[1][6]=1;block[1][8]=6;
block[2][1]=6;block[2][4]=8;
block[3][0]=7;block[3][1]=2;block[3][4]=5;
block[4][2]=9;block[4][3]=2;block[4][5]=3;block[4][6]=5;
block[5][4]=6;block[5][7]=8;block[5][8]=4;
block[6][4]=2;block[6][7]=5;
block[7][0]=4;block[7][2]=6;block[7][3]=9;
block[8][0]=3;block[8][3]=6;block[8][7]=1;block[8][8]=8;
}

//--------------------------
void _ShowRule()
{
cout << "** 數獨遊戲在9x9的方格內進行，分為9個3x3的小方格，這些方格被稱為區。 **" << endl;
cout << "** 遊戲首先從已經填入數字的格子開始判斷， **" << endl;
cout << "** 用1至9之間的數字填滿空格，一個格子只能填入一個數字， **" << endl;
cout << "** 數字1到9在每一直行只能出現一次； **" << endl;
cout << "** 數字1到9在每一橫列只能出現一次； **" << endl;
cout << "** 數字1到9在每一區只能出現一次。 **" << endl;
cout << "** 總結這些規則，即每個數字在每一行、每一列和每一區都只能出現一次。**" << endl;
cout << endl;
cout << "=================================================================" << endl;
cout << endl;
}
//--------------------------
void _ShowBoard(int b[][9])
{
cout << endl;
cout << " 1 2 3 4 5 6 7 8 9 " << endl;
cout << " ---------------------------" << endl;
for (int i=0;i<9;i++)
{
cout << i+1 << " ";
for (int j=0; j<9; j++)
cout << b[i][j] << " ";
cout << endl;
cout << " ---------------------------" << endl;
}
return;
}
//--------------------------

int typein(int inNum)
{
int X, Y, num;
int count=inNum;
while (count>0)
{
_ShowBoard(block);

cout << "還要輸入 " << count << " 個數字" << endl;
cout << "請輸入欲填入的數字(1-9)(0-放棄):";
cin >> num;
if (num==0) return 0;
if (num>=1 && num<=9)
{
cout << "請輸入 X 座標(1~9):";
cin >> Y;
cout << "請輸入 Y 座標(1~9):";
cin >> X;
X--;
Y--;
if (X<0 || X>9 || Y<0 || Y>9 || block[X][Y]!=0)
cout << "座標不對喔，你要放到哪去？" << endl;
else if (check(X, Y, num))
{
block[X][Y]=num;
count--;
}
}
else cout << "輸入的數字並非1到9，請重新輸入" << endl;
}
cout << endl;
_ShowBoard(block);
return 1;
}

//-------------------------------
int check(int X, int Y, int num)
{
cout << endl;
for(int n=0; n<9; n++)
{
if (block[X][n]==num)
cout << "輸入的這個數字會和橫列的數字衝突喔：）" << endl;
else if (block[n][Y]==num)
cout << "輸入的這個數字會和直行的數字衝突喔：）" << endl;
else if (block[X/3*3+n%3][Y/3*3+n/3]==num)
cout << "輸入的這個數字會和區的數字衝突喔：）" << endl;
else continue;
return 0;
}
return 1;
}
//-------------------------------
int lookup(int b[][9], int x, int y)
{
int xx, yy;
for(int n=0; n<9; n++)
{
xx = x/3*3+n%3;
yy = y/3*3+n/3;
if ((n!=y && b[x][n]==b[x][y]) || (n!=x && b[n][y]==b[x][y])
|| (x!=xx && y!=yy && b[xx][yy]==b[x][y]))
return 0;
}
return 1;
}
//-------------------------------
int fillin(int b[][9])
{
int u, v;
for (u=0;u<=8;u++)
for (v=0;v<=8;v++)
if (b[u][v]==0)
return 0;
return 1;
}
//-------------------------------
int paste(int a[][9], int b[][9])
{
int m,n;
for (m=0;m<=8;m++)
for (n=0;n<=8;n++)
a[m][n] = b[m][n];
return 1;
}
//-------------------------------
int result(int b[][9])
{
if (!fillin(b))
{
cout << "此數獨題目為無解喔！" << endl;
cout << endl;
cout << endl;
return 0;
}
_ShowBoard(b);
return 1;
}
//-------------------------------
int determine(int yen[][9])
{
if (fillin(yen))
return paste(block, yen);
int pro[9][9];
paste(pro, yen);

for (int x=0;x<9;x++)
for (int y=0;y<9;y++)
if (pro[x][y]==0)
{
for (int n=1;n<=9;n++)
{
pro[x][y]=n;
if (lookup(pro, x, y)==1)
if (determine(pro))
return 1;
}
return 0;
}
return 0;
}
//=====================================