Блог

Я работаю над действительным Sudoku — LeetCode и не могу понять, почему box_index = (i // 3 ) * 3 j // 3 может проходить вложенный блок

Определите, допустима ли доска для судоку 9×9. Только заполненные ячейки должны быть проверены в соответствии со следующими правилами:

1. Каждая строка должна содержать цифры 1-9 без повторения.
2. Каждый столбец должен содержать цифры 1-9 без повторения.
3. Каждый из 9 3x3 вложенных блоков сетки должен содержать цифры 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 можно обойти вложенный блок?

Вы можете разделить весь блок на 3*3 вложенный блок, (i, j) который принадлежит вложенным блокам с индексом (i//3, j//3) , это 3*3 2d-массив. если мы хотим преобразовать его в 1*9 1d-массив, индекс будет (i // 3 ) * 3 j // 3 .

вложенные блоки с индексом:

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

Если вы все еще в замешательстве, вы можете попробовать несколько примеров и разобраться в этом.

Надеюсь, это поможет вам, и прокомментируйте, если у вас возникнут дополнительные вопросы. : )