Written by DK-Lite
on December 19, 2019

[LeetCode .37] Sudoku Solver

Problem

비어있는 스도쿠 배열에서 스도쿠 룰에 맞게 채워넣어라

Solution

우선, 간단히 스도쿠 룰에 대해 설명하자면

9 X 9 행렬에서 각 행과 열은 1~9사이의 숫자가 들어갈 수 있다.
각각의 행과 열은 같은 숫자가 들어갈 수 없다.
스도쿠 맵에서 일정한 크기로 가로 or 세로의 3분할 된 지역은 같은 숫자가 들어갈 수 없다.

스도쿠 문제의 솔루션은 백트래킹 방법이 가장 보편화되어있다. 추가적인 탐색 방법으로는 전체 비어있는 곳을 탐색하며, 위 3가지 룰에 위반되지 않는 숫자를 넣고 다음 탐색을 시도한다.

빠른 속도와 간결성을 위해 아래 팁을 사용

백트래킹의 9 X 9를 2차원으로 탐색하기에는 코딩의 어려움이 있음으로 하나의 숫자로 좌표를 표현하는 방법을 사용
많은 경우의 수가 발생하는데 매번 나머지 연산을 시도하면 속도가 느려지고 중복되는 호출이 발생한다. 때문에 미리 숫자에 대한 X, Y 테이블을 생성해두고 바로 호출
스도쿠 맵의 끝에 도달(81번)했다면 제대로 생성된 스도쿠 결과이므로 모든 백트래킹 종료

Code

class Solution {
public:
    bool vert[10][10];
    bool hori[10][10];
    bool area[4][4][10];
    int xdp[82];
    int ydp[82];

    bool checkIn(int x, int y, int value){
        // 스도쿠 배열의 각 행,열,지역 체크
        if(vert[y][value]) return false;
        if(hori[x][value]) return false;
        if(area[y/3][x/3][value]) return false;
        
        // 체크인
        vert[y][value] = true;
        hori[x][value] = true;
        area[y/3][x/3][value] = true;
        return true;
        
    }
    void checkOut(int x, int y, int value){
        // 체크아웃
        vert[y][value] = false;
        hori[x][value] = false;
        area[y/3][x/3][value] = false;
    }
    
    bool back(vector<vector<char>>& board, int p){
        
        // 스도쿠 끝에 도달하면 back 완전 종료
        if(p == 81)
            return true;
        
        int x = xdp[p];
        int y = ydp[p];
        
        // 이미 숫자가 존재 한다면 다음번호로 탐색
        if(board[y][x] != '.') {
            if(back(board, p+1)) return true;
            return false;
        }
        

        for(int i = 1; i <10; i++){
            // 이미 check in 된 숫자라면 무시
            if(!checkIn(x, y, i)) continue;
            board[y][x] = i + '0';

            if( back(board, p+1) ) return true;

            // 원상복귀
            board[y][x] = '.';
            checkOut(x, y, i);
        }
        return false;
    }
    
    // Main Start
    void solveSudoku(vector<vector<char>>& board) {
        // 이미 채워진 부분은 check in
        for(int i = 0; i <9; i++)
            for(int j = 0 ;j <9; j++){
                if(board[i][j]=='.') continue;
                checkIn(j, i, board[i][j]-'0');
            }

        // 각 포인트별 좌표에 대한 테이블 생성
        for(int i = 0 ;i < 81; i++){
            xdp[i] = i%9;
            ydp[i] = i/9;
        }
        back(board, 0);
    }
};

Reference

https://leetcode.com/problems/sudoku-solver/

← → Top