[백준 BOJ] 2239번 - 스도쿠 (C++)

2239번: 스도쿠 (acmicpc.net)

2239번: 스도쿠

81자리의 수가 제일 작은 스도쿠를 만들어서 출력하는 문제이다. 81자리의 수란

이를 143628579572139....854396127로 만든 것을 의미한다.

이 문제는 백트래킹으로 풀었다. 0이 위치한 좌표를 저장한다음 이에 대해 백트래킹을 돌렸다. 이 때 가장 작게 만들려면 맨왼쪽 위의 0부터 차례대로 1부터 9까지의 값을 넣어주면서 스도쿠가 만들어지는지 보면 된다.

#include <iostream>
#include <algorithm>
#include <memory.h>
#include <vector>

using namespace std;

int board[9][9];
vector<pair<int, int>> zero;

bool check(int n, int i, int j)
{
    for (int p = 0; p < 9; p++)
    {
        if (p != j)
            if (board[i][p] == n)
                return false;
        if (p != i)
            if (board[p][j] == n)
                return false;
    }
    int x = (i / 3) * 3;
    int y = (j / 3) * 3;
    for (int p = x; p < x + 3; p++)
    {
        for (int q = y; q < y + 3; q++)
        {
            if (p != i && q != j)
            {
                if (board[p][q] == n)
                    return false;
            }
        }
    }
    return true;
}

bool finish = false;
void back(int n)
{
    if (finish)
        return;
    if (n == zero.size())
    {
        finish = true;
    }
    else
    {
        for (int i = 1; i <= 9; i++)
        {
            if (check(i, zero[n].first, zero[n].second))
            {
                board[zero[n].first][zero[n].second] = i;
                back(n + 1);
                if (finish)
                    return;
                board[zero[n].first][zero[n].second] = 0;
            }
        }
    }
}

int main()
{
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            scanf("%1d", &board[i][j]);
            if (board[i][j] == 0)
            {
                zero.emplace_back(i, j);
            }
        }
    }
    back(0);
    int en = 8;
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            cout << board[i][j];
        }
        cout << '\n';
    }
    return 0;
}