N-Queens II

Q: Độ phức tạp thời gian của N-Queens II là bao nhiêu?

Thuật toán quay lui có độ phức tạp bị chặn bởi O(n!) : hàng đầu tiên có n lựa chọn, hàng tiếp theo có nhiều nhất n-1 lựa chọn, và cứ tiếp tục như vậy. Việc cắt tỉa giúp giảm đáng kể số thao tác thực tế, xuống còn 856,189 bàn cờ chưa hoàn chỉnh với n = 12 . Độ phức tạp không gian là O(n) .

KhóQuay lui

+10

Một quân hậu tấn công mọi ô trên cùng hàng, cùng cột và cả hai đường chéo của nó, dù ở xa đến đâu. Cho một số nguyên n, hãy trả về số cách đặt n quân hậu trên bàn cờ n × n sao cho không có hai quân hậu nào tấn công lẫn nhau.

Các bàn cờ khác nhau ở bất kỳ ô nào đều được tính riêng, kể cả các bàn cờ đối xứng gương.

Hàm

totalNQueens(n: integer) → integer

ninteger: kích thước bàn cờ và số lượng quân hậu
Trả vềinteger: số cách đặt các quân hậu sao cho không quân nào tấn công quân nào

Ràng buộc

1 ≤ n ≤ 12
Đáp án với n = 12 là 14,200, nên giá trị này nằm trong phạm vi của một số nguyên (integer) 32 bit.

Ví dụ

Đầu vào: n = 4
Đầu ra: 2
Giải thích: Ghi lại cột có quân hậu của mỗi hàng từ trên xuống dưới, ta có các bàn cờ 1, 3, 0, 2 và 2, 0, 3, 1: chúng là ảnh đối xứng của nhau, nhưng vẫn được tính là hai cách. Mọi lựa chọn khác đều đặt hai quân hậu cùng cột hoặc cùng đường chéo.

Câu hỏi mở rộng

Bạn có thể chỉ đếm những bàn cờ vẫn khác nhau sau khi xoay và lật bàn cờ không? Với n = 8, 92 bàn cờ được chia thành 12 nhóm như vậy.

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

Hai quân hậu trên cùng một hàng luôn tấn công nhau, vì vậy mỗi hàng trên bàn cờ chỉ có một quân hậu: có n^n danh sách, khoảng 8.9 × 10^12 với n = 12. Thay vào đó, hãy xây dựng bàn cờ theo từng hàng, loại bỏ bàn cờ chưa hoàn chỉnh ngay khi một quân hậu bị tấn công, đồng thời đánh dấu các cột và đường chéo đã bị chiếm để kiểm tra một ô chỉ cần ba lần tra cứu.

Thử mọi vị trí, đặt một quân hậu ở mỗi hàng

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Biểu diễn một cách sắp xếp dưới dạng danh sách cols, trong đó mỗi hàng ghi cột của quân hậu, rồi duyệt qua tất cả n^n danh sách như một công tơ mét. Các quân hậu ở hàng i < j tấn công nhau khi cols[i] == cols[j] hoặc |cols[i] - cols[j]| == j - i, vì đường chéo dịch chuyển một cột mỗi hàng. Mỗi danh sách được kiểm tra đúng một lần, nên không có bàn cờ nào bị bỏ sót hoặc đếm hai lần.

Không có gì khiến quá trình dừng sớm: dù hai hàng đầu tiên xung đột, vẫn còn n^(n-2) danh sách. Với n = 8, có 16,777,216 danh sách cho 92 bàn cờ; với n = 12, có 8.9 × 10^12 danh sách, mất khoảng 2.5 giờ nếu mỗi danh sách mất một nano giây.

Thuật toán

