大概是把網(wǎng)上找到的代碼稍微改了一下，記不清了= =
代碼
#include <iostream>
using namespace std;
/* 構(gòu)造完成標志 */
bool sign = false;
/* 創(chuàng)建數(shù)獨矩陣 */
int num[9][9];
void Input();
void Output();
bool Check(int n, int key);
int DFS(int n);
int main()
{
cout << "請輸入一個9*9的數(shù)獨矩陣耻讽，數(shù)字用空格隔開棕叫，空位以0表示:" << endl;
Input();
DFS(0);
Output();
}
/* 讀入數(shù)獨矩陣 */
void Input()
{
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
cin >> num[i][j];
}
/* 輸出數(shù)獨矩陣 */
void Output()
{
cout << endl;
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
cout << num[i][j] << " ";
if (j % 3 == 2)
cout << " ";
}
cout << endl;
if (i % 3 == 2)
cout << endl;
}
}
/* 判斷key填入n時是否滿足條件 */
bool Check(int n, int key)
{
/* 判斷n所在橫列是否合法 */
for (int i = 0; i < 9; i++)
{
/* j為n豎坐標 */
int j = n / 9;
if (num[j][i] == key) return false;
}
/* 判斷n所在豎列是否合法 */
for (int i = 0; i < 9; i++)
{
/* j為n橫坐標 */
int j = n % 9;
if (num[i][j] == key) return false;
}
/* x為n所在的小九宮格左頂點豎坐標 */
int x = n / 9 / 3 * 3;
/* y為n所在的小九宮格左頂點橫坐標 */
int y = n % 9 / 3 * 3;
/* 判斷n所在的小九宮格是否合法 */
for (int i = x; i < x + 3; i++)
for (int j = y; j < y + 3; j++)
if (num[i][j] == key) return false;
/* 全部合法昭抒，返回正確 */
return true;
}
/* 深搜構(gòu)造數(shù)獨 */
int DFS(int n)
{
/* 所有的都符合执泰，退出遞歸 */
if (n > 80)
{
sign = true;
return 0;
}
/* 當前位不為空時跳過 */
if (num[n/9][n%9] != 0)
DFS(n+1);
else
/* 否則對當前位進行枚舉測試 */
for (int i = 1; i <= 9; i++)
/* 滿足條件時填入數(shù)字 */
if (Check(n, i) == true)
{
num[n/9][n%9] = i;
/* 繼續(xù)搜索 */
DFS(n+1);
/* 返回時如果構(gòu)造成功龙屉，則直接退出 */
if (sign == true) return 0;
}
}
測試用例
1 0 3 0 0 0 5 0 9
0 0 2 1 0 9 4 0 0
0 0 0 7 0 4 0 0 0
3 0 0 5 0 2 0 0 6
0 6 0 0 0 0 0 5 0
7 0 0 8 0 3 0 0 4
0 0 0 4 0 1 0 0 0
0 0 9 2 0 5 8 0 0
8 0 4 0 0 0 1 0 7
