Permalink
Cannot retrieve contributors at this time
Name already in use
A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
LeetCode/valid-sudoku
Go to fileThis commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
100 lines (87 sloc)
3.31 KB
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules: | |
Each row must contain the digits 1-9 without repetition. | |
Each column must contain the digits 1-9 without repetition. | |
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 code: | |
class Solution: | |
def isValidSudoku(self, board): | |
""" | |
:type board: List[List[str]] | |
:rtype: bool | |
""" | |
#First line check | |
for i in range(len(board)): | |
tmp_list=board[i] | |
record=[] | |
for j in range(len(board)): | |
if tmp_list[j]!='.': | |
if tmp_list[j] not in record: | |
record.append(tmp_list[j]) | |
else: | |
return False | |
#2nd row check | |
for i in range(9): | |
globals()['checklist%d'%i]=[] | |
for i in range(len(board)): | |
tmp_list=board[i] | |
for j in range(len(board)): | |
if tmp_list[j]!='.': | |
if tmp_list[j] not in globals()['checklist%d'%j]: | |
globals()['checklist%s'%j].append(tmp_list[j]) | |
else: | |
return False | |
print('executing final check') | |
#Do a small cube check | |
for i in range(3): | |
for j in range(3): | |
record=[] | |
start1=i*3 | |
start2=j*3 | |
for k in range(3): | |
tmp_list=board[start1+k] | |
for l in range(3): | |
if tmp_list[start2+l]!='.': | |
if tmp_list[start2+l] not in record: | |
record.append(tmp_list[start2+l]) | |
else: | |
return False | |
return True | |
Solution: | |
https://leetcode.com/problems/valid-sudoku |