2580번: 스도쿠

2580번: 스도쿠

사용 언어: C++

 

풀이

문제 요약

9×9 스도쿠 판에서, 일부 칸이 비어 있고(0으로 표시됨), 규칙에 맞게 모든 칸을 채워야 함.

• 각 행에 1~9가 한번씩
• 각 열에 1~9가 한번씩
• 각 3×3 구역에 1~9가 한번씩

---

풀이

백트래킹 기법을 이용하여 모든 빈 칸에 대해 가능한 수를 대입하고,
불가능한 경우 이전 상태로 돌아가서 다른 수를 시도.

핵심 아이디어

• 빈 칸을 순서대로 탐색하며 가능한 숫자를 시도
• 숫자를 채울 때마다, 행/열/구역 사용 여부를 표시
• 가능한 경우 다음 칸으로 재귀 호출
• 실패하면 상태를 되돌리고 다음 숫자 시도 (백트래킹)

구현 포인트

• 각 행/열/3×3 구역에 대해 숫자 사용 여부를 확인하기 위해
  bool row[9][10], col[9][10], square[9][10] 배열을 사용한다.
• (i / 3) * 3 + (j / 3)로 3×3 구역 번호 계산
• 0~80까지 순차적으로 인덱스화하여 빈 칸을 처리

#include <iostream>
using namespace std;

int board[9][9];
bool row[9][10];
bool col[9][10];
bool square[9][10];

int squareIndex(int i, int j) {
    return (i / 3) * 3 + (j / 3);
}

bool solve(int idx = 0) {
    if (idx == 81) return true;

    int i = idx / 9;
    int j = idx % 9;

    if (board[i][j] != 0) return solve(idx + 1);

    for (int num = 1; num <= 9; num++) {
        int sq = squareIndex(i, j);
        if (!row[i][num] && !col[j][num] && !square[sq][num]) {
            board[i][j] = num;
            row[i][num] = col[j][num] = square[sq][num] = true;

            if (solve(idx + 1)) return true;

            board[i][j] = 0;
            row[i][num] = col[j][num] = square[sq][num] = false;
        }
    }

    return false;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> board[i][j];
            int num = board[i][j];
            if (num != 0) {
                row[i][num] = true;
                col[j][num] = true;
                square[squareIndex(i, j)][num] = true;
            }
        }   
    }

    solve();

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++)
            cout << board[i][j] << ' ';
        cout << '\n';
    }

    return 0;
}