Implement Sudoku Cheat

labuladongOriginalAbout 1526 words

Please implement the solveSudoku method to make a working Sudoku solver. The program should solve any Sudoku problem with one click using brute-force.

After you finish the code, click the "Submit" button to let the algorithm solve the Sudoku puzzle. Then, you can click the "Replay" button to see how the algorithm uses brute-force to solve the problem step by step.

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

java

// The game panel only supports submitting JavaScript code
// The code in other languages is only for understanding

// Assume BoardHandler is an interface
interface BoardHandler {
    Integer get(int i, int j);
    void set(int i, int j, Integer value);
    boolean isEditable(int i, int j);
}

public static void solveSudoku(BoardHandler boardHandler) {
    // will be true if a solution is found
    boolean[] found = {false};

    class Solver {
        void backtrack(int index) {
            if (found[0]) {
                // a solution has been found, end immediately
                return;
            }

            int m = 9, n = 9;
            int i = index / n, j = index % n;
            if (index == m * n) {
                // find a feasible solution, trigger the base case
                found[0] = 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 (int 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[0]) {
                    // 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);
            }
        }

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

    new Solver().backtrack(0);
}

cpp

// The game panel only supports submitting JavaScript code
// The code in other languages is only for understanding

#include <vector>

// Assume BoardHandler is an interface class
class BoardHandler {
public:
    virtual int get(int i, int j) = 0;
    virtual void set(int i, int j, int value) = 0;
    virtual bool isEditable(int i, int j) = 0;
};

void solveSudoku(BoardHandler* boardHandler) {
    // will be true if a solution is found
    bool found = false;

    std::function<void(int)> backtrack = [&](int index) {
        if (found) {
            // a solution has been found, end immediately
            return;
        }

        const int m = 9, n = 9;
        int i = 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) != 0 && !boardHandler->isEditable(i, j)) {
            // if there is a preset number, we don't need to enumerate it
            backtrack(index + 1);
            return;
        }

        for (int 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, 0);
        }
    };

    auto isValid = [&](int r, int c, int num) -> bool {
        // check if there is a duplicate in the row
        for (int i = 0; i < 9; i++) {
            if (boardHandler->get(r, i) == num) return false;
        }
        
        // check if there is a duplicate in the column
        for (int 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
        int boxRow = (r / 3) * 3;
        int boxCol = (c / 3) * 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (boardHandler->get(boxRow + i, boxCol + j) == num) {
                    return false;
                }
            }
        }
        
        return true;
    };

    backtrack(0);
}

python

# The game panel only supports submitting JavaScript code
# The code in other languages is only for understanding

def solve_sudoku(board_handler):
    # will be true if a solution is found
    found = [False]

    def backtrack(index):
        if found[0]:
            # a solution has been found, end immediately
            return

        m, n = 9, 9
        i, j = index // n, index % n
        if index == m * n:
            # find a feasible solution, trigger the base case
            found[0] = True
            return

        if board_handler.get(i, j) is not None and not board_handler.is_editable(i, j):
            # if there is a preset number, we don't need to enumerate it
            backtrack(index + 1)
            return

        for c in range(1, 10):
            # pruning: if we encounter an invalid number, skip it
            if not is_valid(i, j, c):
                continue

            # make a choice
            board_handler.set(i, j, c)

            backtrack(index + 1)
            if found[0]:
                # if a solution is found, end immediately
                # don't cancel the choice, otherwise the value will be reset
                return

            # cancel the choice
            board_handler.set(i, j, None)

    def is_valid(r, c, num):
        # check if there is a duplicate in the row
        for i in range(9):
            if board_handler.get(r, i) == num:
                return False
        
        # check if there is a duplicate in the column
        for i in range(9):
            if board_handler.get(i, c) == num:
                return False
        
        # check if there is a duplicate in the 3 x 3 box
        box_row = (r // 3) * 3
        box_col = (c // 3) * 3
        for i in range(3):
            for j in range(3):
                if board_handler.get(box_row + i, box_col + j) == num:
                    return False
        
        return True

    backtrack(0)

// The game panel only supports submitting JavaScript code
// The code in other languages is only for understanding

// Assume BoardHandler is an interface
type BoardHandler interface {
    Get(i, j int) int
    Set(i, j, value int)
    IsEditable(i, j int) bool
}

func solveSudoku(boardHandler BoardHandler) {
    // will be true if a solution is found
    found := false

    var backtrack func(int)
    backtrack = func(index int) {
        if found {
            // a solution has been found, end immediately
            return
        }

        m, n := 9, 9
        i, j := index/n, index%n
        if index == m*n {
            // find a feasible solution, trigger the base case
            found = true
            return
        }

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

        for 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, 0)
        }
    }

    isValid := func(r, c, num int) bool {
        // check if there is a duplicate in the row
        for i := 0; i < 9; i++ {
            if boardHandler.Get(r, i) == num {
                return false
            }
        }
        
        // check if there is a duplicate in the column
        for 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
        boxRow := (r / 3) * 3
        boxCol := (c / 3) * 3
        for i := 0; i < 3; i++ {
            for j := 0; j < 3; j++ {
                if boardHandler.Get(boxRow+i, boxCol+j) == num {
                    return false
                }
            }
        }
        
        return true
    }

    backtrack(0)
}

javascript

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