36-有效的数独

题目

原题链接

给定一个数独，验证它是否是有效的。

只需要根据以下规则，验证已经填入的数字是否有效即可。

• 数字 1-9 在每一行只能出现一次。
• 数字 1-9 在每一列只能出现一次。
• 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
• 数独部分空格内已填入了数字，空白格用 '.' 表示。

解题思路

"有效的数独" 题目要求判断一个 9x9 的数独是否有效。数独的规则是每一行、每一列以及每一个 3x3 的小方格（9个小方格）内不能重复数字 1-9。有效的数独不需要是可解的，只需要当前填入的数字不违反上述规则。

解决这个问题的关键在于检查每一行、每一列以及每个 3x3 方格内是否有重复的数字。这可以通过使用哈希表来实现，以存储已经遇到的数字及其出现的位置。以下是具体步骤：

1. 创建哈希表：为每一行、每一列和每个 3x3 方格创建一个哈希表，用于跟踪出现过的数字。

2. 遍历数独：遍历数独的每一个单元格。

3. 检查规则：

   • 对于每个非空单元格，检查数字是否已经在相应的行、列或 3x3 方格的哈希表中。
   • 如果数字已存在，那么数独无效。
   • 否则，将数字添加到对应行、列和 3x3 方格的哈希表中。

4. 返回结果：如果所有单元格都遵循数独的规则，返回 true，表示数独有效；否则返回 false。

以下是使用 Go 语言实现的代码示例：

package main

import (
    "fmt"
)

func isValidSudoku(board [][]byte) bool {
    rows := make([]map[byte]bool, 9)
    cols := make([]map[byte]bool, 9)
    boxes := make([]map[byte]bool, 9)
    for i := 0; i < 9; i++ {
        rows[i] = make(map[byte]bool)
        cols[i] = make(map[byte]bool)
        boxes[i] = make(map[byte]bool)
    }

    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            num := board[i][j]
            if num != '.' {
                boxIndex := (i/3)*3 + j/3 // 3x3 方格的索引
                if rows[i][num] || cols[j][num] || boxes[boxIndex][num] {
                    return false
                }
                rows[i][num] = true
                cols[j][num] = true
                boxes[boxIndex][num] = true
            }
        }
    }
    return true
}

func main() {
    board := [][]byte{
        {'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'},
    }
    result := isValidSudoku(board)
    fmt.Println(result)
}

在这个实现中，isValidSudoku 函数接收一个表示数独的二维数组 board，并使用哈希表来检查是否有重复的数字。如果数独有效，它返回 true；否则返回 false。