解数独（Sudoku）

MrHe··5 min read

别小看这玩意儿，好像就是填格子，但里面的门道可不少。一个题，能玩出好几种花样，从新手小白到算法老鸟，都能在里面找到自己的乐趣和挑战。今天，我就带你走一遍我的心路历程，看看怎么从最笨的方法，一步步优化到让面试官都眼前一亮的程度。

题目要求很简单：给你一个9x9的数独棋盘，里面有些数字已经填好了，有些是空的（用 . 表示），让你把空的地方填满，让整个数独成立。

规则大家都懂：

  1. 每一行，数字1-9都得出现一次，不能重复。

  2. 每一列，数字1-9都得出现一次，不能重复。

  3. 每一个3x3的小九宫格里，数字1-9也得出现一次，不能重复。

解法一：无脑爆搜，暴力递归走起！

拿到这种要在二维矩阵里填东西，还得满足一堆限制条件的题，我脑子里第一个蹦出来的词就是“递归”、“回溯”。这思路最直观，最符合人的思维。

咋想的呢？

很简单，咱就模拟人肉填数独的过程。从左上角第一个格子 (0, 0) 开始，一个一个往后走。

  • 如果这个格子已经有数了，那好，不用我管，直接去看下一个格子。

  • 如果这个格子是空的，机会来了！我从1到9挨个试。

    • 比如我先试填个1。填完之后，我得检查一下，填1合不合法？也就是当前行、当前列、当前3x3小方块里，是不是已经有1了。

    • 如果合法，太棒了！我就当它暂时就是1了，然后继续去處理下一个格子（递归调用）。如果后面的格子一路绿灯，最后都填完了，说明我这条路走对了，解出来了！

    • 如果填1不合法，或者填了1之后，后面的路走不通（递归返回了false），那说明1不行。咋办？回溯啊！把刚才填的1擦掉，恢复现场（变回.），然后试试填2。

    • 如果1到9都试完了，发现哪个数字放进去，后面的路都走不通，那就说明之前的决策有问题。这层递归就得返回false，告诉上一层：“你给我的这个盘面，我搞不定，你换个别的数吧”。

这就是最纯粹的回溯思想。写成代码，大概是这么个结构：

public void solveSudoku(char[][] board) {
    if (board == null || board.length != 9 || board[0].length != 9) {
        return;
    }
    backtrack(board, 0, 0);
}

private boolean backtrack(char[][] board, int row, int col) {
    // base case: 如果行号走到头了，说明整个棋盘都填完了
    if (row == 9) {
        return true;
    }

    // 计算下一个要处理的格子坐标
    int nextRow = col == 8 ? row + 1 : row;
    int nextCol = col == 8 ? 0 : col + 1;

    // 如果当前格子已经有数字了，直接去处理下一个
    if (board[row][col] != '.') {
        return backtrack(board, nextRow, nextCol);
    }

    // 如果是空格，开始尝试填1-9
    for (char num = '1'; num <= '9'; num++) {
        if (isValid(board, row, col, num)) {
            board[row][col] = num; // 做出选择

            // 深入下一层递归
            if (backtrack(board, nextRow, nextCol)) {
                return true; // 如果下一层成功了，直接返回true
            }

            // 回溯，撤销选择
            board[row][col] = '.';
        }
    }

    // 1-9都试完了还不行，说明这条路走不通
    return false;
}

// 检查在(row, col)位置放num是否合法
private boolean isValid(char[][] board, int row, int col, char num) {
    // 检查行
    for (int i = 0; i < 9; i++) {
        if (board[row][i] == num) {
            return false;
        }
    }

    // 检查列
    for (int i = 0; i < 9; i++) {
        if (board[i][col] == num) {
            return false;
        }
    }

    // 检查3x3小方块
    int startRow = (row / 3) * 3;
    int startCol = (col / 3) * 3;
    for (int i = startRow; i < startRow + 3; i++) {
        for (int j = startCol; j < startCol + 3; j++) {
            if (board[i][j] == num) {
                return false;
            }
        }
    }

    return true;
}

