Backtracking - Sudoku

제일 일상에서 써먹기 좋은(?) 알고리즘이다.

예전에 학교에서 시험끝나고 수학선생님이 스도쿠 문제를 나눠주고 빨리 푸는 사람한테 먹을것을 나눠주는 이벤트를 많이 했는데

그 때 이 알고리즘만 알았으면 내가 싹 쓸어먹지 않았을까 ㅋ.ㅋ

심지어 그 때 시험 끝나고 딱 1달 즈음 뒤에 이 문제를 풀어서 더 아쉬웠다.

 

#include <stdio.h>

#include <stdlib.h>

#define n 9  // 스도쿠판은 9 x 9

int arr[10][10];

int zero[100][2];

int cnt = 0;

int garo[100][100];

int sero[100][100];

int box[5][5][10];

void r(int x)

{

int i, j;

if(x == cnt) { //만약 모든 빈칸을 채웠다면 출력하고 프로그램을 종료한다.

printf("\n\n\n\n");

for(i=1;i<=n;i++) {

for(j=1;j<=n;j++) {

printf("%d ", arr[i][j]);

}

printf("\n");

}

exit(1);

}

for(i=1;i<=9;i++) { //그게 아니라면 현재 가지고있는 빈킨에다가 1부터 9까지의 숫자를 하나씩 재워넣으면서 

if(garo[zero[x][0]][i] == 0 && sero[i][zero[x][1]] == 0 && box[(zero[x][0]-1)/3+1][(zero[x][1]-1)/3+1][i] == 0) { //맞으면 다음 빈칸으로

garo[zero[x][0]][i] = 1;

sero[i][zero[x][1]] = 1;

box[(zero[x][0]-1)/3+1][(zero[x][1]-1)/3+1][i] = 1;

arr[zero[x][0]][zero[x][1]] = i;

r(x+1); //재귀호출을 하고

arr[zero[x][0]][zero[x][1]] = 0; //이 아래부터는 호출을 했는데 틀려서 다시 돌아온 경우이다.

garo[zero[x][0]][i] = 0;

sero[i][zero[x][1]] = 0;

box[(zero[x][0]-1)/3+1][(zero[x][1]-1)/3+1][i] = 0; // 틀리면 그냥 다시 빈칸으로 초기화하고 다른 숫자를 집어넣는다.

}

}

}

int main()

{

int i, j;

for(i=1;i<=n;i++) {

for(j=1;j<=n;j++) {

scanf("%d", &arr[i][j]);            //빈칸은 0으로 입력받음

if(arr[i][j] == 0) {                    //빈칸을 입력받으면  

zero[cnt][0] = i;            

zero[cnt][1] = j;            //0의 위치를 저장하고

cnt++;                    //갯수를 센다.

}

else {

garo[i][arr[i][j]] = 1; //빈칸이 아니라면 테이블을 만들어서 어떤 행에 어떤 숫자가 채워져 있는지

sero[arr[i][j]][j] = 1; // 행과 열에 대한 정보를 채워넣는다.

box[(i-1)/3+1][(j-1)/3+1][arr[i][j]] = 1; // 3 x 3 박스도 마찬가지로 정보를 채워준다.

}

}

}

r(0); //가장 첫번째 0부터 시작해서 백트래킹을 시작한다.

printf("Not Possible\n");

return 0;

}

자료구조가 살짝 헷갈릴 수도 있으니 그림으로 설명하겠다.

이런식으로 하나의 행 또는 열을 기준으로 잡고 해당 행이나 열에 숫자가 있는지 없는지 여부를 배열의 값(0 혹은 1)로 표시하는 것이다.

예를 들어 가로 1행에 8이 있으면 garo[1][8] = 1; 로 표시하는 식이다.

열은 같은 방식이고

빡스는 기준으로 잡는 범위가 1x9에서 3x3으로 바뀌었을 뿐이다.