Implement Sudoku Cheat

labuladongOriginalAbout 344 words

Implement the solveSudoku method as required. Create a working Sudoku solver that can solve any Sudoku problem with brute-force.

After you finish the code, click the "Submit" button to let the algorithm solve the Sudoku puzzle. When it's done, you can click the "Replay" button to see how the brute-force algorithm works step by step.

This problem is simple. You can directly use the solution from Backtracking Practice: Sudoku and N-Queens Problem. Here is a sample code:

function solveSudoku(boardHandler) {
    // will be true if a solution is found
    let found = false;

    function backtrack(index) {
        if (found) {
            // a solution has been found, end immediately
            return;
        }

        const m = 9, n = 9;
        const i = Math.floor(index / n), j = index % n;
        if (index === m * n) {
            // find a feasible solution, trigger the base case
            found = true;
            return;
        }

        if (boardHandler.get(i, j) !== null && !boardHandler.isEditable(i, j)) {
            // if there is a preset number, we don't need to enumerate it
            backtrack(index + 1);
            return;
        }

        for (let c = 1; c <= 9; c++) {
            // pruning: if we encounter an invalid number, skip it
            if (!isValid(i, j, c)) {
                continue;
            }

            // make a choice
            boardHandler.set(i, j, c);

            backtrack(index + 1);
            if (found) {
                // if a solution is found, end immediately
                // don't cancel the choice, otherwise the value will be reset
                return;
            }

            // cancel the choice
            boardHandler.set(i, j, null);
        }
    }

    function isValid(r, c, num) {
        // check if there is a duplicate in the row
        for (let i = 0; i < 9; i++) {
            if (boardHandler.get(r, i) === num) return false;
        }
        
        // check if there is a duplicate in the column
        for (let i = 0; i < 9; i++) {
            if (boardHandler.get(i, c) === num) return false;
        }
        
        // check if there is a duplicate in the 3 x 3 box
        const boxRow = Math.floor(r / 3) * 3;
        const boxCol = Math.floor(c / 3) * 3;
        for (let i = 0; i < 3; i++) {
            for (let j = 0; j < 3; j++) {
                if (boardHandler.get(boxRow + i, boxCol + j) === num) {
                    return false;
                }
            }
        }
        
        return true;
    }

    backtrack(0);
}