2580 스도쿠

2580 스도쿠

백트래킹을 이용하여 완전탐색 하는 문제이다.

1. map입력 받을때 0값인 곳의 좌표를 vector에 푸쉬 한다.

2. 가로 세로 3x3칸에 대해 타당함을 확인하는 isPromising() 함수를 만든다.

3. 완전 탐색 한다.

#include <iostream>
#include <vector>
#define P pair<int,int>
using namespace std;
 
int map[9][9];
vector<P> v;
bool flag;
 
//타당성 여부 확인
bool isPromising(int x,int y) {
    int check = 0;
 
    for (int i = 0; i < 9; i++) {
        if (map[x][i] == 0) continue;
        if (check & (1 << map[x][i]))return false;
        check |= (1 << map[x][i]);
    }
 
    check = 0;
    for (int i = 0; i < 9; i++) {
        if (map[i][y] == 0) continue;
        if (check & (1 << map[i][y]))return false;
        check |= (1 << map[i][y]);
    }
    check = 0;
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if ((x / 3 == i / 3) && (y / 3 == j / 3)) {
                if (map[i][j] == 0) continue;
                if (check & (1 << map[i][j]))return false;
                check |= (1 << map[i][j]);
            }
        }
    }
    return true;
}
 
void printAll() {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cout << map[i][j] << " ";
        }
        cout << "\n";
    }
}
 
//백트래킹
void dfs(int idx) {
    if (flag) return;
 
    if (idx == v.size()) {
        printAll();
        flag = true;
    }
    else {
        int x = v[idx].first;
        int y = v[idx].second;
        for (int i = 1; i <= 9; i++) {
            map[x][y] = i;
            if (isPromising(x, y)) {
                dfs(idx + 1);
            }
            map[x][y] = 0;
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
 
    
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> map[i][j];
            if (map[i][j] == 0) v.push_back(P(i, j));
        }
    }
    
    flag = false;
    dfs(0);
}