[2239번][C/C++] 스도쿠

https://www.acmicpc.net/problem/2239

2239번: 스도쿠

미완성된 스도쿠 판이 입력으로 주어질 때, 스도쿠판을 완성해서 출력하는 문제이다.

 

이 문제는 일단 N-Queen과 굉장히 유사하다.

N-Queen문제를 생각해보면 보드에서 모든 자리를 살펴보는데 각 자리에 대해서 queen을 놓을 수 있는지 없는지 판단한 뒤, 놓을 수 있는 경우에는 놓고 지나거나 안 놓고 지나가고, 놓을 수 없는 경우에는 안놓고 지나간다.

 

이러한 백트래킹은 다음과 같은 논리구조로 구성된다.

     1. 지금 내가 있는 칸에서 하고자하는 걸 할 수 있는 조건이 되는가?

           1-1) YES : 하고 지나가는 경우와 안 하고 지나가는 경우, 두가지를 재귀적으로 탐색한다.

           1-2) NO : 무조건 안 하고 지나간다.

 

이러한 논리구조는 N-Queen문제 뿐 아니라, 이 스도쿠 문제에서도 그대로 적용된다.

 

여기서 생각해볼만한 점은 어떻게 지금 내 위치에서 어떤 수를 놓을 수 있는지 없는지 체크할 것인가? 라는 문제이다.

이는 3가지 테스트에 대해서 통과하면된다.

        1. 지금 보드에서의 내 위치의 정사각형 모양의 네모 칸에 지금 내가 넣으려는 수와 중복된 수가 없어야한다.

        2. 지금 보드에서 내 y좌표에서 모든 x위치의 칸에 지금 내가 넣으려는 수와 중복된 수가 없어야한다.

        3. 지금 보드에서 내 x좌표에서 모든 y위치의 칸에 지금 내가 넣으려는 수와 중복된 수가 없어야한다.

 

이 테스트를 통과하면 이제 재귀적으로 지금 수를 넣고 지나가거나 안넣고 다른 수를 테스트하거나 할 수 있다.

이후는 구현력의 문제이다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

int map[11][11];
bool flag;

void input()
{
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            char inp;
            scanf("%c", &inp);

            map[i][j] = inp - '0';
        }
        getchar();
    }
}

void print()
{
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            printf("%d", map[i][j]);
        }
        printf("\n");
    }
}

bool test(int y, int x, int num)
{
    int baseY = (y / 3) * 3;
    int baseX = (x / 3) * 3;

    // TEST FOR SQUARE
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            if (map[baseY + i][baseX + j] == num)
                return false;
        }
    }

    // TEST FOR VERTICAL, HORIZONTAL LINE
    for (int i = 0; i < 9; i++)
    {
        if (map[i][x] == num || map[y][i] == num)
            return false;
    }

    // TEST PASSED
    return true;
}

void backTracking(int y, int x)
{
    // BASE CASE
    if (flag)
        return;
    if (y == 9 && x == 0)
    {
        print();
        flag = true;
        return;
    }

    if (map[y][x] != 0)
    {
        // BACK TRACKING : CASE 1
        if (x == 8)
            backTracking(y + 1, 0);
        else
            backTracking(y, x + 1);
        if (flag)
            return;
    }
    else
    {
        // BACKTRACKING : CASE 2
        for (int i = 1; i <= 9; i++)
        {
            if (test(y, x, i))
            {
                map[y][x] = i;
                if (x == 8)
                    backTracking(y + 1, 0);
                else
                    backTracking(y, x + 1);
                if (flag)
                    return;
                map[y][x] = 0;
            }
        }
    }
}

int main()
{
    input();

    backTracking(0, 0);
    return 0;
}