sudoku-practice-test.js

/**
 * Problem: Sudoku Solver
 *
 * You are given a 9x9 Sudoku board represented as a 2D array of characters.
 * Empty cells are denoted by '.'.
 *
 * Goal:
 * Fill the board in-place so that it becomes a valid completed Sudoku.
 *
 * Rules:
 * - Each row must contain the digits '1' to '9' without repetition.
 * - Each column must contain the digits '1' to '9' without repetition.
 * - Each of the 9 3x3 sub-boxes must contain the digits '1' to '9' without repetition.
 *
 * Input: 9x9 grid with '.' for blanks
 * Output: The same grid, modified in-place to a solved state
 *
 * Approach:
 * Use backtracking to try placing digits in empty cells.
 * Validate each placement with a helper like isValid().
 * Backtrack if a placement leads to an invalid board state.
 */
function solveSudoku(board) {
    // TODO: implement backtrack(board)
    backtrack(board);
    return board;
}

function backtrack(board) {
    // 1. Loop over each cell in the board (row and col)
    // 2. If the cell is not empty ('.'), skip it
    // 3. Try digits '1' to '9'
    //    a. Check if placing the digit is valid using isValid()
    //    b. If valid, place the digit
    //    c. Recurse to continue solving
    //    d. If it fails, undo the placement (backtrack)
    // 4. If no digit works, return false to trigger backtracking
    // 5. If the entire board is filled, return true
}

function isValid(board, row, col, char) {
    for (let i = 0; i < 9; i++) {
        if (board[row][i] === char) return false; // row check
        if (board[i][col] === char) return false; // col check

        const boxRow = 3 * Math.floor(row / 3) + Math.floor(i / 3);
        const boxCol = 3 * Math.floor(col / 3) + (i % 3);
        if (board[boxRow][boxCol] === char) return false; // 3x3 box check
    }
    return true;
}

function testSudokuSolver() {
    const input = [
        ['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']
    ];

    const expected = [
        ['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']
    ];

    solveSudoku(input);

    const passed = JSON.stringify(input) === JSON.stringify(expected);
    console.log(passed ? "✅ PASS" : "❌ FAIL");
}

testSudokuSolver();