面试经典算法题86-有效的数独

LeetCode.36

问题描述

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

• 一个有效的数独（部分已被填充）不一定是可解的。
• 只需要根据以上规则，验证已经填入的数字是否有效即可。
• 空白格用 '.' 表示。

示例 1：

输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true

示例 2：

输入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

思路

1. 行验证：使用一个二维布尔数组 rows，其中 rows[i][num] 表示第 i 行是否包含数字 num。
2. 列验证：使用一个二维布尔数组 cols，其中 cols[j][num] 表示第 j 列是否包含数字 num。
3. 3x3 宫验证：使用一个三维布尔数组 boxes，其中 boxes[k][num] 表示第 k 个 3x3 宫是否包含数字 num，其中 k = (i / 3) * 3 + j / 3。
4. 遍历验证：遍历整个数独矩阵，对于每一个非空格位置 board[i][j]，将其数字转为索引 num，然后检查并更新 rows[i][num]，cols[j][num]，boxes[k][num]。如果发现重复，则数独无效。

参考代码

C++

#include <iostream>
#include <vector>
using namespace std;

bool isValidSudoku(vector<vector<char>>& board) {
    // 定义行、列、和3x3小宫格的记录表
    bool rows[9][9] = {false};
    bool cols[9][9] = {false};
    bool boxes[9][9] = {false};

    // 遍历数独矩阵
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            if (board[i][j] != '.') {
                // 将字符转换为索引
                int num = board[i][j] - '1';
                // 计算3x3小宫格的索引
                int boxIndex = (i / 3) * 3 + j / 3;
                // 检查行、列、小宫格是否已经存在该数字
                if (rows[i][num] || cols[j][num] || boxes[boxIndex][num]) {
                    return false; // 数独无效
                }
                // 记录该数字已存在
                rows[i][num] = cols[j][num] = boxes[boxIndex][num] = true;
            }
        }
    }
    return true; // 数独有效
}

int main() {
    vector<vector<char>> board = {
        {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
        {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
        {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
        {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
        {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
        {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
        {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
        {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
        {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
    };

    if (isValidSudoku(board)) {
        cout << "数独有效" << endl;
    } else {
        cout << "数独无效" << endl;
    }

    return 0;
}

Java

public class ValidSudoku {
    public static boolean isValidSudoku(char[][] board) {
        // 定义行、列、和3x3小宫格的记录表
        boolean[][] rows = new boolean[9][9];
        boolean[][] cols = new boolean[9][9];
        boolean[][] boxes = new boolean[9][9];

        // 遍历数独矩阵
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    // 将字符转换为索引
                    int num = board[i][j] - '1';
                    // 计算3x3小宫格的索引
                    int boxIndex = (i / 3) * 3 + j / 3;
                    // 检查行、列、小宫格是否已经存在该数字
                    if (rows[i][num] || cols[j][num] || boxes[boxIndex][num]) {
                        return false; // 数独无效
                    }
                    // 记录该数字已存在
                    rows[i][num] = cols[j][num] = boxes[boxIndex][num] = true;
                }
            }
        }
        return true; // 数独有效
    }

    public static void main(String[] args) {
        char[][] board = {
            {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
            {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
            {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
            {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
            {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
            {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
            {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
            {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
            {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };

        if (isValidSudoku(board)) {
            System.out.println("数独有效");
        } else {
            System.out.println("数独无效");
        }
    }
}

Python

def isValidSudoku(board):
    # 定义行、列、和3x3小宫格的记录表
    rows = [[False] * 9 for _ in range(9)]
    cols = [[False] * 9 for _ in range(9)]
    boxes = [[False] * 9 for _ in range(9)]

    # 遍历数独矩阵
    for i in range(9):
        for j in range(9):
            if board[i][j] != '.':
                # 将字符转换为索引
                num = int(board[i][j]) - 1
                # 计算3x3小宫格的索引
                box_index = (i // 3) * 3 + j // 3
                # 检查行、列、小宫格是否已经存在该数字
                if rows[i][num] or cols[j][num] or boxes[box_index][num]:
                    return False  # 数独无效
                # 记录该数字已存在
                rows[i][num] = cols[j][num] = boxes[box_index][num] = True

    return True  # 数独有效

# 测试代码
if __name__ == "__main__":
    board = [
        ['5', '3', '.', '.', '7', '.', '.', '.', '.'],
        ['6', '.', '.', '1', '9', '5', '.', '.', '.'],
        ['.', '9', '8', '.', '.', '.', '.', '6', '.'],
        ['8', '.', '.', '.', '6', '.', '.', '.', '3'],
        ['4', '.', '.', '8', '.', '3', '.', '.', '1'],
        ['7', '.', '.', '.', '2', '.', '.', '.', '6'],
        ['.', '6', '.', '.', '.', '.', '2', '8', '.'],
        ['.', '.', '.', '4', '1', '9', '.', '.', '5'],
        ['.', '.', '.', '.', '8', '.', '.', '7', '9']
    ]

    if isValidSudoku(board):
        print("数独有效")
    else:
        print("数独无效")