본문 바로가기

DataStructure/Array

Valid Sudoku

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.


A partially filled sudoku which is valid.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Example 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

Example 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.

Note:

  • A Sudoku board (partially filled) could be valid but is not necessarily solvable.
  • Only the filled cells need to be validated according to the mentioned rules.
  • The given board contain only digits 1-9 and the character '.'.
  • The given board size is always 9x9.

My Solution:
class Solution:
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
for i in range(9):
rows_dict = dict()
columns_dict = dict()
for j in range(9):
if board[i][j] != ".":
if board[i][j] in rows_dict:
return False

rows_dict[board[i][j]] = board[i][j]

if board[j][i] != ".":
if board[j][i] in columns_dict:
print(board[j][i], columns_dict)
return False

columns_dict[board[j][i]] = board[j][i]

for i in range(9):
square_dict = dict()
for j in range(3):
for k in range(3):
first = i // 3 * 3 + j
second = (i % 3) * 3 + k
print(first, second)
if board[first][second] != ".":
if board[first][second] in square_dict:
return False

square_dict[board[first][second]] = board[first][second]

return True


'DataStructure > Array' 카테고리의 다른 글

Rotate Image  (0) 2018.10.31
Two Sum  (0) 2018.10.29
Move Zeroes  (0) 2018.10.29
Plus One  (0) 2018.10.29
Intersection of Two Arrays II  (0) 2018.10.29