[C/C++] 프로젝트 오일러 #96 Su Doku(백트래킹)

Project Euler의 96번 문제는 스도쿠 퍼즐을 해결하는 알고리즘 설계를 다루고 있습니다. 스도쿠는 9x9 격자로 이루어진 퍼즐 게임으로, 각 행, 열, 그리고 3x3의 작은 박스에 1부터 9까지의 숫자를 중복 없이 채워 넣는 것이 목표입니다. 이 문제는 단순히 하나의 스도쿠를 푸는 것이 아니라, 여러 개의 스도쿠 퍼즐을 입력받아 각각을 해결한 뒤, 각 퍼즐의 해답에서 첫 번째 세 숫자를 추출하여 합산하는 과제를 제시하고 있습니다.

프로그래머의 관점에서 이 문제를 접하면, 가장 먼저 고려해야 할 점은 스도쿠 퍼즐을 효율적으로 해결할 수 있는 알고리즘입니다. 일반적으로 사람이 스도쿠를 풀 때는 규칙을 기반으로 논리적 접근을 활용합니다. 특정 위치에 들어갈 수 있는 숫자의 후보를 좁혀가는 과정을 반복하게 됩니다. 이를 컴퓨터로 구현할 때는 보통 백트래킹(backtracking) 알고리즘이 효과적입니다. 백트래킹은 빈칸에 가능한 숫자를 하나씩 채워가며, 모순이 발생하면 이전 단계로 돌아가 다른 가능성을 탐색하는 방식입니다.

백트래킹은 구현이 비교적 간단하고 강력한 방법이지만, 효율성 문제를 고려하지 않으면 비효율적으로 작동할 수 있습니다. 특히 숫자를 채울 수 있는 후보가 많고 제약이 적은 퍼즐의 경우 탐색 공간이 매우 커질 수 있습니다. 이를 해결하기 위해 다음과 같은 최적화 전략을 고려할 수 있습니다:
1. 후보 숫자 미리 계산하기
각 빈칸에 대해 가능한 숫자의 목록을 유지하면, 가능한 후보가 가장 적은 칸부터 탐색을 시작할 수 있습니다. 이를 통해 탐색 공간을 줄일 수 있습니다.
2. 제약 조건의 전파(Constraint Propagation)
특정 칸에 숫자를 배치한 후, 해당 숫자로 인해 다른 칸의 후보 목록이 변경되는 것을 즉시 반영합니다. 이를 통해 일부 칸에서 후보가 하나로 좁혀질 수 있으며, 탐색 과정을 더욱 효율적으로 진행할 수 있습니다.

문제에서 제공하는 스도쿠 퍼즐은 “고유한 해답”을 가진다는 보장이 있습니다. 이 점은 탐색 알고리즘 설계를 단순화하는 데 큰 도움을 줍니다. 예를 들어, 다중 해답이 나올 가능성을 고려할 필요가 없으므로 알고리즘 구현이 더 간결해질 수 있습니다.

이 문제는 단순히 스도쿠를 해결하는 도구를 만드는 것을 넘어서, 다수의 퍼즐을 해결해야 하므로 성능 최적화가 매우 중요합니다. 많은 퍼즐을 처리하는 과정에서 알고리즘의 효율성이 실질적인 영향을 미치기 때문입니다.

Project Euler #96 문제는 프로그래머에게 논리적 문제 해결 능력과 성능 최적화라는 두 가지 중요한 측면을 시험합니다. 스도쿠 게임을 즐기시는 분들께는 인간적인 직관과 컴퓨터적인 계산 능력을 결합해 퍼즐을 해결하는 과정에서 큰 흥미와 만족감을 느끼실 수 있을 것입니다.

 

sudoku

 

제가 작성한 소스입니다.

//------------------------------------------------
//    Project Euler #96 - Su Doku
//        - by Aubrey Choi
//        - created at 2015-10-23
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <math.h>

#define    FILENAME    "0096.txt"

bool SolveSudoku(int sudoku[], int mask[27], int k)
{
    while( k < 81 && sudoku[k] ) k++;
    if( k == 81 ) return true;
    for( int i = 1 ; i < 10 ; i++ )
    {
        int row = k/9, col = k%9+9, box = (k/27)*3+(k/3)%3 + 18;
        if( mask[row] & (1<<i) ) continue;
        if( mask[col] & (1<<i) ) continue;
        if( mask[box] & (1<<i) ) continue;
        mask[row] |= 1<<i; mask[col] |= 1<<i; mask[box] |= 1<<i;
        sudoku[k] = i;
        if( SolveSudoku(sudoku, mask, k+1) ) return true;
        sudoku[k] = 0;
        mask[row] &= ~(1<<i); mask[col] &= ~(1<<i); mask[box] &= ~(1<<i);
    }
    return false;
}

void SolveSudoku(int sudoku[])
{
    int mask[27];
    memset(mask, 0, sizeof(mask));
    for( int k = 0 ; k < 81 ; k++ )
    {
        if( sudoku[k] == 0 ) continue;
        int row = k/9, col = k%9+9, box = (k/27)*3+(k/3)%3 + 18, i = sudoku[k];
        mask[row] |= 1<<i; mask[col] |= 1<<i; mask[box] |= 1<<i;
    }
    SolveSudoku(sudoku, mask, 0);
}

