Sudoku Solver

Sudoku Solver

문제 내용

수도쿠에 빈 칸을 모두 채우시오

 

접근 방법

full search를 제외하고 해결 방법은 없다.

가장 쉬운 방법은 모든칸에 모든 값을 대입하는 방법이다.

row 9개 col 9개의 cell로 구성된 board가 수도쿠 임으로

모든 cell은 81칸으로 이루어져 있다.

각 cell은 1부터 9까지 9개의 값을 갖을 수 있다.

이런칸이 81칸임으로

$$ 9^{81} $$

이 된다.

이것을 약간 최적화 해보자면 다음과 같이 바꿀수 있다.

- 앞서 선택된 값을 선택하지 않는다.

예를 들자면

9개의 네모칸이 있다고 생각해 보겠다.

이중 첫번째 네모칸을 1로 선택한다면 뒤에있는 8개의 칸은 2에서 9사이 선택권을 갖는다.

이런방식으로 첫번째 칸은 9가지 선택권을 두번째 칸은 8가지 .. 최종은 1가지 선택권을 갖음으로

$ 9 * 8 * 7 * ... * 1$ 이 됨으로 

$$ 9! $$

이 한 row에 선택할 수 있는 횟수이다. Row가 모두 9개 임으로

$$ 9!^9 $$

번의 횟수로 $ 9^{81} > 9!^9 $ 가 더 많은 횟수를 순환하게 된다.

이를 Backtracking 방식으로 접근을 한다면 다음과 같이 할 수 있다.

1. Row와 Col 그리고 Box를 Check하기 위한 공간을 만든다.

그런데 Box의 경우는 네모의 모양이 다른 Row와 Col과는 다소 다르다.

이런 모습으로 index를 관리 해야 하기 때문이다.

해당 부분을 다음과 같이 계산 할 수 있다.

• Box Number = (Row / 3* 3)  + (Col / 3)

2. Board를 순환 한다.

빈 공간이 나타날때 까지 순환한 이후 해당 공간이 나타나면 1에서 9사이의 값을 넣어 주고 다음 빈 공간을 찾는 행위를 순한 하면 된다.

순환의 종료 조건은 다음과 같다.

• Row 8, Col 8에 도착을 했고 숫자가 정해 져있다면 답을 구한 것이다.
• 그렇지 않다면 col이 8이면 row + 1, col은 0이다.
• col이 8미만이면 col + 1이다

 

3. 빈 공간이 나타나면 다음과 같이 3가지를 만족해야 한다.

• Box에 없는 수인가
• Row에 없는 수인가
• Col에 없는 수인가

이렇게 3가지가 만족된다면 다음 공간으로 Backtracking을 넘어 간도 된다.

 

마지막으로 Backtracking이 실패 했다면 해당 Backtracking은 원상 복구를 시키고 다시 시작해야한다.

 

var solveSudoku = function(board) {
    let boardSize = 9;
    let boxSize = 3;
    let solved = false;
    //1에서 10사이에 값이 있는지 확인 하는 Array임으로 10 size의 Array를 갖음
    let rowArr = new Array(9).fill(0).map(_=> new Array(10).fill(0));
    let colArr = new Array(9).fill(0).map(_=> new Array(10).fill(0));
    let boxArr = new Array(9).fill(0).map(_=> new Array(10).fill(0));

    function saveDigits(digit,row,col){
        rowArr[row][digit]++;
        colArr[col][digit]++;
        boxArr[(Math.floor(row/3)*3) + (Math.floor(col/3))][digit]++;
        board[row][col] = digit.toString();
    }
    function removeDigits(digit,row,col){
        rowArr[row][digit]--;
        colArr[col][digit]--;
        boxArr[(Math.floor(row/3)*3) + (Math.floor(col/3))][digit]--;
        board[row][col] = '.';
    }

    function existedDigit(digit,row,col){
        return !(rowArr[row][digit] | colArr[col][digit] | boxArr[(Math.floor(row/3)*3) + (Math.floor(col/3))][digit]);
    }

    function backtracking(row,col){
        if(board[row][col] === "."){ //빈 값일 경우
            for(let i = 1; i < 10; i++){
                if(existedDigit(i,row,col)){ //빈공간에 i의 값이 들어갈 수 있다면 해당 값을 넣고 backtracking을 이동한다.
                    saveDigits(i, row, col);
                    moveNext(row, col);

                    if(!solved) removeDigits(i, row, col); //backtracking을 끝까지 갔지만 해결이 안된 값임으로 입력했던 값을 삭제 한다.
                }
            }
        } else { // 해당 보드에 값이 있을 경우
            moveNext(row,col);
        }
    }


    function moveNext(row, col){ //다음으로 move할지 종료할지를 결정한다.
        if(row === 8 && col === 8){
            solved = true;
        } else {
            if(8 <= col){ //더이상 우측으로 가지 못함으로 row를 하나더 증가 시킨다
                backtracking(row + 1, 0);
            } else { // 우측으로 point를 이동한다.
                backtracking(row, col+1);
            }
        }
    }

    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            if(board[i][j] !== "."){
                saveDigits(parseInt(board[i][j]), i, j);
            }
        }
    }

    backtracking(0,0); //시작은 0,0에서 시작하고 8,8에서 종료한다.

};