N-Queens II

Q: Berapa kompleksitas waktu N-Queens II?

Backtracking dibatasi oleh O(n!) : baris pertama memiliki n pilihan, baris berikutnya paling banyak n-1 , dan seterusnya. Pemangkasan mengurangi pekerjaan nyata jauh lebih banyak, menjadi 856,189 papan parsial untuk n = 12 . Penggunaan ruangnya adalah O(n) .

SulitBacktracking

+10

Ratu menyerang setiap petak pada barisnya, kolomnya, dan kedua diagonalnya, sejauh apa pun jaraknya. Diberikan bilangan bulat n, kembalikan jumlah cara untuk menempatkan n ratu pada papan n × n sehingga tidak ada dua ratu yang saling menyerang.

Papan yang berbeda pada petak mana pun dihitung secara terpisah, termasuk bayangan cerminnya.

Fungsi

totalNQueens(n: integer) → integer

ninteger: ukuran papan dan jumlah ratu
Mengembalikaninteger: jumlah cara menempatkan ratu agar tidak ada yang saling menyerang

Batasan

1 ≤ n ≤ 12
Jawaban untuk n = 12 adalah 14,200, jadi nilainya muat dalam integer 32-bit.

Contoh

Input: n = 4
Output: 2
Penjelasan: Jika kita menuliskan kolom ratu di setiap baris dari atas ke bawah, papan-papannya adalah 1, 3, 0, 2 dan 2, 0, 3, 1: bayangan cermin, dihitung sebagai dua. Pilihan lainnya menempatkan dua ratu pada kolom atau diagonal yang sama.

Pertanyaan lanjutan

Bisakah kamu menghitung hanya papan yang tetap berbeda setelah papan diputar dan dicerminkan? Untuk n = 8, 92 papan terbagi menjadi 12 kelompok seperti itu.

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Dua ratu dalam satu baris selalu saling menyerang, jadi papan terdiri dari satu kolom untuk setiap baris: n^n list, sekitar 8.9 × 10^12 untuk n = 12. Bangun papan baris demi baris, buang papan parsial segera setelah ada ratu yang diserang, lalu tandai kolom dan diagonal yang terisi agar pengujian sebuah petak hanya memerlukan tiga pencarian.

Cobalah setiap penempatan dengan satu ratu di setiap baris

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Tuliskan penempatan sebagai list cols, yaitu kolom ratu di setiap baris, lalu telusuri semua list n^n seperti odometer. Ratu di baris i < j saling menyerang jika cols[i] == cols[j] atau |cols[i] - cols[j]| == j - i, karena diagonal bergerak satu kolom untuk setiap baris. Setiap list diperiksa sekali, jadi tidak ada papan yang terlewat atau dihitung dua kali.

Tidak ada yang menghentikan proses lebih awal: bentrokan di dua baris pertama pun tetap menyisakan n^(n-2) list. Untuk n = 8, ada 16,777,216 list untuk 92 papan; untuk n = 12, ada 8.9 × 10^12 list, sekitar 2.5 jam jika setiap pemeriksaan memerlukan satu nanodetik.

Algoritma

Mulai dengan cols yang semuanya bernilai 0.
Tambahkan 1 ke hitungan jika tidak ada pasangan baris i < j yang memenuhi cols[i] == cols[j] atau |cols[i] - cols[j]| == j - i.
Lanjutkan seperti odometer: mulai dari baris terakhir ke atas, atur ulang setiap entri yang bernilai n-1 menjadi 0, lalu tambahkan 1 ke entri pertama yang nilainya kurang dari n-1.
Berhenti dan kembalikan hitungannya ketika setiap entri bernilai 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

Backtracking dengan himpunan kolom dan diagonal

Intuisi

Tempatkan ratu baris demi baris dan uji setiap ratu saat kamu menempatkannya. Mengisi baris-baris di bawahnya tidak bisa menyelamatkan ratu yang diserang, jadi lewati kotak itu. Ratu yang aman melakukan rekursi ke baris berikutnya dan dihapus saat pemanggilan kembali; mencapai baris n dihitung sebagai satu papan.

