#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <map>
#include <cmath>
#include <numeric>
using namespace std;
int board[10][10];
vector<pair<int,int>> v;
void func(int depth)
{
if(depth == v.size()){
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
cout << board[i][j]<< ' ';
cout << '\n';
}
exit(0);
}else{
for(int i=depth;i<v.size();i++)
{
auto cur = v[i];
bool vis[10];
fill(vis, vis+10, true);
for(int a=0;a<9;a++)
{
vis[board[a][cur.second]] = false;
vis[board[cur.first][a]] = false;
}
int ny = (cur.first/3)*3;
int nx = (cur.second/3)*3;
for(int a=ny;a<ny+3;a++)
for(int b=nx;b<nx+3;b++)
vis[board[a][b]] = false;
for(int j=1;j<=9;j++)
{
if(!vis[j]) continue;
board[cur.first][cur.second] = j;
func(i+1);
board[cur.first][cur.second] = 0;
}
return;
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
{
cin >> board[i][j];
if(board[i][j] == 0)
v.push_back({i,j});
}
cout << '\n';
func(0);
return 0;
}
- key point
해당 좌표
에서 가능한 숫자
가 없으면 바로 return;
으로 종료
시켜줘야함
(그렇지 않으면 그대로 0
인 값을 가지고 다음 depth
를 실행
하기 때문;)