[TIOJ] 1025. 數獨問題

題目連結:http://tioj.infor.org/problems/1025

---

又是一題數獨，同樣的按照對的順序dfs，則你輸出答案的順序也會是好的，所以就爆搜吧XD

#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;

void solve(int);
inline bool isOK();

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;
}

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;
	}
}

inline bool isOK(){
	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;
		}
	}
	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;
		}
	}
	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;
}