題目連結: https://tioj.ck.tp.edu.tw/problems/1025
# 內容
所謂的數獨就是在一個九乘九的宮格（9 個三乘三宮格）裡，填入 1 到 9 等 9 個數字，讓每個數字在每一行、列及所在的三乘三宮格裡都只出現一次。謎題中會預先填入若干數字，其他宮格位則留白讓玩家自行填入，通常數獨題目都會設計成唯一解。但本題之測試輸入可能會有多解，請你通通將其輸出。
你可以假設題目所給的數獨都是合法的，也就是不會有本身已經填好的數字不合規則的情形存在。題目的解數不會超過 50 組。
# 思路
按照題意 DFS 窮舉就有答案囉～～
# 程式碼
#include <bits/stdc++.h> | |
using namespace std; | |
struct pos{ | |
int x,y; | |
pos(int a,int b){x=a;y=b;} | |
}; | |
vector<pos> need; | |
int sudoku[9][9]; | |
int sum=0; | |
inline bool isOK(){ | |
//column | |
for(int i=0;i<9;i++){ | |
int sm[10]={0}; | |
for(int j=0;j<9;j++){ | |
if(sudoku[i][j]==0)continue; | |
if(sm[sudoku[i][j]]==0)sm[sudoku[i][j]]=1; | |
else return 0; | |
} | |
} | |
//row | |
for(int i=0;i<9;i++){ | |
int sm[10]={0}; | |
for(int j=0;j<9;j++){ | |
if(sudoku[j][i]==0)continue; | |
if(sm[sudoku[j][i]]==0)sm[sudoku[j][i]]=1; | |
else return 0; | |
} | |
} | |
//cell | |
for(int i=0;i<3;i++){ | |
for(int j=0;j<3;j++){ | |
int sm[10]={0}; | |
for(int k=0;k<3;k++){ | |
for(int l=0;l<3;l++){ | |
if(sudoku[i*3+k][j*3+l]==0)continue; | |
if(sm[sudoku[i*3+k][j*3+l]]==0)sm[sudoku[i*3+k][j*3+l]]=1; | |
else return 0; | |
} | |
} | |
} | |
} | |
return 1; | |
} | |
void solve(int w){ | |
if(w==need.size()){ | |
for(int i=0;i<9;i++){ | |
for(int j=0;j<9;j++)cout<<sudoku[i][j]<<' '; | |
cout<<'\n'; | |
} | |
cout<<'\n'; | |
sum++; | |
}else{ | |
auto cur = need[w]; | |
for(int i=1;i<=9;i++){ | |
sudoku[cur.x][cur.y] = i; | |
if(isOK()) solve(w+1); | |
} | |
sudoku[cur.x][cur.y]=0; | |
} | |
} | |
int main(){ | |
ios_base::sync_with_stdio(0);cin.tie(0); | |
for(int i=0;i<9;i++){ | |
for(int j=0;j<9;j++){ | |
cin>>sudoku[i][j]; | |
if(sudoku[i][j]==0) need.push_back(pos(i,j)); | |
} | |
} | |
solve(0); | |
cout<<"there are a total of "<<sum<<" solution(s)."; | |
return 0; | |
} |