评价一下： 这个解法，逻辑清晰，代码好懂。但性能嘛...你懂的。瓶颈就在 isValid 这个函数。每次我要尝试填一个数，都要把整行、整列、整个小方块扫一遍。递归深度又那么深，这重复计算量可就大了去了。面试时写出这个，算及格，但想拿高分，还得继续。

解法二：空间换时间，加个状态记录

暴力解法慢在哪？慢在信息不流通。每次都得重新去盘面里找，这一行用过啥数了？这一列呢？这个小方块呢？

那咱能不能提前把这些信息存起来？当然可以！这就是典型的空间换时间思想。

我们可以用几个二维数组来记录状态：

  • boolean[][] rowUsed = new boolean[9][10]; rowUsed[i][j] 表示第 i 行是否已经用过数字 j。

  • boolean[][] colUsed = new boolean[9][10]; colUsed[i][j] 表示第 i 列是否已经用过数字 j。

  • boolean[][] boxUsed = new boolean[9][10]; boxUsed[i][j] 表示第 i 个小方块是否已经用过数字 j。

小方块的编号怎么算？从左到右，从上到下，可以给9个小方块编个号0-8。一个格子 (row, col) 所在的小方块编号就是 (row / 3) * 3 + (col / 3)。

有了这三个状态数组，isValid 的检查就从 O(N) 变成了 O(1)！

改造思路：

  1. 初始化：在递归开始前，先遍历一遍整个棋盘。把那些已经填好的数字，在我们的 rowUsed, colUsed, boxUsed 数组里做好标记。

  2. 递归过程：

    • 当我要在 (row, col) 位置尝试填数字 num 的时候，不再傻乎乎地去遍历棋盘了。

    • 直接查表：if (!rowUsed[row][num] && !colUsed[col][num] && !boxUsed[boxId][num])。如果都没用过，那这个数就能填！

    • 做选择：填上数字后，别忘了同步更新我们的状态数组，把对应的位置都设为 true。

    • 撤销选择 (回溯)：如果后面的路走不通，要回溯。不仅要把棋盘上的数字擦掉，更重要的是，要把我们刚才在状态数组里做的标记也给还原了，设回 false。

代码就变成了这样：

// 状态数组，作为成员变量
boolean[][] rowUsed = new boolean[9][10];
boolean[][] colUsed = new boolean[9][10];
boolean[][] boxUsed = new boolean[9][10];

public void solveSudoku2(char[][] board) {
    if (board == null || board.length != 9 || board[0].length != 9) {
        return;
    }

    // 1. 初始化状态数组
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] != '.') {
                int num = board[i][j] - '0';
                int boxId = (i / 3) * 3 + (j / 3);
                rowUsed[i][num] = true;
                colUsed[j][num] = true;
                boxUsed[boxId][num] = true;
            }
        }
    }

    backtrack2(board, 0, 0);
}

private boolean backtrack2(char[][] board, int row, int col) {
    if (row == 9) {
        return true;
    }

    int nextRow = col == 8 ? row + 1 : row;
    int nextCol = col == 8 ? 0 : col + 1;

    if (board[row][col] != '.') {
        return backtrack2(board, nextRow, nextCol);
    }

    for (int num = 1; num <= 9; num++) {
        int boxId = (row / 3) * 3 + (col / 3);

        // O(1) 检查合法性
        if (!rowUsed[row][num] && !colUsed[col][num] && !boxUsed[boxId][num]) {
            // 做选择 + 更新状态
            board[row][col] = (char) ('0' + num);
            rowUsed[row][num] = true;
            colUsed[col][num] = true;
            boxUsed[boxId][num] = true;

            if (backtrack2(board, nextRow, nextCol)) {
                return true;
            }

            // 回溯 + 恢复状态
            board[row][col] = '.';
            rowUsed[row][num] = false;
            colUsed[col][num] = false;
            boxUsed[boxId][num] = false;
        }
    }

    return false;
}

