Valid Sudoku

Trung bìnhBăm

+10

Bạn nhận được một bảng Sudoku 9 × 9 trong board, là một danh sách gồm 9 chuỗi, mỗi chuỗi có 9 ký tự, mỗi chuỗi tương ứng với một hàng. Mỗi ký tự là một chữ số từ 1 đến 9 hoặc . để biểu thị ô trống. Trả về true nếu không có chữ số nào xuất hiện hai lần trong cùng một hàng, cột hoặc ô vuông 3 × 3, và trả về false trong các trường hợp còn lại. Chỉ kiểm tra các ô đã điền: bảng không cần phải có lời giải.

Hàm

isValidSudoku(board: string-array) → boolean

boardstring-array: 9 chuỗi gồm 9 ký tự, mỗi chuỗi trên một hàng, các chữ số từ 1 đến 9 và dấu . biểu thị ô trống
Trả vềboolean: true nếu không có hàng, cột hoặc ô 3 × 3 nào lặp lại một chữ số, false nếu ngược lại

Ràng buộc

board.length == 9 và board[i].length == 9
board[i][j] là một chữ số từ 1 đến 9 hoặc .
Bàn cờ có thể không hoàn thành được; chỉ cần quan tâm đến các lần lặp giữa những ô đã điền.

Ví dụ

Đầu vào: board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]
Đầu ra: true
Giải thích: Hàng 4, nếu đếm từ 0, .74..89.3, có mỗi chữ số 7, 4, 8, 9 và 3 đúng một lần, và 26 nhóm còn lại cũng không có nhóm nào lặp lại chữ số.

Đầu vào: board = ["3.64.....", "258..9..1", "...8.2...", "...9...43", ".6.1..28.", "....87.65", "8......24", "3.......6", "6....45.8"]
Đầu ra: false
Giải thích: Cả hàng 0 và hàng 7 đều bắt đầu bằng 3, nên cột 0 có hai số 3. Chúng không nằm chung hàng hay ô nào, vì vậy chỉ kiểm tra cột mới phát hiện được điều này.

Đầu vào: board = ["987..36.5", "2.6.8..13", ".1.64.75.", "8..261..4", "16.97.3.8", "..9.5..6.", "7.....49.", "..48.....", "5.1.....7"]
Đầu ra: false
Giải thích: Số 5 ở hàng 0, cột 8 và số 5 ở hàng 2, cột 7 không nằm cùng hàng hay cùng cột, nhưng cả hai đều nằm trong ô vuông phía trên bên phải, nên đáp án là false.

Câu hỏi mở rộng

Bạn sẽ kiểm tra bảng 16 × 16 có các ô vuông 4 × 4 và các ký hiệu từ 1 đến 9 và từ A đến G như thế nào? Công thức tính ô vuông sẽ trở thành gì?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Mỗi chữ số thuộc về ba nhóm: hàng, cột và ô vuông 3 × 3. Có thể xác định chỉ số hàng và cột trực tiếp; còn ô vuông là nơi các bug ẩn náu. Đánh số các ô vuông từ 0 đến 8 bằng (r / 3) * 3 + c / 3, rồi duyệt qua 81 ô một lần để kiểm tra cả 27 nhóm.

Kiểm tra riêng từng hàng, cột và ô vuông

Ý tưởng

Quy tắc này xác định 27 nhóm: 9 hàng, 9 cột và 9 ô vuông. Gom chín ô của từng nhóm rồi tìm chữ số bị lặp, bỏ qua các dấu chấm. Bảng hợp lệ khi và chỉ khi không nhóm nào có chữ số bị lặp.

Mỗi chữ số có một cờ đánh dấu đã gặp để tìm chữ số lặp trong chín ô. Mỗi ô trong số 81 ô được đọc một lần cho từng nhóm trong ba nhóm của nó: 243 lần đọc, một lượng công việc cố định. Với bảng n × n, phương pháp tương tự có độ phức tạp O(n²).

Thuật toán

Với i từ 0 đến 8, thu thập hàng i, cột i và ô vuông i.
Ô vuông i có góc ở hàng 3 * (i / 3), cột 3 * (i % 3); ô k nằm thấp hơn k / 3 hàng và lệch phải k % 3 cột so với góc đó.
Duyệt từng nhóm với các cờ đã thấy được đặt lại, bỏ qua dấu chấm. Nếu một chữ số đã được đánh dấu, trả về false.
Sau khi duyệt đủ 27 nhóm, trả về true.

def has_repeat(cells):
    seen = set()
    for ch in cells:
        if ch == '.':
            continue
        if ch in seen:
            return True
        seen.add(ch)
    return False


def isValidSudoku(board):
    for r in range(9):
        if has_repeat(board[r][c] for c in range(9)):
            return False
    for c in range(9):
        if has_repeat(board[r][c] for r in range(9)):
            return False
    for top in (0, 3, 6):
        for left in (0, 3, 6):
            box = (board[top + i][left + j] for i in range(3) for j in range(3))
            if has_repeat(box):
                return False
    return True

