Giả sử chúng ta có một lưới Sudoku 9x9. Chúng ta phải kiểm tra xem lưới đó có hợp lệ hay không. Chỉ các ô đã điền cần được xác thực theo các quy tắc sau:
- Mỗi hàng phải chứa các chữ số từ 1-9 không lặp lại.
- Mỗi cột phải chứa các chữ số từ 1-9 không lặp lại.
- Mỗi trong 9 ô con 3x3 của lưới phải chứa các chữ số từ 1-9 không lặp lại.
Giả sử lưới Sudoku như sau:
Lưới này là hợp lệ.
Để giải quyết, chúng ta thực hiện các bước sau:
- với i từ 0 đến 8:
- tạo từ điển rỗng row, col, block; row_cube := 3 * (i // 3), col_cube := 3 * (i % 3)
- với j từ 0 đến 8:
- nếu board[i][j] không phải '.' VÀ board[i][j] trong row, trả về False
- row[board[i][j]] := 1
- nếu board[j][i] không phải '.' VÀ board[j][i] trong col, trả về False
- col[board[j][i]] := 1
- rc := row_cube + j//3, cc := col_cube + j%3
- nếu board[rc][cc] trong block VÀ board[rc][cc] không phải '.', trả về False
- block[board[rc][cc]] := 1
- trả về True
Ví dụ
class Solution(object):
def isValidSudoku(self, board):
for i in range(9):
row = {}
column = {}
block = {}
row_cube = 3 * (i // 3)
column_cube = 3 * (i % 3)
for j in range(9):
if board[i][j] != '.' and board[i][j] in row:
return False
row[board[i][j]] = 1
if board[j][i] != '.' and board[j][i] in column:
return False
column[board[j][i]] = 1
rc = row_cube + j // 3
cc = column_cube + j % 3
if board[rc][cc] in block and board[rc][cc] != '.':
return False
block[board[rc][cc]] = 1
return True
ob1 = Solution()
print(ob1.isValidSudoku([
["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"]
]))
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