Bắt đầu với cols đều bằng 0.
Tăng biến đếm lên 1 nếu không có cặp hàng nào i < j thỏa mãn cols[i] == cols[j] hoặc |cols[i] - cols[j]| == j - i.
Tăng như đồng hồ công-tơ-mét: bắt đầu từ hàng cuối cùng trở lên, đặt lại mỗi phần tử bằng n-1 thành 0, rồi tăng phần tử đầu tiên nhỏ hơn n-1 lên 1.
Dừng và trả về biến đếm khi mọi phần tử đều bằng n-1.

def totalNQueens(n):
    def is_valid(cols):
        # cols[r] is the column of the queen in row r, so rows never clash.
        for i in range(n):
            for j in range(i + 1, n):
                if cols[i] == cols[j] or abs(cols[i] - cols[j]) == j - i:
                    return False
        return True

    cols = [0] * n
    count = 0
    while True:
        if is_valid(cols):
            count += 1
        # Move to the next placement, like an odometer with n digits in base n.
        row = n - 1
        while row >= 0 and cols[row] == n - 1:
            cols[row] = 0
            row -= 1
        if row < 0:
            return count
        cols[row] += 1

Quay lui với các tập hợp cột và đường chéo

Ý tưởng

Đặt các quân hậu (queen) lần lượt theo từng hàng và kiểm tra từng ô khi đặt quân. Không có cách nào điền các hàng bên dưới để cứu một quân hậu đang bị tấn công, vì vậy hãy bỏ qua ô đó. Nếu quân hậu an toàn, hãy gọi đệ quy (recursion) cho hàng tiếp theo rồi gỡ quân hậu khi lời gọi trả về; khi đến hàng n, ta tính được một bàn cờ.

Chỉ có ba đường có thể tấn công ô (row, c): cột của ô đó, đường chéo /, nơi row + c không đổi, và đường chéo \, nơi row - c không đổi (cộng n-1 để đánh chỉ số từ 0). Các mảng đánh dấu (flag arrays) cols, diag và anti biến phép kiểm tra an toàn thành ba lần tra cứu. Mỗi đường chỉ chứa tối đa một quân hậu, nên xóa các cờ khi lời gọi trả về sẽ khôi phục chính xác các mảng.

Hàng k có tối đa n - k cột, nên độ phức tạp thời gian của phép tìm kiếm là O(n!), với độ phức tạp không gian là O(n).

Thuật toán

Tạo các mảng cờ cols có kích thước n và diag, anti có kích thước 2n-1, tất cả đều tắt.
place(row): nếu row == n, trả về 1.
Với mỗi cột c, bỏ qua cột đó nếu cols[c], diag[row + c] hoặc anti[row - c + n - 1] đang bật.
Nếu không, bật ba cờ, cộng place(row + 1) vào tổng rồi tắt chúng.
Trả về tổng. Đáp án là place(0).

def totalNQueens(n):
    cols = [False] * n             # cols[c]: column c holds a queen
    diag = [False] * (2 * n - 1)   # diag[r + c]: that / diagonal holds a queen
    anti = [False] * (2 * n - 1)   # anti[r - c + n - 1]: that \ diagonal holds a queen

    def place(row):
        if row == n:
            return 1  # a queen in every row: one complete board
        count = 0
        for c in range(n):
            if cols[c] or diag[row + c] or anti[row - c + n - 1]:
                continue  # attacked: three lookups, no scan of the board
            cols[c] = diag[row + c] = anti[row - c + n - 1] = True
            count += place(row + 1)
            cols[c] = diag[row + c] = anti[row - c + n - 1] = False  # take it back
        return count

    return place(0)

Quay lui với mặt nạ bit

Ý tưởng

Phép tìm kiếm bằng cờ vẫn kiểm tra cả n cột của mỗi hàng; mặt nạ bit nhảy thẳng đến các cột còn trống. Bit c là cột c của hàng đang được điền: cols lưu các cột đã bị chiếm, còn left và right lưu các ô bị tấn công dọc theo từng đường chéo. Khi đó, free = ~(cols | left | right) & full, trong đó full là n bit thấp, và free & -free là ô trống có chỉ số thấp nhất. Xuống một hàng, cột vẫn bị chiếm và các đòn tấn công trên từng đường chéo dịch sang một cột.

