[LeetCode] 37. Sudoku Solver

백트레킹을 활용해야 하는 문제이다.

이전 문제 풀이와 같이 3x3 서브 박스 검증이 가능하다면 어렵지 않은 풀이가 가능하다.

😎풀이

/**
 Do not return anything, modify board in-place instead.
 */
function solveSudoku(board: string[][]): void {
    backTracking(board)
};

function backTracking(board: string[][]) {
    for(let row = 0; row < 9; row++) {
        for(let col = 0; col < 9; col++) {
            // 빈 셀을 찾으면
            if (board[row][col] === '.') {
                // 1부터 9까지의 숫자를 시도
                for (let num = 1; num <= 9; num++) {
                    const strNum = num.toString();
                    // 현재 숫자가 유효한지 확인
                    if (isValidCell(board, row, col, strNum)) {
                        // 유효하다면 셀에 숫자를 채움
                        board[row][col] = strNum;
                        // 재귀적으로 다음 빈 셀을 채우기 시도
                        if (backTracking(board)) {
                            return true; // 모든 셀이 채워졌다면 성공
                        } else {
                            // 실패했다면 백트래킹: 셀을 다시 비움
                            board[row][col] = '.';
                        }
                    }
                }
                // 1-9 중 어떤 숫자도 유효하지 않다면 이전 단계로 백트래킹
                return false;
            }

        }
    }

    return true
}

function isValidCell(board: string[][], row: number, col: number, numStr: string) {

    // 동일 행/열 검사
    for(let i = 0; i < 9; i++) {
        if(board[row][i] === numStr) return false
        if(board[i][col] === numStr) return false
    }

    // 3x3 서브 박스 검사
    const startRow = Math.floor(row / 3) * 3;
    const startCol = Math.floor(col / 3) * 3;
    for (let i = 0; i < 3; i++) {
        for (let j = 0; j < 3; j++) {
            if (board[i + startRow][j + startCol] === numStr) return false;
        }
    }
    

    return true
}