스도쿠

코드

#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);
            // 1. 가로 & 세로 검사
            for(int a=0;a<9;a++)
            {
                vis[board[a][cur.second]] = false;
                vis[board[cur.first][a]] = false;
            }
            // 2. 3X3 사각형 검사
            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를 실행하기 때문;)