BOJ 2580 스도쿠

개요

BOJ 2580 스도쿠

• 백준 온라인 저지 2580번 문제
• BOJ 22단계

C++

#include <bits/stdc++.h>
using namespace std;

int arr[9][9];
vector<pair<int, int>> blanks;

bool check(pair<int, int> p) {
    for(int i=0; i<9; i++) {
        if(arr[p.first][i]==arr[p.first][p.second] && i!=p.second) {
            return false;
        }
        if(arr[i][p.second]==arr[p.first][p.second] && i!=p.first) {
            return false;
        }
    }
    int x = p.first/3;
    int y = p.second/3;
    for(int i=3*x; i<3*x+3; i++) {
        for(int j=3*y; j<3*y+3; j++) {
            if(arr[i][j]==arr[p.first][p.second] && i!=p.first && j!=p.second) {
                return false;
            }
        }
    }
    return true;
}

bool solve(int n) {
    if(n == blanks.size()) {
        for(int i=0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                cout << arr[i][j] << ' ';
            }
            cout << '\n';
        }
        return true;
    }
    for(int i=1; i<=9; i++) {
        arr[blanks[n].first][blanks[n].second] = i;
        if(!check(blanks[n])) continue;
        if(solve(n+1)) return true;
    }
    arr[blanks[n].first][blanks[n].second] = 0;
    return false;
}

int main() {
    pair<int, int> p;
    for(int i=0; i<9; i++) {
        for(int j=0; j<9; j++) {
            cin >> arr[i][j];
            if(arr[i][j] == 0) {
                p.first = i;
                p.second = j;
                blanks.push_back(p);
            }
        }
    }
    solve(0);
}