void solve1()
{
    int sudoku[81];
    FILE *fi = fopen(FILENAME, "r");

    int ans = 0;
    for( int i = 0 ; i < 50 ; i++ )
    {
        char line[100];
        fgets(line, 100, fi);
        printf("%s", line);
        for( int j = 0 ; j < 9 ; j++ )
        {
            fgets(line, 100, fi);
            for( int k = 0 ; k < 9 ; k++ )
            {
                sudoku[j*9+k] = line[k]-'0';
            }
        }
        SolveSudoku(sudoku);
        //for( int j = 0 ; j < 81 ; j++ )
        //{
        //    printf("%d ", sudoku[j]);
        //    if( j%9 == 8 ) printf("\n");
        //}
        ans += sudoku[0]*100+sudoku[1]*10+sudoku[2];
    }
    fclose(fi);

    printf("Ans = %d\n", ans);
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

    printf("Elapsed time is %.3f seconds \n", (float)(clock() - t) / CLOCKS_PER_SEC);
}

 

이 코드는 Project Euler #96에서 주어진 스도쿠 퍼즐들을 해결하는 프로그램입니다. 주된 목적은 50개의 스도쿠 퍼즐을 풀고, 각 퍼즐의 해답에서 첫 번째 세 자리 숫자를 추출하여 이들의 합을 계산하는 것입니다. 프로그램의 주요 부분을 단계별로 분석하면 다음과 같습니다.

1. 프로그램 개요

• 이 코드는 SolveSudoku라는 백트래킹 기반의 알고리즘을 사용하여 스도쿠 퍼즐을 해결합니다.
• 입력 파일 0096.txt에는 50개의 스도쿠 퍼즐이 포함되어 있습니다.
• 각 퍼즐을 해결한 뒤, 왼쪽 위 모서리 숫자 세 개(sudoku[0], sudoku[1], sudoku[2])를 조합하여 합계를 계산합니다.

2. 주요 함수 분석

SolveSudoku(int sudoku[], int mask[27], int k)

• 목적: 스도쿠를 백트래킹 기법으로 해결합니다.
• 매개변수:
• sudoku[]: 1차원 배열로 표현된 9x9 스도쿠 격자. 값이 0인 곳은 빈 칸입니다.
• mask[27]: 각 행, 열, 그리고 3x3 박스에 어떤 숫자가 이미 사용되었는지 기록하는 비트마스크.
• mask[0] ~ mask[8]: 각 행의 사용 상태.
• mask[9] ~ mask[17]: 각 열의 사용 상태.
• mask[18] ~ mask[26]: 각 3x3 박스의 사용 상태.
• k: 현재 탐색 중인 칸의 인덱스.
• 작동 방식:
1. k가 81이 되면 모든 칸이 채워졌으므로 해결된 상태로 간주하고 true를 반환합니다.
2. 현재 위치가 이미 채워져 있다면 다음 칸으로 이동합니다.
3. 빈 칸에 대해 1~9까지의 숫자를 하나씩 시도합니다.
• 특정 숫자가 해당 행, 열, 박스에서 이미 사용되었으면 건너뜁니다.
• 사용할 수 있으면 비트마스크를 업데이트하고 숫자를 배치합니다.
• 재귀적으로 다음 칸을 시도하며, 해결되면 true를 반환합니다.
• 실패하면 복원하고 다음 숫자를 시도합니다.
4. 모든 경우를 시도해도 해결되지 않으면 false를 반환합니다.

SolveSudoku(int sudoku[])

• 목적: 퍼즐 상태와 비트마스크를 초기화한 뒤, 백트래킹 알고리즘을 호출합니다.
• 작동 방식:
1. mask[] 배열을 초기화하여 모든 비트마스크를 0으로 설정합니다.
2. 주어진 퍼즐 상태에서 이미 채워진 숫자들을 반영해 비트마스크를 설정합니다.
3. 백트래킹 함수 SolveSudoku(sudoku, mask, 0)를 호출하여 퍼즐을 해결합니다.

solve1()

• 목적: 파일에서 스도쿠 퍼즐을 읽어와 각 퍼즐을 해결한 후, 결과를 계산합니다.
• 작동 방식:
1. 파일 0096.txt를 열어 퍼즐 데이터를 읽어옵니다.
2. 각 퍼즐을 1차원 배열 sudoku[]에 저장합니다.
3. SolveSudoku(sudoku)를 호출하여 퍼즐을 해결합니다.
4. 해결된 퍼즐의 왼쪽 위 세 자리 숫자를 추출하여 누적 합을 계산합니다.
5. 결과를 출력합니다.

3. 코드의 동작 과정

1. 프로그램이 실행되면 main() 함수에서 solve1()을 호출합니다.
2. solve1()은 파일에서 50개의 스도쿠 퍼즐을 순차적으로 읽고, 각 퍼즐을 해결하며 결과를 집계합니다.
3. SolveSudoku()는 백트래킹 기법으로 퍼즐을 해결합니다.
4. 모든 퍼즐을 처리한 뒤, 합계를 출력합니다.
5. 실행 시간은 clock()을 통해 측정됩니다.

4. 비트마스크를 활용한 효율성

• 각 행, 열, 박스의 숫자 사용 여부를 비트마스크로 관리하여 연산을 빠르게 수행합니다.
• 특정 숫자가 사용 중인지 확인할 때 mask[row] & (1<<i)와 같은 비트 연산을 사용하여 효율성을 극대화합니다.
• 숫자를 배치하거나 제거할 때도 비트 연산을 사용하여 빠르게 상태를 업데이트합니다.

5. 결과 출력

• 프로그램은 50개의 퍼즐을 해결한 뒤, 다음과 같은 형식으로 결과를 출력합니다:

Ans = <결과값>
Elapsed time is <소요 시간> seconds

이 프로그램은 스도쿠를 백트래킹 기법으로 해결하는 방식의 교과서적인 예이며, 비트마스크를 활용해 효율을 높였습니다.