LeetCode Sudoku (JavaScript), Backtracking

링크 : https://leetcode.com/problems/sudoku-solver/description/

문제 설명

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

Example 1:

Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
Explanation: The input board is shown above and the only valid solution is shown below:

Constraints:

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit or '.'.
• It is guaranteed that the input board has only one solution.

---

문제 풀이

접근 방식

1. 각 행, 열, 박스 내부에 1~9 숫자가 있는지 판단하기 위해 2차원 배열 선언 (각 자리 숫자가 쓰였는지 판단하기 위해)
   • 좌표에 따른 박스(squares)의 특정 위치 계산하는 법은 다음과 같음
     • (x, y) -> (x/9) * 3 + (y/9)
     • x를 9로 나눈 몫에 3을 곱한 값 + y를 9로 나눈 몫
2. 입력된 board를 토대로 rows, cols, squares 정보를 채워 넣음
3. Backtracking을 통해 board를 채워나감

---

Backtracking 로직

1. n (0 ~ 81)을 기준으로 재귀를 돎
2. n 값을 기준으로 좌표 구하는 법
   • n / 9 = x좌표
   • n % 9 = y좌표
3. 특정 좌표가 '.'일 때 1~9사이의 숫자를 하나 씩 대입하면서 board를 채워나감.
   • 주의 사항 (return 값)
     • board를 채워나가는 solution 함수를 단순히 재귀만 돌렸을 경우 재귀가 끝나고 백트래킹 로직에 의해 모든 곳이 '.'로 초기화 되기 때문에 제대로 구해지지 않음
     • 따라서, 재귀를 진행하는 과정에서 true를 리턴한다면 롤백 시키지 않도록 조건을 설정해줘야 함
       • `if (solution(index + 1)) { return true ; }` 부분

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function(board) {
    const LENGTH = 9;
    // 각 행에 대한 정보
    const rows = Array.from({ length: LENGTH }, () => Array(LENGTH).fill(false));
    // 각 열에 대한 정보
    const cols = Array.from({ length: LENGTH }, () => Array(LENGTH).fill(false));
    // 특정 board 3 x 3 에 대한 정보
    const squares = Array.from({ length: LENGTH }, () => Array(LENGTH).fill(false));

    // 입력된 정보를 토대로 rows, cols, squares 정보 채우기
    for (let i = 0; i < LENGTH; i++) {
        for (let j = 0; j < LENGTH; j++) {
            if (board[i][j] !== '.') {
                const target = parseInt(board[i][j]);
                rows[i][target] = true;
                cols[j][target] = true;
                squares[Math.floor(j / 3) * 3 + Math.floor(i / 3)][target] = true;
            }       
        }
    }

    const solution = (index) => {
        if (index === 81) {
            return true;
        }

        const x = Math.floor(index / LENGTH);
        const y = index % LENGTH;

        if (board[y][x] === '.') {
            for (let i = 1; i <= LENGTH; i++) {
                const s_id = Math.floor(x / 3) * 3 + Math.floor(y / 3);
                if (!rows[y][i] && !cols[x][i] && !squares[s_id][i]) {
                    rows[y][i] = cols[x][i] = squares[s_id][i] = true;
                    board[y][x] = i.toString();

                    if (solution(index + 1)) {
                        return true;
                    };

                    rows[y][i] = cols[x][i] = squares[s_id][i] = false;
                    board[y][x] = '.';
                }
            }
        } else {
            return solution(index + 1);
        }

        return false;
    }

    solution(0);
};

---

결론

• 재귀를 돌면서 리턴을 하는 과정에서 백트래킹에 의해 롤백되는 부분의 로직을 처리하는 것이 중요
• 특정 좌표를 어떻게 관리할지 -> rows, cols, squares 각각 2차원 배열로 관리
• n (0 ~ 81)의 값을 토대로 x, y 좌표 구하는 법
  • x 좌표 : n / 9
  • y 좌표 : n % 9
• x, y 좌표를 통해 특정 squares의 위치(0~8)를 구하는 법
  • (x / 9) * 3 + (y / 9)