d263 - 00989 - Su Doku
題目描述
題目要求解一個 n x n 的數獨。給定一個部分填寫的數獨盤面，其中一些格子已經填有數字，其餘格子為空白（用 0 表示）。目標是填寫空白格子，使得每一行、每一列以及每一個 n x n 的子方陣都包含 1 到 n 的所有數字，且每個數字只出現一次。如果存在解，輸出解；否則，輸出 "NO SOLUTION"。
解題思路
本題採用 backtracking (回溯) 演算法來解決。核心思想是遞迴地嘗試在每個空白格中填入 1 到 n 的數字。在填入數字之前，需要檢查該數字是否符合數獨的規則，即是否與同一行、同一列以及同一子方陣中的其他數字重複。如果填入的數字不符合規則，則回溯到上一步，嘗試其他數字。
程式碼中 cwa 函數用於檢查填入數字是否符合規則，check 函數是 cwa 的簡化版本，用於在遞迴過程中快速驗證。dfs 函數實現了回溯演算法，它遞迴地遍歷數獨盤面，找到下一個空白格，並嘗試填入合法的數字。如果找到一個解，則輸出解並結束遞迴。如果所有可能的數字都嘗試過，但仍然無法找到解，則回溯到上一步。
複雜度分析
- 時間複雜度: O(n^n)，其中 n 是數獨盤面的大小。在最壞的情況下，需要嘗試所有可能的數字組合。
- 空間複雜度: O(n^2)，主要用於儲存數獨盤面和遞迴調用堆疊。
程式碼
#include <iostream>
using namespace std;
int n,a[10][10],b[10][10],ans,sn,s,wa;
bool cwa(int x,int y,int v){
for(int i=0;i<n;++i)
if((a[x][i]==v&&i!=y)||(a[i][y]==v&&i!=x))
return 0;
int bx=(x/sn)*sn,by=(y/sn)*sn;
for(int i=0;i<sn;++i)
for(int j=0;j<sn;++j)
if(a[bx+i][by+j]==v&&(bx+i!=x||by+j!=y))
return 0;
return 1;
}
bool check(int x,int y,int v){
for(int i=0;i<n;++i)
if(a[x][i]==v||a[i][y]==v)
return 0;
int bx=(x/sn)*sn,by=(y/sn)*sn;
for(int i=0;i<sn;++i)
for(int j=0;j<sn;++j)
if(a[bx+i][by+j]==v)
return 0;
return 1;
}
void dfs(int x,int y){
if(ans)return;
if(x==n&&y==n-1){
ans=1;
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
cout << a[i][j];
if(j!=n-1)cout << " ";
}
cout << "\n";
}
return;
}
if(b[x][y]){
for(int i=1;i<=n;++i)
if(check(x,y,i)){
a[x][y]=i;
dfs(x+(y+1)/n,(y+1)%n);
a[x][y]=0;
}
}
else
dfs(x+(y+1)/n,(y+1)%n);
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> n){
if(s==1)
cout << "\n";
s=1;
for(int i=0;i<10;++i)
for(int j=0;j<10;++j){
a[i][j]=0;
b[i][j]=0;
}
wa=0;ans=0;sn=n;n*=n;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j){
cin >> a[i][j];
b[i][j]=!a[i][j];
}
for(int i=0;i<n&&wa==0;++i)
for(int j=0;j<n&&wa==0;++j)
if(a[i][j]!=0)
if(cwa(i,j,a[i][j])==0)
wa=1;
if(wa==0)dfs(0,0);
if(ans==0)
cout << "NO SOLUTION\n";
}
}