Implement Sudoku Cheat

labuladongOriginalAbout 344 words

Implement the solveSudoku method as required to create a functioning Sudoku solver. Use brute-force to solve any Sudoku problem with a single click.

After completing the code, click the "Submit" button to let the algorithm solve the Sudoku problem. Once completed, you can click the "Replay" button to view the algorithm's brute-force process.

Sudoku Game Demo

This problem is relatively simple and can directly apply the solution from Backtracking Algorithm Practice: Sudoku and N-Queens Problem. The reference code is as follows:

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);
}