Hanya tiga garis yang bisa menyerang kotak (row, c): kolomnya, diagonal /, dengan row + c yang konstan, dan diagonal \, dengan row - c yang konstan (tambahkan n-1 agar indeksnya dimulai dari 0). array penanda cols, diag, dan anti mengubah pemeriksaan keamanan menjadi tiga pencarian. Setiap garis menampung paling banyak satu ratu, jadi menghapus penanda saat kembali memulihkan array persis seperti semula.

Baris k memiliki paling banyak n - k kolom, jadi pencariannya dibatasi oleh O(n!), dengan ruang O(n).

Algoritma

Buat array penanda cols berukuran n serta diag dan anti berukuran 2n-1, semuanya mati.
place(row): jika row == n, kembalikan 1.
Untuk setiap kolom c, lewati jika cols[c], diag[row + c], atau anti[row - c + n - 1] menyala.
Jika tidak, nyalakan ketiga penanda, tambahkan place(row + 1) ke total, lalu matikan ketiganya.
Kembalikan total. Jawabannya adalah 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)

Backtracking dengan bitmask

Intuisi

Pencarian menggunakan flag masih menguji semua n kolom pada setiap baris. Bitmask langsung menuju kolom yang kosong. Bit c adalah kolom c pada baris yang sedang diisi: cols menyimpan kolom yang sudah terisi, sedangkan left dan right menyimpan petak yang diserang pada setiap diagonal. Lalu free = ~(cols | left | right) & full, dengan full berisi n bit terendah, dan free & -free adalah petak kosong paling rendah. Satu baris ke bawah, kolom tetap terisi dan setiap serangan diagonal bergeser satu kolom.

Dengan n = 4 dan ratu pertama pada bit = 0010, baris 1 mendapatkan free = 1000: kolom 3, ditemukan tanpa menguji kolom lainnya. Untuk n = 12, 856,188 langkah perulangan menggantikan 10,103,868 pengujian petak. Kode R menumbuhkan satu baris penuh papan parsial sekaligus, alih-alih menggunakan rekursi.

Algoritma

Tetapkan full = (1 << n) - 1.
count(cols, left, right): jika cols == full, kembalikan 1.
Hitung free = ~(cols | left | right) & full.
Selama free bukan 0, ambil bit = free & -free, hapus nilai itu dari free, lalu tambahkan count(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1) ke total.
Kembalikan total. Jawabannya adalah 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)

Jebakan dan kasus tepi

Mengindeks anti dengan row - c tanpa menambahkan n-1. Java menghasilkan exception, C membaca di luar array, dan anti[-2] di Python diam-diam membaca penanda diagonal lain.
Mengatur ukuran array diagonal menjadi n, bukan 2n-1. row + c mencapai 2n-2.
Tidak menghapus penanda setelah pemanggilan rekursif. Cabang berikutnya melihat ratu yang sudah tidak ada, sehingga jumlahnya berkurang.
Tidak menyertakan & full dalam free. ~x mengatur bit di atas kolom n-1, sehingga perulangan memilih petak di luar papan. Di Python atau Ruby, free menjadi negatif dan perulangan tidak pernah berakhir.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu N-Queens II?

Backtracking dibatasi oleh O(n!): baris pertama memiliki n pilihan, baris berikutnya paling banyak n-1, dan seterusnya. Pemangkasan mengurangi pekerjaan nyata jauh lebih banyak, menjadi 856,189 papan parsial untuk n = 12. Penggunaan ruangnya adalah O(n).

Apa perbedaan antara N-Queens dan N-Queens II?

N-Queens mengembalikan setiap papan dalam bentuk baris teks, sedangkan N-Queens II hanya mengembalikan jumlahnya. Pencariannya sama, tetapi proses penghitungan tidak menyimpan papan, sehingga cocok untuk versi bitmask.

Bisakah kamu menggunakan simetri untuk mempercepat N-Queens II?

Mencerminkan papan dari kiri ke kanan menghasilkan papan valid lainnya, jadi hitung papan yang ratu pertamanya berada di kolom 0 hingga n/2 - 1, lalu kalikan dua. Untuk n ganjil, tambahkan papan yang ratu pertamanya berada di kolom tengah satu kali.

def totalNQueens(n):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

n = 4

Output yang diharapkan

N-Queens II

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Cobalah setiap penempatan dengan satu ratu di setiap baris

Backtracking dengan himpunan kolom dan diagonal

Backtracking dengan bitmask

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa