문제

2339번 스도쿠

풀이

답이 여러개인 경우도 고려해야 하기 때문에 백트래킹으로 모든 경우의 수를 살펴봐야합니다.

우선 스도쿠의 규칙에 의해 중복된 숫자가 존재하지 않도록 각 행, 열, 3x3 사각형에 해당하는 중복 확인을 위한 배열을 만듭니다. 숫자가 스도쿠판에 하나 채워지면 해당 위치의 행, 열, 사각형을 의미하는 배열의 숫자를 체크해둡니다.

답이 여러개일 경우 사전식으로 가장 앞서는 것을 출력해야 하므로 왼쪽위부터, 1부터 채워넣어보며 완성이 되는 경우를 바로 답으로 채택합니다. 이를 위해 백트래킹 함수의 리턴을 bool로 하여 어떤 경우가 true를 리턴한다면 그 답을 채택하도록 하였습니다.

코드

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

using namespace std;

int sudoku[9][9];
bool row[9][10];
bool col[9][10];
bool square[3][3][10];

bool dfs(int idx)
{
    if (idx == 9*9)
        return true;

    int x = idx / 9;
    int y = idx % 9;

    if (sudoku[x][y] != 0)
        return dfs(idx+1);
    
    for (int i=1; i<10; ++i)
    {
        if (row[x][i] || col[y][i] || square[x/3][y/3][i])
            continue;

        row[x][i] = true;
        col[y][i] = true;
        square[x/3][y/3][i] = true;

        sudoku[x][y] = i;
        if (dfs(idx+1))
        {
            return true;
        }
        sudoku[x][y] = 0;
        
        row[x][i] = false;
        col[y][i] = false;
        square[x/3][y/3][i] = false;
    }

    return false;
    
}

int main()
{
    memset(row, false, sizeof(row));
    memset(col, false, sizeof(col));
    memset(square, false, sizeof(square));

    for (int i=0; i<9; ++i)
    {
        string input;
        cin >> input;
        for (int j=0; j<9; ++j)
        {
            int val = (int)input[j] - '0';
            sudoku[i][j] = val;

            row[i][val] = true;
            col[j][val] = true;
            square[i/3][j/3][val] = true;
        }
    }
    
    dfs(0);

    for (int i=0; i<9; ++i)
    {
        for (int j=0; j<9; ++j)
        {
            cout << sudoku[i][j];
        }
        cout << endl;
    } 
    return 0;
}