這道題很顯然要用DFS（深度優先搜索）
注：有其它方法也可以，不過我這里用的是DFS，
題目描述
數獨是根據 9×9 盤面上的已知數字，推理出所有剩余空格的數字，并滿足每一行、每一列、每一個粗線宮內的數字均含 1?9 ，不重復，每一道合格的數獨謎題都有且僅有唯一答案，推理方法也以此為基礎，任何無解或多解的題目都是不合格的，
芬蘭一位數學家號稱設計出全球最難的“數獨游戲”，并刊登在報紙上，讓大家去挑戰，
這位數學家說，他相信只有“智慧最頂尖”的人才有可能破解這個“數獨之謎”，
據介紹，目前數獨游戲的難度的等級有一到五級，一是入門等級，五則比較難，不過這位數學家說，他所設計的數獨游戲難度等級是十一，可以說是所以數獨游戲中，難度最高的等級，他還表示，他目前還沒遇到解不出來的數獨游戲，因此他認為“最具挑戰性”的數獨游戲并沒有出現，
輸入格式
一個未填的數獨，
輸出格式
填好的數獨，
如果不知道數獨的規則請先看下面這段話 知道直接略過
數獨由9×9的格子組成，
規則是：每行、列、宮各自都要填上1-9的數字，要做到每行、列、宮里的數字都不重復，
宮是由3×3的小格子組成的
這道題時間限制是1s，記憶體限制125M，用DFS問題不大，
直接上代碼
#include<bits/stdc++.h>
using namespace std;
int a[15][15],b[15][15],c[15][15],g[15][15],flag=0;
/*開四個陣列，a陣列用來保存數獨，b陣列用來記錄當前行是否出現過該數字，
c陣列用來記錄當前列是否出現過該數字，g陣列用來記錄當前宮格是否出現過該數字*/
void dfs(int x,int y)
{
if(x>9)//當x大于9時說明矩陣已經被填滿，已經找到數獨的解，于是結束呼叫
{
flag=1;
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
cout<<a[i][j]<<' ';
cout<<endl;
}
return;
}
if(a[x][y]==0)//如果當前位置未被占用，則進行填數，否則直接進入下一個位置
for(int i=1;i<=9;i++)
{
if(flag)
return;
if(a[x][y]==0&&b[x][i]==0&&c[i][y]==0&&g[(x-1)/3*3+(y-1)/3+1][i]==0)
a[x][y]=i,b[x][i]=1,c[i][y]=1,g[(x-1)/3*3+(y-1)/3+1][i]=1;//保存現場
else continue;//(x-1)/3*3+(y-1)/3+1表示當前所在的宮格數，這里不做具體的數學證明
if(y<9)
dfs(x,y+1);
else
dfs(x+1,1);
a[x][y]=0,b[x][i]=0,c[i][y]=0,g[(x-1)/3*3+(y-1)/3+1][i]=0;//恢復現場
}
else{
if(y<9)
dfs(x,y+1);
else
dfs(x+1,1);
}
}
int main (void)
{
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
{
scanf("%d",&a[i][j]);
if(a[i][j])
b[i][a[i][j]]=1,c[a[i][j]][j]=1,g[(i-1)/3*3+(j-1)/3+1][a[i][j]]=1;
}
dfs(1,1);
}
以下為測驗結果
這是我在洛谷中的測評記錄，這道題用DFS最快能跑3ms，最慢也只用了6ms，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/253005.html
標籤：其他
上一篇：51單片機藍牙遙控麥輪小車
下一篇：賽后題解——真偽亞瑟王