Một lượt duyệt với bảng đã xem cho từng hàng, cột và ô

Ý tưởng

Kiểm tra từng ô một lần và đặt cả ba câu hỏi cùng lúc. Dùng ba bảng 9 × 9 để đánh dấu: seenRow[r][d] cho biết chữ số d+1 đã có trong hàng r, còn seenCol và seenBox hoạt động tương tự.

Ô (r, c) thuộc hộp (r / 3) * 3 + c / 3. Phần đầu xác định dải gồm ba hộp, còn c / 3 xác định hộp bên trong dải. Ô (4, 7) nằm trong hộp 1 * 3 + 2 = 5, hộp ở giữa bên phải.

Cờ đã bật nghĩa là chữ số bị lặp trong nhóm đó. Mỗi ô được đọc một lần và các bảng chứa 243 cờ: thời gian và bộ nhớ cố định ở đây, O(n²) trên bàn cờ n × n.

Thuật toán

Tạo seenRow, seenCol và seenBox, mỗi mảng có kích thước 9 × 9 và toàn bộ phần tử đều là false.
Với mỗi ô đã điền (r, c), gọi chữ số của ô đó trừ 1 là d và b = (r / 3) * 3 + c / 3.
Nếu seenRow[r][d], seenCol[c][d] hoặc seenBox[b][d] được đặt, hãy trả về false; nếu không, hãy đặt cả ba giá trị.
Sau ô cuối cùng, trả về true.

def isValidSudoku(board):
    # seen_row[r][d] is True once digit d + 1 appears in row r; same for columns and boxes.
    seen_row = [[False] * 9 for _ in range(9)]
    seen_col = [[False] * 9 for _ in range(9)]
    seen_box = [[False] * 9 for _ in range(9)]
    for r in range(9):
        for c in range(9):
            ch = board[r][c]
            if ch == '.':
                continue
            d = int(ch) - 1
            b = (r // 3) * 3 + c // 3
            if seen_row[r][d] or seen_col[c][d] or seen_box[b][d]:
                return False
            seen_row[r][d] = seen_col[c][d] = seen_box[b][d] = True
    return True

Lỗi thường gặp và trường hợp biên

Tính hộp bằng r / 3 + c / 3. Cách này chỉ cho kết quả từ 0 đến 4, nên (0, 3) và (3, 0) có cùng một số dù thuộc các hộp khác nhau, và hai số 7 ở đó sẽ bị báo là trùng lặp.
Chia bằng / trong JavaScript, Python 3 hoặc Lua, trong đó 4 / 3 bằng 1.33. Hãy làm tròn xuống.
Coi . là một giá trị. Một bảng trống, mỗi hàng có chín dấu chấm, vẫn hợp lệ.
Thử giải câu đố. Hàng 0 là 12345678., với số 9 nằm bên dưới ở cột 8, thì không thể hoàn thành, nhưng không có gì bị lặp lại: true.
Bỏ qua các hộp. Một lưới đầy đủ mà mỗi hàng là hàng phía trên dịch sang trái một vị trí sẽ không có số nào lặp lại trong hàng hoặc cột, nhưng mỗi hộp đều có số bị lặp.

Câu hỏi thường gặp3

Độ phức tạp thời gian của Valid Sudoku là bao nhiêu?

Bảng luôn có 81 ô, nên cả hai cách đều chạy trong thời gian O(1) và dùng O(1) bộ nhớ. Với Sudoku tổng quát kích thước n × n, bước kiểm tra một lượt đọc mỗi ô trong số n² ô đúng một lần và lưu giữ 3n² cờ: thời gian và bộ nhớ O(n²).

Bảng Sudoku hợp lệ có nhất thiết phải giải được không?

Không. Ở đây, hợp lệ chỉ có nghĩa là không có chữ số nào lặp lại trong cùng một hàng, cột hoặc ô 3 × 3 ở các ô đã điền. Bảng có thể vượt qua bước kiểm tra đó mà vẫn không có lời giải. Để xác định bảng có lời giải hay không, cần tìm kiếm bằng thuật toán như quay lui, đây là một bài toán khác.

Sudoku hợp lệ có thể được giải bằng mặt nạ bit không?

Có. Gán cho mỗi hàng, cột và ô vuông một số nguyên, trong đó bit d cho biết chữ số d+1 đã xuất hiện. Với một ô đã điền, nếu 1 << d thực hiện phép AND cho kết quả khác 0 với bất kỳ mặt nạ nào trong ba mặt nạ của ô đó, chữ số bị lặp lại; nếu không, hãy thực hiện phép OR với cả ba mặt nạ. Cách này dùng 27 số nguyên thay vì 243 cờ.

def isValidSudoku(board):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]

Đầu ra mong đợi

true