评价一下： 这个版本比第一个强太多了。通过引入额外的空间记录状态，把每次决策前的判断成本降到了最低。执行效率上了一个大台阶。面试的时候能写到这一步，基本上已经很不错了，说明你懂的用空间换时间的优化思想。

解法三：位运算，秀出你的基本功！

用 boolean[9][10] 感觉还是有点笨重。每一行/列/块，我们只是想记录9个数字（1-9）到底用没用过，这不就是一个典型的集合嘛！一个只有9个元素的集合，用布尔数组来表示，其实有点浪费。

这时候，就该位运算登场了！

一个int类型有32位，别说存9个状态了，存30个都绰绰有余。咱们可以用一个int的低9位（第0位到第8位）来分别代表数字1到9。

  • 比如，第 i 位是 1，就代表数字 i+1 已经用过了。

  • 第 i 位是 0，就代表数字 i+1 还没用过。

这样，我们只需要三个一维数组就够了：

  • int[] rowMask = new int[9];

  • int[] colMask = new int[9];

  • int[] boxMask = new int[9];

位运算怎么操作？

  • 标记数字 num 已使用：mask |= (1 << (num - 1))。比如要标记数字5，就是把第4位置为1。

  • 检查数字 num 是否已使用： (mask & (1 << (num - 1))) == 0。如果结果是0，说明那一位是0，没用过。

  • 取消标记（回溯）： mask &= ~(1 << (num - 1))。把那一位重新变回0。

代码整体结构和解法二一模一样，就是把对布尔数组的操作，换成对整数的位运算操作。

// 位运算版本状态记录
int[] rowMask = new int[9];
int[] colMask = new int[9];
int[] boxMask = new int[9];

public void solveSudoku3(char[][] board) {
    if (board == null || board.length != 9 || board[0].length != 9) {
        return;
    }

    // 1. 初始化状态
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] != '.') {
                int num = board[i][j] - '0';
                int boxId = (i / 3) * 3 + (j / 3);
                int bit = 1 << (num - 1);
                rowMask[i] |= bit;
                colMask[j] |= bit;
                boxMask[boxId] |= bit;
            }
        }
    }

    backtrack3(board, 0, 0);
}

private boolean backtrack3(char[][] board, int row, int col) {
    if (row == 9) return true;

    int nextRow = col == 8 ? row + 1 : row;
    int nextCol = col == 8 ? 0 : col + 1;

    if (board[row][col] != '.') {
        return backtrack3(board, nextRow, nextCol);
    }

    for (int num = 1; num <= 9; num++) {
        int boxId = (row / 3) * 3 + (col / 3);
        int bit = 1 << (num - 1);

        // O(1) 检查合法性
        if ((rowMask[row] & bit) == 0 && 
            (colMask[col] & bit) == 0 && 
            (boxMask[boxId] & bit) == 0) {

            // 做选择 + 更新状态
            board[row][col] = (char)('0' + num);
            rowMask[row] |= bit;
            colMask[col] |= bit;
            boxMask[boxId] |= bit;

            if (backtrack3(board, nextRow, nextCol)) {
                return true;
            }

            // 回溯 + 恢复状态
            board[row][col] = '.';
            rowMask[row] &= ~bit;
            colMask[col] &= ~bit;
            boxMask[boxId] &= ~bit;
        }
    }

    return false;
}

评价一下： 这个解法在时间复杂度上和解法二是一样的，都是 O(1) 的判断。但是空间上更优，而且代码看起来B格满满，充分展现了你扎实的计算机基础和对位运算的熟练掌握。在性能上，位运算通常会比数组访问更快一点点（虽然在现代JVM上这点差异可能微不足道），但它代表的是一种更极致、更底层的优化思路。

总结

  1. 暴力回溯：最直观，但有大量重复计算，性能差。

  2. 数组状态记录：用空间换时间，把判断耗时从 O(N) 降到 O(1)，性能大幅提升。

  3. 位运算优化：解法二基础上，用更紧凑、更高效的方式来存储和操作状态，是压榨性能和空间的终极骚操作。

  • #交互