[백준 / BOJ] C++ 2580 스도쿠

백준  - 단계별로 풀어보기 [2580]

https://www.acmicpc.net/problem/2580

2580번: 스도쿠

풀이

가로, 세로 줄에는 1부터 9까지의 숫자가 한번씩만 나타나야합니다. 

3x3 정사각형 안에서도 1부터 9까지의 숫자가 한번만 나타나야한다. 

스도쿠 판의 좌표 (x,y) 에 넣는 숫자 num은 값의 존재유무판단을 우선적으로 한 이후, 위의 조건에 해당하지 않을 경우에만

값을 넣어주는 식으로 진행했습니다.

 

sudoku[9][9]의 끝 좌표까지 탐색한 경우 결과를 출력하고 종료합니다.

 

Code

#include <iostream>
using namespace std;

int sudoku[9][9];

bool check(int y, int x, int num) {
    for (int i = 0; i < 9; i++) {
        if (sudoku[y][i] == num) return false;
        if (sudoku[i][x] == num) return false;
    }

    for (int i = (y / 3) * 3; i < (y / 3) * 3 + 3; i++)
        for (int j = (x / 3) * 3; j < (x / 3) * 3 + 3; j++)
            if (sudoku[i][j] == num) return false;

    return true;
}

void func(int y, int x) {
    if (x == 9) { y++; x = 0; }

    if (y == 9) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++)
                cout << sudoku[i][j] << " ";
            cout << endl;
        }
        exit(0);
    }

    if (sudoku[y][x] != 0) {
        func(y, x + 1);
        return;
    }

    for (int i = 1; i <= 9; i++) {
        if (check(y, x, i)) {
            sudoku[y][x] = i;
            func(y, x + 1);
            sudoku[y][x] = 0;
        }
    }
}

int main() {
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)
            cin >> sudoku[i][j];

    func(0, 0);

    return 0;
}