배너 이미지

스도쿠 풀어주는 프로그램 만들기

최종 수정일 : (8개월 전)

Github
웹 앱

평소 즐기는 게임인 스도쿠를 푸는 앱을 만들어봤습니다.
C++로 작업했다가, 아무래도 접근성이 많이 떨어져 웹 앱으로도 만들었습니다.

나중에 좀 더 실력이 늘면 카메라로 스도쿠 문제를 스캔해서 자동으로 풀어주는 수준까지 업데이트해보고 싶네요.

C++

#include <iostream>
const int g_max = 9;
const int g_subMax = g_max / 3;
int grid[g_max][g_max];

스도쿠 칸의 크기를 g_max에, 작은 칸(Subgrid)의 크기를 g_subMax에 담아뒀습니다.
이후, 스도쿠 칸이 담길 배열을 만들어줍니다.

bool isSolvable()
{
    int rowcol;
    int filled = 0;

    for (row = 0row < g_maxrow++)
    {
        for (col = 0col < g_maxcol++)
        {
            if (grid[row][col!= 0)
                filled++;
        }
    }

    return filled >= 17;
}

스도쿠가 하나의 해만 갖기 위해선 최소 17개의 칸이 채워져 있어야 합니다.
풀이를 시작하기 전에 풀 수 있는 최소한의 조건이 충족됐는지 검사하도록 했습니다.

스도쿠 판 크기가 달라지면 조건이 바뀌기도 하고, 어차피 검사하지 않아도 조건이 충족되지 않으면 높은 확률로 풀다가 던져버리니 빼도 무관한 부분이긴 합니다.

bool isInRow(int rowint num)
{
    for (int i = 0i < g_maxi++)
    {
        if (num == grid[row][i])
            return true;
    }

    return false;
}

bool isInCol(int colint num)
{
    for (int i = 0i < g_maxi++)
    {
        if (num == grid[i][col])
            return true;
    }

    return false;
}

bool isInSubGrid(int startRowint startColint num)
{
    int ij;

    for (i = startRowi < startRow + g_subMaxi++)
    {
        for (j = startColj < startCol + g_subMaxj++)
        {
            if (grid[i][j== num)
                return true;
        }
    }

    return false;
}

bool isValid(int rowint colint num)
{
    return !isInRow(rownum&& !isInCol(colnum&& !isInSubGrid(row - row % g_subMaxcol - col % g_subMaxnum);
}

스도쿠 풀이에 핵심이 되는 부분입니다.
행, 열, 작은 칸에 같은 숫자가 있는지 확인하고, 어디에도 같은 숫자가 없으면 참을 반환합니다.

bool hasEmptyBox(int &rowint &col)
{
    for (row = 0row < g_maxrow++)
    {
        for (col = 0col < g_maxcol++)
        {
            if (grid[row][col== 0)
                return true;
        }
    }

    return false;
}

bool solve()
{
    int rowcol;

    if (!hasEmptyBox(rowcol))
        return true;

    for (int num = 1num <= g_maxnum++)
    {
        if (isValid(rowcolnum))
        {
            grid[row][col= num;
            if (solve())
                return true;
            grid[row][col= 0;
        }
    }

    return false;
}

스도쿠를 풀이하는 부분입니다.
0(풀이되지 않은 부분)인 칸을 찾아서, 1부터 최댓값(9)까지 숫자를 넣어보며 유효성을 확인하고, 유효한 값이 나오지 않으면 0으로 재설정합니다.

int main(void)
{
    for (int i = 0i < g_maxi++)
    {
        for (int j = 0j < g_maxj++)
        {
            scanf("%d"&grid[i][j]);
        }
    }

    if (!isSolvable())
    {
        printf("It's undefeatable!");
    }
    else
    {
        if (solve())
            printGrid();
        else
            printf("Oops! I can't solve this.");
    }

    return 0;
}

이제 입력을 받고 스도쿠를 풀게 하기만 하면 됩니다.

C++ 스도쿠 실행 결과

g++ -o sudoku sudoku.cpp로 빌드 후 실행하면, 위 사진처럼 스도쿠를 자동으로 풀어주기 시작합니다.

Typescript

solver.ts 확인

아무래도 C++로만 만들어두면 접근성이 굉장히 떨어지기에, 편하게 실행할 수 있도록 웹으로 옮겼습니다.

처음엔 웹 어셈블리를 사용해볼까 하다가, 스도쿠 풀이는 계산량이 적어서 시간이 오래 걸리지 않는데 웹 어셈블리를 쓰면 wasm 파일 불러오는 데만 시간이 더 들 것 같아 타입스크립트로 만들었습니다. 포인터를 활용할 수가 없어서, 객체를 사용해 비슷하게 작동하도록 수정한 것만 제외하면, C++로 만든 코드와 똑같이 작동합니다.

그 다음, app.ts에 작업한 것처럼 9 * 9 스도쿠 그리드를 배열에 넣어주고, 배열을 전부 탐색하며 input을 생성하게 하여 웹 앱을 완성했습니다.

풀이 안 된 스도쿠

모르는 칸은 0으로 채우거나 빈칸으로 남겨두고 "Solve" 버튼을 클릭하면

스도쿠 풀이 완료

순식간에 풀어줍니다. 제 기기 기준으론 14ms 내외로 걸리네요.

Reference

Sudoku Solver in C++
[지식in] 스도쿠와 라틴방진


profile

이메일 주소는 공개되지 않습니다.

주의 : 비밀 댓글 사용 시 수정 기능을 이용할 수 있는 시간이 지나면 작성자도 내용 확인이 불가능합니다.
카카오페이 qr코드 모바일이시라면 클릭