[백준 2239] 스도쿠 [C]

백준 - 2239

---

풀이

스도쿠를 완성시키고, 81자리의 수가 제일 작은 경우를 출력하면 되는 문제이다.

Backtracking방식으로 스도쿠에 넣어줄 수 있는 작은 수 부터 탐색하면서, 만약 81번째 자리에 도달했다면 가장 작은 81자리의 수를 완성시킨 것이기 때문에 출력을 해주고 중단을 해줘야한다.

---

소스코드

#include <stdio.h>
int arr[9][9], print = 1;
int check(int x, int y, int val){
    for (int i = 0; i < 9; i++)
        if (arr[x][i] == val || arr[i][y] == val)
            return 0;
		
    x = (x/3)*3;
    y = (y/3)*3;
    for (int i = x; i < x+3; i++)
        for (int j = y; j < y+3; j++)
            if (arr[i][j] == val)
                return 0;
    return val;	
}

void BT(int n){
    if (!print) return;
    if (n == 81){
        for (int i = 0; i < 9; i++){
            for (int j = 0; j < 9; j++)
                printf("%d", arr[i][j]);
            putchar(10);
        }
        print = 0;
        return;
    }
	
    int x = n/9, y = n%9;
    if (!arr[x][y]){
        for (int val = 1; val <= 9; val++)
            if (check(x, y, val)){
                arr[x][y] = val;
                BT(n + 1);
                arr[x][y] = 0;	
            }
    }else BT(n + 1);
}

int main(){
    for (int i = 0; i < 81; i++)
        scanf("%1d", &arr[i/9][i%9]);
    BT(0);
}

---

출처

2239번: 스도쿠