스도쿠

백준 2580번: 스도쿠

아이디어

숫자를 입력받으면서 스도쿠 판에 기록하고 각 행, 열, 3*3 정사각형에 해당 숫자가 포함되는지 확인하는 배열에도 기록한다. 0을 입력받으면 그 좌표에는 숫자를 채워줘야 하니 따로 기록해둔다.
기록해둔 좌표에 숫자 1부터 9까지 하나하나 조건에 맞나 검사하면서 숫자를 채워넣는다. 숫자를 더이상 채워넣을 수 없는 경우 되돌아가면서 아까 채웠던 숫자를 없애준다. 물론 숫자가 포함되는지 확인하는 배열도 원래대로 돌려놔야 한다.
또 주의할 점은 스도쿠 판을 한 번만 출력해야 한다는 것이다.

코드

#include <bits/stdc++.h>

using namespace std;

int arr[9][9];
bool r_check[9][10];
bool c_check[9][10];
bool s_check[3][3][10];
bool SW = false;
vector<pair<int, int>> v;

void solve(vector<pair<int, int>>::iterator iter) {
    if (SW) return;
    if (iter == v.end()) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                cout << arr[i][j] << ' ';
            }
            cout << '\n';
        }
        SW = true;
        return;
    }
    
    int y = (*iter).first;
    int x = (*iter).second;
    
    for (int i = 0; i < 9; i++) {
        if (r_check[y][i+1]) continue;
        if (c_check[x][i+1]) continue;
        if (s_check[y/3][x/3][i+1]) continue;
        
        arr[y][x] = i+1;
        r_check[y][i+1] = true;
        c_check[x][i+1] = true;
        s_check[y/3][x/3][i+1] = true;
        
        solve(iter+1);
        
        arr[y][x] = 0;
        r_check[y][i+1] = false;
        c_check[x][i+1] = false;
        s_check[y/3][x/3][i+1] = false;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int x;
    for(int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> x;
            if (x == 0) {
                v.push_back({i, j});
            }
            else {
                arr[i][j] = x;
                r_check[i][x] = true;
                c_check[j][x] = true;
                s_check[i/3][j/3][x] = true;
            }
        }
    }
    vector<pair<int, int>>::iterator iter = v.begin();
    solve(iter);
    return 0;
}

여담

훈련소 격리때 너무 심심해서 이런거 그려서 풀었는데 ㅋㅋ;