89 lines
2.4 KiB
Markdown
89 lines
2.4 KiB
Markdown
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
|
||
]
|
||
|