[백준/C언어] 2580번 - 스도쿠

백준 웹사이트 "2580번 - 스도쿠" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

2580번: 스도쿠

---

소스 코드

#include <stdio.h>
#include <stdlib.h>

void solve(int (*sudoku)[9], int count);

int main(void){
    int sudoku[9][9];
    for(int i=0; i<9; i++){
        for(int j=0; j<9; j++){
            scanf("%d", &sudoku[i][j]);
        }
    }

    solve(sudoku, 0);
}

void solve(int (*sudoku)[9], int count){
    if(count == 81){
        //print sudoku
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                printf("%d ", sudoku[i][j]);
            }
            printf("\n");
        }
        exit(0);    //"스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력"
    }
    else{
        int index1 = count/9;
        int index2 = count%9;

        if(sudoku[index1][index2] != 0){    //해당 숫자가 0이 아니면 재귀
            solve(sudoku, count+1);
        }
        else{                               //해당 숫자가 0이면 숫자 가정
            for(int i=1; i<=9; i++){
                sudoku[index1][index2] = i;
                int failure = 0;
                //가로줄, 세로줄
                for(int j=0; j<9; j++){
                    if(j!=index2 && sudoku[index1][j] == i)
                        failure = 1;
                    if(j!=index1 && sudoku[j][index2] == i)
                        failure = 1;
                }
                //3x3 정사각형
                int center1=0;  //속해있는 정사각형의 인덱스
                int center2=0;  //속해있는 정사각형의 인덱스
                for(int k1=1; k1<=7; k1+=3){
                    for(int k2=1; k2<=7; k2+=3){
                        if(abs(k1 - index1)<=1 && abs(k2 - index2)<=1){
                            center1 = k1;
                            center2 = k2;
                        }
                    }
                }
                //sudoku[center1][center2]가 속한 정사각형의 인덱스
                for(int num1=center1-1; num1<=center1+1; num1++){
                    for(int num2=center2-1; num2<=center2+1; num2++){
                        if(num1==index1 && num2==index2)
                            continue;
                        else{
                            if(sudoku[num1][num2] == i)
                                failure = 1;
                        }
                    }
                }
            
                //이때, failure==0이면 재귀, failure==1이면 재귀x
                if(!failure){
                    solve(sudoku, count+1);
                }
                sudoku[index1][index2] = 0; //시도 후, 0으로 되돌리기
            }
        }
    }
}

---

문제 풀이

  누구나 한 번쯤은 해봤을 스도쿠 퍼즐을 푸는 문제입니다. 어렸을 적 머리를 써가며 열심히 풀었을 스도쿠를 이제 1초만에 푸는 능력이 생기는 셈이죠.

  우선 스도쿠판 'sudoku'를 선언한 후, 빈 칸과 주어진 수들을 해당 9×9 이차원 배열에 저장합니다. 이렇게 초기화한 sudoku를 파라미터로 solve 재귀함수를 실행시켜 스도쿠를 해결합니다. 'solve' 재귀함수는 다음과 같이 정의합니다.

함수: solve(int (*sudoku)[9], int count)

파라미터
- sudoku : 9×9 스도쿠판 (이차원 배열)
- count : 재귀 반복 횟수 (최대는 9×9판의 칸 수 81)

Base Case (기본 케이스)
- 조건문: count == 81
- 실행문: 스도쿠판 출력. 이때 스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력해야 하므로, exit(0)을 통해 프로그램이 종료되도록 함

Recursive Case (재귀 케이스)
- 조건문: count != 81 (count가 81보다 작을 경우)
- 실행문: 해당 숫자가 0이면, 1 ~ 9의 숫자를 각각 넣어보고 가로줄/세로줄/정사각형 내에 겹치는 숫자가 있는지 확인. 겹치는 숫자가 없다면 재귀
- 재귀: solve(sudoku, count+1)

 

  solve 재귀함수의 재귀 케이스를 봅시다. 알고리즘은 간단하지만, 그 구현은 생각보다 까다롭습니다. 해당 칸이 0이라면, 빈 칸이므로 이를 채워줘야 합니다. 1부터 9까지의 수를 하나씩 대입해보고, 겹치는 숫자가 있는지 확인해봅니다. Line 40 ~ 45는 가로줄, 세로줄에 겹치는 숫자가 있는지 확인하는 과정이고, Line 47 ~ 67은 3×3 정사각형 내에 겹치는 숫자가 있는지 확인하는 과정입니다. 이때 겹치는 숫자가 있다면 failure에 1이 저장되어 Line 71의 재귀가 일어나지 않습니다.

  코드에서 가장 틀리기 쉬운 부분은 3×3 정사각형 내에 겹치는 숫자가 있는지 확인하는 과정입니다. 이 과정은 두 섹션으로 나뉘어 있는데, 첫 번째는 현재 칸이 어느 정사각형에 속하는지 확인하는 섹션 (Line 47 ~ 56)이고, 두 번째는 그 정사각형에 겹치는 숫자가 있는지 확인하는 섹션 (Line 58 ~ 67)입니다. 총 9개인 3×3 정사각형들의 중앙 칸은 인덱스가 '1, 4, 7'로 이루어져 있습니다. 즉, sudoku[1][1], sudoku[1][4], sudoku[1][7] ... sudoku[7][7]이 중앙 칸들입니다. 한 정사각형의 칸들은 인덱스가 중앙 칸의 인덱스와 절댓값 1 이하 차이가 나므로, 이 원리를 이용해 어느 정사각형에 속하는지 찾고 겹치는 숫자가 있는지 파악할 수 있습니다.