Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each colum

solveSudoku.js

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function(board) {
    const SIZE = 9;

    // Track used digits in rows, columns, and 3x3 boxes
    const row = Array.from({ length: SIZE }, () => Array(SIZE).fill(false));
    const col = Array.from({ length: SIZE }, () => Array(SIZE).fill(false));
    const box = Array.from({ length: SIZE }, () => Array(SIZE).fill(false));

    // Initialize tracking arrays based on the initial board
    function initialize() {
        for (let i = 0; i < SIZE; i++) {
            for (let j = 0; j < SIZE; j++) {
                const cell = board[i][j];
                if (cell !== '.') {
                    const num = parseInt(cell) - 1;
                    const boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);
                    row[i][num] = true;
                    col[j][num] = true;
                    box[boxIndex][num] = true;
                }
            }
        }
    }

    // Check if placing digit `char` at (i, j) is valid
    function isValid(i, j, char) {
        const num = parseInt(char) - 1;
        const boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);
        return !row[i][num] && !col[j][num] && !box[boxIndex][num];
    }

    // Recursive DFS to fill the board
    function dfs(i, j) {
        // If we've reached the end of the board, we're done
        if (i === SIZE) return true;

        // Move to the next cell
        const nextI = j === SIZE - 1 ? i + 1 : i;
        const nextJ = j === SIZE - 1 ? 0 : j + 1;

        // Skip filled cells
        if (board[i][j] !== '.') return dfs(nextI, nextJ);

        for (let num = 1; num <= 9; num++) {
            const char = num.toString();
            if (isValid(i, j, char)) {
                board[i][j] = char;
                const idx = num - 1;
                const boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);

                // Mark digit as used
                row[i][idx] = col[j][idx] = box[boxIndex][idx] = true;

                // Recurse
                if (dfs(nextI, nextJ)) return true;

                // Backtrack
                board[i][j] = '.';
                row[i][idx] = col[j][idx] = box[boxIndex][idx] = false;
            }
        }

        return false;
    }

    initialize();
    dfs(0, 0);
};