2.4 KiB
You are given a a 9 x 9 Sudoku board board. A Sudoku board is valid if the following rules are followed:
Each row must contain the digits 1-9 without duplicates. Each column must contain the digits 1-9 without duplicates. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without duplicates. Return true if the Sudoku board is valid, otherwise return false
Note: A board does not need to be full or be solvable to be valid.
Example 1:
Input: board = [["1","2",".",".","3",".",".",".","."], ["4",".",".","5",".",".",".",".","."], [".","9","8",".",".",".",".",".","3"], ["5",".",".",".","6",".",".",".","4"], [".",".",".","8",".","3",".",".","5"], ["7",".",".",".","2",".",".",".","6"], [".",".",".",".",".",".","2",".","."], [".",".",".","4","1","9",".",".","8"], [".",".",".",".","8",".",".","7","9"]]
Output: true Example 2:
Input: board = [["1","2",".",".","3",".",".",".","."], ["4",".",".","5",".",".",".",".","."], [".","9","1",".",".",".",".",".","3"], ["5",".",".",".","6",".",".",".","4"], [".",".",".","8",".","3",".",".","5"], ["7",".",".",".","2",".",".",".","6"], [".",".",".",".",".",".","2",".","."], [".",".",".","4","1","9",".",".","8"], [".",".",".",".","8",".",".","7","9"]]
Output: false Explanation: There are two 1's in the top-left 3x3 sub-box.
Constraints:
board.length == 9 board[i].length == 9 board[i][j] is a digit 1-9 or '.'.
Решение
Пусть будет матрица 3х3 где будут храниться числа в каждом квадрате валидации, т.е.
sq = [
(), (), (),
(), (), (),
(), (), (),
]
Когда начнем проходить по двумерной матрице - будем смотреть на номер строк и остаток деления на три от длины проверяемого столбца, чтобы определять в какой квадрат писать
i // 3 [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2
]
j // 3 [ 0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2
0 0 0 1 1 1 2 2 2
0 0 0 1 1 1 2 2 2
0 0 0 1 1 1 2 2 2
0 0 0 1 1 1 2 2 2
0 0 0 1 1 1 2 2 2
0 0 0 1 1 1 2 2 2
]