백준 소스코드 [C++] 4056 스-스-스도쿠

www.acmicpc.net/problem/4056

4056번: 스-스-스도쿠

백준 소스코드 [C++] 4056 스-스-스도쿠

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <deque>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string.h>
#include <set>
#include <map>
#include <unordered_map>
#include <sstream>
#include <cstdlib>
#include <cassert>
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define pli pair<ll, int>
#define make_unique(v) sort(all(v)), v.erase(unique(all(v)), v.end())
typedef long long ll;
using namespace std;

int arr[9][9];
bool flag = false;
struct Dot {
    int y, x;
};
vector<Dot> dots;

bool chk(Dot D, int num) {
    int Y = D.y / 3;
    int X = D.x / 3;

    for (int i = 0;i < 9;i++) if (D.y!=i && arr[i][D.x] == num) return false;
    for (int j = 0;j < 9;j++) if (D.x!=j && arr[D.y][j] == num) return false;

    for (int i = 3 * Y;i < 3 * Y + 3;i++)
        for (int j = 3 * X;j < 3 * X + 3;j++)
            if (!(D.y==i && D.x==j) && arr[i][j] == num) return false;
    return true;
}

void search(int k) {
    if (k == dots.size()) {
        bool finalCheck = true;
        for (int Y = 0; Y <3 ;Y++)
        for (int X = 0; X <3 ;X++){
            bool valid[10];
            memset(valid,false,sizeof(valid));
            for (int i = 3 * Y;i < 3 * Y + 3;i++)
                for (int j = 3 * X;j < 3 * X + 3;j++) {
                    if (!valid[arr[i][j]]) valid[arr[i][j]] = true;
                    else finalCheck = false;
                }
        }
        
        if (!finalCheck) {
            flag = false;
            return;
        } 
        for (int i = 0;i < 9;i++) {
            for (int j = 0;j < 9;j++) cout << arr[i][j];
            cout << '\n';
        }
        flag = true;
        return;
    }

    Dot dot = dots[k];
    for (int a = 1;a <= 9;a++) {
        arr[dot.y][dot.x] = a;
        if (chk(dot, a) == true) search(k + 1);
        if (flag == true) return;
        arr[dot.y][dot.x] = 0;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    int t; cin >> t;
    while (t--) {
        flag = false;
        for (int i = 0;i < 9;i++) {
            cin >> s;
            for (int j = 0;j < 9;j++) {
                arr[i][j] = s[j] - '0';
                if (arr[i][j] == 0) {
                    Dot dot;
                    dot.y = i;
                    dot.x = j;
                    dots.push_back(dot);
                }
            }
        }
        search(0);
        if (flag == false) cout << "Could not complete this grid."<<'\n';
        cout << '\n';
    }
    return 0;
}