Với n = 4 và quân hậu đầu tiên ở bit = 0010, hàng 1 có free = 1000: cột 3, được tìm thấy mà không cần kiểm tra các cột khác. Với n = 12, 856,188 bước lặp thay cho 10,103,868 lần kiểm tra ô. Code R tạo cùng lúc cả một hàng gồm các bàn cờ chưa hoàn chỉnh thay vì dùng đệ quy.

Thuật toán

Gán full = (1 << n) - 1.
count(cols, left, right): nếu cols == full, trả về 1.
Tính free = ~(cols | left | right) & full.
Khi free khác 0, lấy bit = free & -free, xóa nó khỏi free và cộng count(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1) vào tổng.
Trả về tổng. Đáp án là count(0, 0, 0).

def totalNQueens(n):
    full = (1 << n) - 1  # bit c stands for column c of the current row

    def count(cols, left, right):
        # cols: columns taken. left, right: squares of this row hit along a diagonal.
        if cols == full:
            return 1  # every column used: n queens placed
        total = 0
        free = full & ~(cols | left | right)
        while free:
            bit = free & -free  # the lowest free square
            free -= bit
            # Moving down a row shifts each diagonal attack one column over.
            total += count(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1)
        return total

    return count(0, 0, 0)

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

Lấy chỉ số của anti bằng row - c mà không cộng thêm n-1. Java sẽ phát sinh lỗi, C đọc ngoài mảng, còn anti[-2] trong Python âm thầm đọc cờ của một đường chéo khác.
Khai báo mảng đường chéo có kích thước n thay vì 2n-1. row + c có thể đạt đến 2n-2.
Không xóa các cờ sau lời gọi đệ quy. Các nhánh sau sẽ thấy những quân hậu đã bị gỡ, khiến số lượng giảm.
Bỏ & full khỏi free. ~x bật các bit phía trên cột n-1, khiến vòng lặp chọn các ô ngoài bàn cờ; trong Python hoặc Ruby, free trở thành số âm và vòng lặp không bao giờ kết thúc.

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

Độ phức tạp thời gian của N-Queens II là bao nhiêu?

Thuật toán quay lui có độ phức tạp bị chặn bởi O(n!): hàng đầu tiên có n lựa chọn, hàng tiếp theo có nhiều nhất n-1 lựa chọn, và cứ tiếp tục như vậy. Việc cắt tỉa giúp giảm đáng kể số thao tác thực tế, xuống còn 856,189 bàn cờ chưa hoàn chỉnh với n = 12. Độ phức tạp không gian là O(n).

N-Queens và N-Queens II khác nhau như thế nào?

N-Queens trả về mọi bàn cờ, được hiển thị thành các hàng văn bản; N-Queens II chỉ trả về số lượng bàn cờ. Cách tìm kiếm giống nhau, nhưng việc đếm không lưu bàn cờ nào, phù hợp với phiên bản dùng mặt nạ bit.

Bạn có thể dùng tính đối xứng để giải N-Queens II nhanh hơn không?

Lật đối xứng bàn cờ từ trái sang phải sẽ tạo ra một bàn cờ hợp lệ khác, vì vậy hãy đếm các bàn cờ có quân hậu đầu tiên ở các cột từ 0 đến n/2 - 1 rồi nhân đôi kết quả. Với n lẻ, hãy cộng thêm một lần số bàn cờ có quân hậu đầu tiên ở cột giữa.

def totalNQueens(n):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Đối số

n = 4

Đầu ra mong đợi

N-Queens II

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Thử mọi vị trí, đặt một quân hậu ở mỗi hàng

Quay lui với các tập hợp cột và đường chéo

Quay lui với mặt nạ bit

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

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

Bài tập tương tự