时间戳

首页 > 解决方案 > 遍历有效数独的子框

python - 遍历有效数独的子框

问题描述

我正在研究Valid Sudoku - LeetCode 并且无法弄清楚为什么box_index = (i // 3 ) * 3 + j // 3能够遍历子框

确定 9x9 数独板是否有效。只有填充的单元格需要根据以下规则进行验证：

  1. 每行必须包含1-9不重复的数字。
  2. 每列必须包含1-9不重复的数字。
  3. 3x3网格的 9 个子框中的每一个都必须包含1-9不重复的数字。

在此处输入图像描述 有效的部分填充数独。

数独板可以部分填充，其中空单元格填充有字符'.'。

示例 1：

Input:
[
  ["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"]
]
Output: true

示例 2：

Input:
[
  ["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"]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being 
    modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

笔记：

  • 数独板（部分填充）可能是有效的，但不一定是可解的。
  • 只有填充的单元格需要根据上述规则进行验证。
  • 给定的棋盘只包含数字1-9和字符'.'。
  • 给定的电路板尺寸始终为9x9.

阅读一个聪明的解决方案

class Solution:
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        # init data
        rows = [{} for i in range(9)]
        columns = [{} for i in range(9)]
        boxes = [{} for i in range(9)]

        # validate a board
        for i in range(9):
            for j in range(9):
                num = board[i][j]
                if num != '.':
                    num = int(num)
                    box_index = (i // 3 ) * 3 + j // 3

                    # keep the current cell value
                    rows[i][num] = rows[i].get(num, 0) + 1
                    columns[j][num] = columns[j].get(num, 0) + 1
                    boxes[box_index][num] = boxes[box_index].get(num, 0) + 1

                    # check if this value has been already seen before
                    if rows[i][num] > 1 or columns[j][num] > 1 or boxes[box_index][num] > 1:
                        return False         
        return True

测试用例

class MyCase(unittest.TestCase):
   class MyCase(unittest.TestCase):
    def setUp(self):
        self.solution = Solution()

    def test_a(self):
        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"]
                ]
        check = self.solution.isValidSudoku(board)
        self.assertTrue(check)

    def test_b(self):
        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"]
                ]
        check = self.solution.isValidSudoku(board)
        self.assertFalse(check)

unittest.main() def setUp(self):
        self.solution = Solution()

    def test_a(self):
        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"]
                ]
        check = self.solution.isValidSudoku(board)
        self.assertTrue(check)

    def test_b(self):
        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"]
                ]
        check = self.solution.isValidSudoku(board)
        self.assertFalse(check)

unittest.main()

您能否提供任何提示，为什么box_index = (i // 3 ) * 3 + j // 3可以遍历子框？

标签： python

解决方案

您可以将整个框拆分为3*3子框，(i, j)属于索引为的子框，(i//3, j//3)这是一个3*3二维数组。如果我们想将其展平为一1*9维数组，则索引将为(i // 3 ) * 3 + j // 3.

带索引的子框：

|0|1|2|
|3|4|5|
|6|7|8|

如果您仍然感到困惑，您可以尝试一些示例，并弄清楚。

希望对您有所帮助，如果您还有其他问题，请发表评论。:)

推荐阅读