Valid Sudoku
Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules: [#36]
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 .
题意：给定一个数独数据列表，已知部分由数字组成以及待填的部分都由‘.’代替，要求检查数独的已知部分的数字是否有效。注意只求判断是否有效，不要求一定要有解。
我的解题思路：
第一步. 判断已知列表是否由9个子列表组成，每个子列表又都有9个元素；
第二步. 把已知列表的9行，9列，“九宫格”的9格，组建一个有27个元素的新列表；
第三步. 判断新列表中每个子列表筛掉“.”后，是否都只包含1-9且元素各不相同。
>>> val = [ ["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"], ["1","2",".",".","8",".",".","7","9"] ] >>> len(val)==9 and all([len(i)==9 for i in val]) True >>> Tmp = val # 给临时列表添加原列表的9行 >>> [Tmp.append(i) for i in list(zip(*val))] # 转置后给临时列表再添加9行，即原列表的9列 [None, None, None, None, None, None, None, None, None] >>> t = [[j[i:i+3] for i in range(0,9,3)] for j in val] >>> # 分拆原列表为九宫格 >>> [Tmp.append(t[i][j]+t[i+1][j]+t[i+2][j]) for j in range(3) for i in range(0,9,3)] [None, None, None, None, None, None, None, None, None] >>> # 把9个“宫格”都作为子列表，再次添加进临时列表Tmp中 >>> Tmp [['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'], ['1', '2', '.', '.', '8', '.', '.', '7', '9'], ['5', '6', '.', '8', '4', '7', '.', '.', '1'], ['3', '.', '9', '.', '.', '.', '6', '.', '2'], ['.', '.', '8', '.', '.', '.', '.', '.', '.'], ['.', '1', '.', '.', '8', '.', '.', '4', '.'], ['7', '9', '.', '6', '.', '2', '.', '1', '8'], ['.', '5', '.', '.', '3', '.', '.', '9', '.'], ['.', '.', '.', '.', '.', '.', '2', '.', '.'], ['.', '.', '6', '.', '.', '.', '8', '.', '7'], ['.', '.', '.', '3', '1', '6', '.', '5', '9'], ['5', '3', '.', '6', '.', '.', '.', '9', '8'], ['8', '.', '.', '4', '.', '.', '7', '.', '.'], ['.', '6', '.', '.', '.', '.', '1', '2', '.'], ['.', '7', '.', '1', '9', '5', '.', '.', '.'], ['.', '6', '.', '8', '.', '3', '.', '2', '.'], ['.', '.', '.', '4', '1', '9', '.', '8', '.'], ['.', '.', '.', '.', '.', '.', '.', '6', '.'], ['.', '.', '3', '.', '.', '1', '.', '.', '6'], ['2', '8', '.', '.', '.', '5', '.', '7', '9'] ] >>> >>> len(Tmp) 27 >>>
Sudoku Solver
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
Empty cells are indicated by the character '.' . [#37]
A sudoku puzzle...
...and its solution numbers marked in red.
Note:
The given board contain only digits 1-9 and the character '.' .
You may assume that the given Sudoku puzzle will have a single unique solution.
The given board size is always 9x9 .
