【游戏】实现数独作弊器

labuladong原创约 883 字

按照要求实现 solveSudoku 方法，完成一个可运行的数独作弊器，通过暴力穷举一键解决任何数独问题。

完成代码后请点击「提交」按钮，让算法完成数独题目。完成后，可以点击「回放」按钮，查看算法暴力穷举的过程。

这道题比较简单，可以直接套用回溯算法实践：数独和 N 皇后问题的解法。参考代码如下：

java

// 游戏面板仅支持提交 JavaScript 代码
// 其他语言代码的作用是帮助大家理解算法逻辑

// 假设 BoardHandler 是一个接口
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) {
    // 标记是否已经找到可行解
    boolean[] found = {false};

    class Solver {
        void backtrack(int index) {
            if (found[0]) {
                // 已经找到一个可行解，立即结束
                return;
            }

            int m = 9, n = 9;
            int i = index / n, j = index % n;
            if (index == m * n) {
                // 找到一个可行解，触发 base case
                found[0] = true;
                return;
            }

            if (boardHandler.get(i, j) != null && !boardHandler.isEditable(i, j)) {
                // 如果有预设数字，不用我们穷举
                backtrack(index + 1);
                return;
            }

            for (int c = 1; c <= 9; c++) {
                // 剪枝：如果遇到不合法的数字，就跳过
                if (!isValid(i, j, c)) {
                    continue;
                }

                // 做选择
                boardHandler.set(i, j, c);

                backtrack(index + 1);
                if (found[0]) {
                    // 如果找到一个可行解，立即结束
                    // 不要撤销选择，否则值会被重置
                    return;
                }

                // 撤销选择
                boardHandler.set(i, j, null);
            }
        }

        boolean isValid(int r, int c, int num) {
            // 判断行是否存在重复
            for (int i = 0; i < 9; i++) {
                if (Objects.equals(boardHandler.get(r, i), num)) return false;
            }
            
            // 判断列是否存在重复
            for (int i = 0; i < 9; i++) {
                if (Objects.equals(boardHandler.get(i, c), num)) return false;
            }
            
            // 判断 3 x 3 方框是否存在重复
            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

// 游戏面板仅支持提交 JavaScript 代码
// 其他语言代码的作用是帮助大家理解算法逻辑

#include <vector>

// 假设 BoardHandler 是一个接口类
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) {
    // 标记是否已经找到可行解
    bool found = false;

    std::function<void(int)> backtrack = [&](int index) {
        if (found) {
            // 已经找到一个可行解，立即结束
            return;
        }

        const int m = 9, n = 9;
        int i = index / n, j = index % n;
        if (index == m * n) {
            // 找到一个可行解，触发 base case
            found = true;
            return;
        }

        if (boardHandler->get(i, j) != 0 && !boardHandler->isEditable(i, j)) {
            // 如果有预设数字，不用我们穷举
            backtrack(index + 1);
            return;
        }

        for (int c = 1; c <= 9; c++) {
            // 剪枝：如果遇到不合法的数字，就跳过
            if (!isValid(i, j, c)) {
                continue;
            }

            // 做选择
            boardHandler->set(i, j, c);

            backtrack(index + 1);
            if (found) {
                // 如果找到一个可行解，立即结束
                // 不要撤销选择，否则值会被重置
                return;
            }

            // 撤销选择
            boardHandler->set(i, j, 0);
        }
    };

    auto isValid = [&](int r, int c, int num) -> bool {
        // 判断行是否存在重复
        for (int i = 0; i < 9; i++) {
            if (boardHandler->get(r, i) == num) return false;
        }
        
        // 判断列是否存在重复
        for (int i = 0; i < 9; i++) {
            if (boardHandler->get(i, c) == num) return false;
        }
        
        // 判断 3 x 3 方框是否存在重复
        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

# 游戏面板仅支持提交 JavaScript 代码
# 其他语言代码的作用是帮助大家理解算法逻辑

def solve_sudoku(board_handler):
    # 标记是否已经找到可行解
    found = [False]

    def backtrack(index):
        if found[0]:
            # 已经找到一个可行解，立即结束
            return

        m, n = 9, 9
        i, j = index // n, index % n
        if index == m * n:
            # 找到一个可行解，触发 base case
            found[0] = True
            return

        if board_handler.get(i, j) is not None and not board_handler.is_editable(i, j):
            # 如果有预设数字，不用我们穷举
            backtrack(index + 1)
            return

        for c in range(1, 10):
            # 剪枝：如果遇到不合法的数字，就跳过
            if not is_valid(i, j, c):
                continue

            # 做选择
            board_handler.set(i, j, c)

            backtrack(index + 1)
            if found[0]:
                # 如果找到一个可行解，立即结束
                # 不要撤销选择，否则值会被重置
                return

            # 撤销选择
            board_handler.set(i, j, None)

    def is_valid(r, c, num):
        # 判断行是否存在重复
        for i in range(9):
            if board_handler.get(r, i) == num:
                return False
        
        # 判断列是否存在重复
        for i in range(9):
            if board_handler.get(i, c) == num:
                return False
        
        # 判断 3 x 3 方框是否存在重复
        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)

// 游戏面板仅支持提交 JavaScript 代码
// 其他语言代码的作用是帮助大家理解算法逻辑

// 假设 BoardHandler 是一个接口
type BoardHandler interface {
    Get(i, j int) int
    Set(i, j, value int)
    IsEditable(i, j int) bool
}

func solveSudoku(boardHandler BoardHandler) {
    // 标记是否已经找到可行解
    found := false

    var backtrack func(int)
    backtrack = func(index int) {
        if found {
            // 已经找到一个可行解，立即结束
            return
        }

        m, n := 9, 9
        i, j := index/n, index%n
        if index == m*n {
            // 找到一个可行解，触发 base case
            found = true
            return
        }

        if boardHandler.Get(i, j) != 0 && !boardHandler.IsEditable(i, j) {
            // 如果有预设数字，不用我们穷举
            backtrack(index + 1)
            return
        }

        for c := 1; c <= 9; c++ {
            // 剪枝：如果遇到不合法的数字，就跳过
            if !isValid(i, j, c) {
                continue
            }

            // 做选择
            boardHandler.Set(i, j, c)

            backtrack(index + 1)
            if found {
                // 如果找到一个可行解，立即结束
                // 不要撤销选择，否则值会被重置
                return
            }

            // 撤销选择
            boardHandler.Set(i, j, 0)
        }
    }

    isValid := func(r, c, num int) bool {
        // 判断行是否存在重复
        for i := 0; i < 9; i++ {
            if boardHandler.Get(r, i) == num {
                return false
            }
        }
        
        // 判断列是否存在重复
        for i := 0; i < 9; i++ {
            if boardHandler.Get(i, c) == num {
                return false
            }
        }
        
        // 判断 3 x 3 方框是否存在重复
        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) {
    // 标记是否已经找到可行解
    let found = false;

    function backtrack(index) {
        if (found) {
            // 已经找到一个可行解，立即结束
            return;
        }

        const m = 9, n = 9;
        const i = Math.floor(index / n), j = index % n;
        if (index === m * n) {
            // 找到一个可行解，触发 base case
            found = true;
            return;
        }

        if (boardHandler.get(i, j) !== null && !boardHandler.isEditable(i, j)) {
            // 如果有预设数字，不用我们穷举
            backtrack(index + 1);
            return;
        }

        for (let c = 1; c <= 9; c++) {
            // 剪枝：如果遇到不合法的数字，就跳过
            if (!isValid(i, j, c)) {
                continue;
            }

            // 做选择
            boardHandler.set(i, j, c);

            backtrack(index + 1);
            if (found) {
                // 如果找到一个可行解，立即结束
                // 不要撤销选择，否则值会被重置
                return;
            }

            // 撤销选择
            boardHandler.set(i, j, null);
        }
    }

    function isValid(r, c, num) {
        // 判断行是否存在重复
        for (let i = 0; i < 9; i++) {
            if (boardHandler.get(r, i) === num) return false;
        }
        
        // 判断列是否存在重复
        for (let i = 0; i < 9; i++) {
            if (boardHandler.get(i, c) === num) return false;
        }
        
        // 判断 3 x 3 方框是否存在重复
        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);
}