[Jungol] 정올 1824 스도쿠

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1097&sca=3030

 Input 

0 3 5 4 6 9 2 7 8

7 8 2 1 0 5 6 0 9

0 6 0 2 7 8 1 3 5

3 2 1 0 4 6 8 9 7

8 0 4 9 1 3 5 0 6

5 9 6 8 2 0 4 1 3

9 1 7 6 5 2 0 8 0

6 0 3 7 0 1 9 5 2

2 5 8 3 9 4 7 6 0

 

 Output 

1 3 5 4 6 9 2 7 8

7 8 2 1 3 5 6 4 9

4 6 9 2 7 8 1 3 5

3 2 1 5 4 6 8 9 7

8 7 4 9 1 3 5 2 6

5 9 6 8 2 7 4 1 3

9 1 7 6 5 2 3 8 4

6 4 3 7 8 1 9 5 2

2 5 8 3 9 4 7 6 1

비어있는 칸에 1~9까지를 모두 넣어서 스도쿠를 완성할 때는 TLE 발생 (최대 981)

따라서 비어있는 칸에 1~9까지 가능한 후보를 백트래킹 과정으로 살펴본다.

▶ 빈 칸인 경우 가로, 세로 영역(3 × 3)을 체크하여 가능한 수를 넣고 다음 칸으로 진행

① row[i][k] = i 행에 『 k 』 라는 숫자가 사용되었는가?

② col[j][k] = j 열에 『 k 』 라는 숫자가 사용되었는가?

③ loc[n][k] = n이라는 영역에 『 k 』 라는 숫자가 사용되었는가?

    영역 = ( i / 3 * 3) + (j / 3)

    ex) (4, 4)가 속한 영역은? (4 / 3 * 3) + (4 / 3) = 3 + 1 = 4

    ex) (6, 6)이 속한 영역은? (6 / 3 * 3) + (6 / 3) = 6 + 2 = 8

 

---

#include <stdio.h>
 
const int LM = 10;
int N, B[LM][LM];
int row[LM][LM], col[LM][LM], loc[LM][LM];
 
void input(){
    int i, j, k;
    for(i=0; i<9; ++i){
        for(j=0; j<9; ++j){
            scanf("%d", &k);
            if(!k) continue;
            B[i][j] = k;
            row[i][k] = col[j][k] = loc[i/3 * 3 + j/3][k] = 1;
        }
    }
}
 
int sudoku(int i, int j){
    if(j > 8) i++, j=0;
    if(i > 8) return 1;
    if(B[i][j]) return sudoku(i, j+1);
    for(int k=1; k<10; ++k){
        if(row[i][k] + col[j][k] + loc[i/3 * 3 + j/3][k] == 0){
            row[i][k] = col[j][k] = loc[i/3 * 3 + j/3][k] = 1;
            B[i][j] = k;
            if(sudoku(i, j + 1)) return 1;
            B[i][j] = 0;
            row[i][k] = col[j][k] = loc[i/3 * 3 + j/3][k] = 0;
        }
    }
    return 0;
}
 
void output(){
    for(int i=0; i<9; ++i){
        for(int j=0; j<9; ++j){
            printf("%d ", B[i][j]);
        }
        puts("");
    }
}
 
int main(){
    input();
    sudoku(0, 0);
    output();
}