[Algorithm Problem] 스도쿠

문제

스도쿠 풀이

코드

const boardSize = 9;

const findZeroArray = function (board) {
    let arr = [];

    // find value "0" position
    for (let x = 0; x < 9; x++) {
        for (let y = 0; y < 9; y++) {
            if (board[x][y] === 0)
                arr.push([x, y]);
        }
    }
    return arr;
}

const checkBox = function (board, x, y, value) {
    // select section
    let startX = parseInt(x / 3) * 3;
    let startY = parseInt(y / 3) * 3;

    // inspect section
    for (let i = startX; i < startX + 3; i++) {
        for (let j = startY; j < startY + 3; j++) {
            if (board[i][j] === value)
                return false;
        }
    }
    return true;
}

const checkCorrect = function (board, x, y, value) {
    for (let index = 0; index < boardSize; index++) {
        // inspect axis X
        if (board[x][index] === value) return false;
        // inspect axis Y
        if (board[index][y] === value) return false;
    }
    // inspect 3x3 box
    if (checkBox(board, x, y, value) === false) return false;
    return true;
}

const backTracking = function (board, zeroPositionArray, n) {
    // fill all value
    if (n === zeroPositionArray.length)
        return true;

    // get value "0" position
    let x = zeroPositionArray[n][0];
    let y = zeroPositionArray[n][1];

    // insert 1 ~ 9 value
    for (let value = 1; value <= 9; value++) {
        // if not problem
        if (checkCorrect(board, x, y, value)) {
            // insert value
            board[x][y] = value;
            // next "0" position recursed
            if (backTracking(board, zeroPositionArray,n + 1)) return true;
            // if is wrong value, set "0"
            board[x][y] = 0;
        }
    }
    // all value (1 ~ 9) is wrong, then back
    return false;
}

const sudoku = function (board) {
    let zeroPositionArray = findZeroArray(board);
    backTracking(board, zeroPositionArray, 0);
    return board;
};

풀이

1. zeroPositionArray에 채워 넣어야 할 위치인 값이 0인 것들의 위치를 담음
2. 채워 넣을 board, 좌표가 담긴 배열 zeroPositionArray, 값을 처리하는 순서 n의 초기 값인 0을 넣어 재귀 함수 실행
3. 모두 채웠는지 확인한 뒤 완료했다면 함수 종료
4. x와 y에 구해야할 위치의 좌표 할당
5. 값 1부터 9까지 반복을 돌리면서 checkCorrect 함수를 통해 올바른 값인지 검사
   5-1. checkCorrect : 행과 열에 대해 같은 값이 있는지 검사
   5-2. checkCorrect - checkBox : 3x3 사각형 안에 있는 숫자 검사
6. 올바른 값이라면 value 할당
7. 그 다음 칸인 n+1을 넣어 재귀함수 호출
8. 3~7번 과정 반복
   8-1. 특정 칸에서 1~9의 값이 전부 올바르지 않아 반복문이 종료됐을 경우 0으로 초기화하면서 false반환
   8-2. 다시 앞의 칸에 해당하는 재귀함수로 돌아와 다른 값을 넣어 다시 시도
9. 값이 모두 채워져 return true를 하여 연쇄적으로 재귀함수 종료