Giả sử chúng ta có một lưới Sudoku 9 × 9. Chúng tôi phải kiểm tra xem điều đó có hợp lệ hay không. Chỉ các ô đã điền mới 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 số 9 (3−3) hộp con của lưới phải chứa các chữ số từ 1−9 mà không lặp lại.
Giả sử lưới Sudoku giống như -
Điều này hợp lệ.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
cho tôi trong phạm vi từ 0 đến 8
-
tạo một số từ điển trống có tên là row, col và block, row_cube:=3 * (i / 3) và col_cube:=3 * (i mod 3)
-
cho j trong phạm vi từ 0 đến 8
-
nếu bảng [i, j] không trống và bảng [i, j] liên tiếp, thì trả về false
-
row [board [i, j]]:=1
-
nếu board [j, i] không trống và board [j, i] in col, thì trả về false
-
col [board [j, i]]:=1
-
rc:=row_cube + j / 3 và cc:=col_cube + j mod 3
-
nếu bảng [rc, cc] trong khối và bảng [rc, cc] không trống, thì trả về false
-
khối [board [rc, cc]]:=1
-
-
-
trả về true
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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"]])) Đầu vào
[ ["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"]]
Đầu ra
True