N-Queens II

Q: N-Queens II'nin zaman karmaşıklığı nedir?

Geri izleme O(n!) ile sınırlıdır: ilk satırda n seçenek, sonraki satırda en fazla n-1 seçenek vardır ve bu böyle devam eder. Köşegen kontrolleri, arama alanını bu sınırın çok altına indirerek n = 12 için 856.189 kısmi tahtaya düşürür. Çözümleri saymak için bilinen bir polinom zamanlı yöntem olmadığından, bu tür bir arama standart yaklaşımdır. Alan kullanımı O(n) ’dir.

Q: Bir karenin hangi köşegeni üzerinde olduğunu nasıl anlarsınız?

/ çaprazında bir adım ilerlemek satıra 1 ekler ve sütundan 1 çıkarır; bu nedenle row + col hiç değişmez. \ çaprazında ilerlemek her ikisine de 1 ekler; bu nedenle row - col hiç değişmez. Her toplam bir çaprazı tanımlar ve farka n-1 eklemek, onu 0 ile 2n-2 arasında bir dizi indeksine dönüştürür.

ZorGeri izleme

+10

Satranç tahtasındaki bir vezir, ne kadar uzakta olursa olsun bulunduğu satırdaki, sütundaki ve iki köşegenindeki tüm karelere saldırır. Bir n tam sayısı veriliyor. Birbirine saldırmayan n veziri n × n boyutundaki bir tahtaya yerleştirmenin kaç farklı yolu olduğunu döndürün.

Birinde bir vezirin bulunduğu, diğerinde ise boş olan en az bir kare varsa iki yerleşim farklıdır. Bu nedenle, birbirine benzeseler bile bir tahta ile ayna görüntüsü iki farklı yol sayılır.

Fonksiyon

totalNQueens(n: integer) → integer

ninteger: tahtanın boyutu ve vezir sayısı
Döndürürinteger: vezirleri hiçbirinin diğerine saldırmayacağı şekilde yerleştirmenin yolu sayısı

Kısıtlar

1 ≤ n ≤ 12
n = 12 için cevap 14.200’dür, dolayısıyla 32 bitlik bir tamsayıya sığar.

Örnekler

Girdi: n = 4
Çıktı: 2
Açıklama: Her satırdaki vezirin sütununu yukarıdan aşağıya yazarak, iki tahta 1, 3, 0, 2 ve 2, 0, 3, 1 olur. Her biri diğerinin ayna görüntüsüdür ve iki farklı çözüm olarak sayılırlar. Diğer tüm seçimlerde iki vezir aynı sütunu veya çaprazı paylaşır.

Gönderirken +10 gizli test

Ek soru

Tahtayı döndürüp yansıttıktan sonra farklı kalmaya devam eden tahtaları sayabilir misin? n = 8 için 92 tahta bu tür 12 gruba ayrılır.

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Her satır için bir sütun seçilerek bir yerleşim belirlenir; çünkü aynı satırdaki iki vezir birbirine her zaman saldırır. Bu hâlâ n^n seçenek demektir; n = 12 için yaklaşık 8.9 × 10^12 seçenek vardır, dolayısıyla hepsini listeleyemezsiniz. Bunu iki fikir çözer. Tahtayı satır satır oluşturun ve bir vezire saldırıldığı anda kısmi tahtayı terk edin; bu, n = 12 için aramayı bir milyonun altındaki kısmi tahtaya indirir. Ayrıca hangi sütunların ve köşegenlerin dolu olduğunu kaydedin; böylece bir kareyi denemek, o ana kadar yerleştirilmiş her veziri taramak yerine üç arama gerektirir.

Her satıra bir vezir koyarak tüm yerleşimleri deneyin

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Her satırda tam olarak bir vezir bulunmalıdır; dolayısıyla bir yerleşim, cols listesidir ve cols[r], r satırındaki vezirin sütununu gösterir. Her giriş, n sütundan herhangi biri olabilir; bu nedenle n^n liste vardır. Hepsini bir kilometre sayacının saydığı gibi sırayla deneyin: son girişi bir artırın; n-1 değerini aşınca 0'a sıfırlayın ve bir önceki girişe elde ekleyin.

Her liste için i < j olan her satır çiftini karşılaştırın. İki vezir aynı sütunu paylaşıyorsa, yani cols[i] == cols[j] ise veya aynı çapraz üzerindeyse birbirlerine saldırırlar. Çapraz üzerinde, bir satır aşağı inmek bir sütun sola ya da sağa gitmek anlamına gelir; bu nedenle iki vezir, sütun farkı satır farkına eşitse tam olarak aynı çaprazı paylaşır: |cols[i] - cols[j]| == j - i. Her çifti geçen bir liste, geçerli bir tahtadır. Her liste kontrol edildiğinden hiçbiri atlanmaz ve hiçbiri iki kez sayılmaz.

Yavaştır, çünkü erken durmaz. İlk iki satırda aynı çapraz üzerindeki iki vezir tahtayı geçersiz kılar, ancak kilometre sayacı diğer satırları doldurmanın n^(n-2) yolunun tamamını yine de dener. n = 8 için 92 tahta bulmak üzere 16,777,216 liste denenir. n = 12 için bu sayı yaklaşık 8.9 × 10^12 listedir. Liste başına bir nanosaniyede bile bu yaklaşık 2,5 saat sürer.

Algoritma

cols değerlerinin tümü 0 ile başla: her vezir 0. sütunda olsun.
i < j olan her satır çifti için kontrol et: cols[i] == cols[j] veya |cols[i] - cols[j]| == j - i ise liste geçersizdir.
Hiçbir çift çatışmıyorsa sayaca 1 ekle.
cols değerlerini bir sayaç gibi ilerlet: son satırdan başlayarak yukarı doğru, n-1 değerini tutan her girdiyi 0 yap, ardından 0 yapmadığın ilk girdiye 1 ekle.
Tüm girdiler n-1 değerindeyse n^n listenin tümü incelenmiştir: sayacı döndür.

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

Sütun ve köşegen kümeleriyle geri izleme

Sezgi

Vezirleri yukarıdan başlayarak satır satır yerleştir ve her yeni veziri yerleştirir yerleştirmez kontrol et. Saldırı altındaysa, aşağıdaki satırları doldurmanın hiçbir yolu bunu düzeltemez; bu yüzden kareyi hemen atla. Güvendeyse bir sonraki satıra özyinelemeli olarak geç ve bu çağrı geri döndüğünde veziri kaldırıp sonraki sütunu dene. n satırına ulaşan bir çağrı, n güvenli vezir yerleştirmiştir ve bir tahtayı sayar. Bu, geri izlemeli aramadır ve arama alanını etkili biçimde budar: n = 12 için 8.9 × 10^12 tamamlanmış tahta yerine 856,189 kısmi tahtayı ziyaret eder.

Diğer yarısı, bir karenin hızlıca test edilmesidir. Aşağıdaki satırlar boştur ve yeni vezirin kendi satırında başka vezir yoktur; dolayısıyla (row, c) karesine yalnızca üç çizgi saldırabilir: sütunu, / köşegeni ve \ köşegeni. Bir / köşegeni üzerindeki her karenin row + c değeri aynıdır ve bu değer 0 ile 2n-2 arasındadır. Bir \ köşegeni üzerindeki her karenin row - c değeri aynıdır ve -(n-1) ile n-1 arasındadır; dolayısıyla 0 ile 2n-2 arasında bir indeks elde etmek için n-1 ekle. Üç bayrak dizisi tut: n boyutunda cols ve 2n-1 boyutunda diag ile anti. Kare ancak ve ancak bu üç bayrağın tümü kapalıysa güvenlidir: üç erişim, O(1); şimdiye kadar yerleştirilmiş her vezirle karşılaştırmak ise O(n) maliyetindedir.

Bir çizgide en fazla bir vezir bulunabilir; bu nedenle bir veziri yerleştirmek üç bayrağını da açar, veziri kaldırmak da onları tekrar kapatarak dizileri tam olarak eski durumlarına getirir. 4'e 4'lük tahtada (0, 0) konumundaki bir vezir cols[0], diag[0] ve anti[3] değerlerini ayarlar. 1. satırdaki 1. sütun anti[3] üzerindedir, bu yüzden vezirin kendisine bakmadan atlanır.

İlk satırda n sütun seçeneği, ikinci satırda en fazla n-1 seçenek ve bu şekilde devam eder; dolayısıyla arama O(n!) ile sınırlıdır ve köşegenler olasılıkları bunun çok altına düşürür. n = 12 için döngüler toplamda 10,103,868 kareyi test eder. Özyineleme n çağrı derinliğindedir ve diziler yaklaşık 5n bayrak tutar; dolayısıyla alan karmaşıklığı O(n)'dir.

Algoritma

Tümü kapalı olan üç bayrak dizisi oluştur: n öğeli cols, her biri 2n-1 öğeli diag ve anti.
place(row) fonksiyonunu yaz. row == n ise 1 döndür: her satırda güvenli bir vezir vardır.
Aksi takdirde, her c sütunu için cols[c], diag[row + c] veya anti[row - c + n - 1] açıksa o sütunu atla.
Güvenli bir sütun için üç bayrağı aç, place(row + 1) değerini toplama ekle, ardından bayrakları kapat.
Toplamı döndür. Yanıt place(0) değeridir.

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)

Bit maskelerle geri izleme

Sezgi

Kümelerle yapılan arama hızlıdır, ancak her satırda hâlâ n sütunun tamamını, çoğu zaten saldırı altında olsa da, sınar. Bir bit maskesi, doğrudan boş karelere geçmeni sağlar. Bir tamsayının c bitini doldurmak üzere olduğun satırın c sütunu olarak düşün ve üç maske tut: cols, zaten alınmış sütunlar; left, bu satırda bir çapraz yön boyunca saldırı altındaki kareler; ve right, diğer yönde saldırı altındaki kareler.

Boş kareler böylece tek bir ifadeyle bulunur: free = ~(cols | left | right) & full; burada full, düşük n bitin ayarlı olduğu maskedir. free & -free, en düşük boş kareyi ayıklar; bu değeri çıkarmak da sonraki kareye geçer. bit konumuna bir vezir yerleştirip bir alt satıra indiğinde, sütunu alınmış olarak kalırken her çapraz saldırı bir sütun kayar. Dolayısıyla sonraki satıra cols | bit, ((left | bit) << 1) & full ve (right | bit) >> 1 değerleri aktarılır. Geri alma işlemi gerekmez: her çağrı kendi üç tamsayısını alır. cols == full olduğunda n vezirin tümü yerleştirilmiştir.

n = 4 değerini ve ilk vezirin 1. sütunda olduğunu ele alalım: sütun 0 en sağdaki bit olacak şekilde yazıldığında bit = 0010. 1. satırda cols = 0010, left = 0100 ve right = 0001 olur; dolayısıyla free = 1000: tek seçenek 3. sütundur ve 0, 1 veya 2. sütunları sınamadan bulunur.

Arama, kümeler sürümündekiyle aynı kısmi tahtaları ziyaret eder, ancak artık döngünün her adımı bir vezir yerleştirir. n = 12 için bu, her adımda birkaç tamsayı işlemiyle 10.103.868 kare sınaması yerine 856.188 adım demektir. Süre hâlâ O(n!) ile sınırlıdır ve özyineleme n çağrı derinliğindedir. R kodu aynı maskeleri özyineleme kullanmadan çalıştırır: bir satırdaki her kısmi tahtayı bir vektörde tutar ve hepsini her seferinde bir satır büyütür; böylece n çağrı yerine tahtaların bir düzeyinin tamamını bellekte tutar.

Algoritma

full = (1 << n) - 1 olarak ayarlayın; bu, tüm n sütunların maskesidir.
count(cols, left, right) fonksiyonunu yazın. cols == full ise 1 döndürün.
free = ~(cols | left | right) & full değerini hesaplayın.
free 0 olmadığı sürece bit = free & -free değerini alın, free içinden çıkarın ve toplam değere count(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1) değerini ekleyin.
Toplamı döndürün. Yanıt count(0, 0, 0) değeridir.

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)

Tuzaklar ve uç durumlar

Aramanın kendisi kısadır. Hataların çoğu köşegen aritmetiğinde ve geri alma adımındadır.

n-1 eklemeden row - c değerini dizin olarak kullanmak. Java'da bu hata fırlatır, C'de dizinin dışındaki belleği okur ve Python'da anti[-2] sessizce başka bir köşegenin bayrağını okur; böylece hata vermeden sayı yanlış çıkar.
Köşegen dizilerini n elemanla boyutlandırmak. n × n boyutundaki bir tahtada her yönde 2n-1 köşegen vardır.
Yalnızca bir köşegen yönünü ya da yalnızca sütunları kontrol etmek. Her iki köşegen yönü de saldırır.
Özyinelemeli çağrı döndükten sonra bayrakları kapatmayı unutmak. Böylece sonraki her dal artık tahtada olmayan vezirleri görür ve sayı azalır.
free hesaplanırken & full kısmını atlamak. ~x ayrıca n-1 sütununun üstündeki her biti ayarlar; bu yüzden döngü tahta dışındaki kareleri seçer ve sabit genişlikleri olmayan tamsayılar kullanan Python veya Ruby'de free negatif olur ve döngü hiç bitmez.
Ayna görüntülerini tek bir tahta olarak değerlendirmek. Problem bunları ayrı sayar: n = 4 için 2 tahta vardır ve bunlar birbirlerinin ayna görüntüleridir.
Küçük tahtalar için yanlış özel durumlar yazmak. n = 1 için 1 tahta vardır; n = 2 ve n = 3 için hiç tahta yoktur. Arama, özel durum olmadan üçünü de doğru sonuçlandırır.

Sıkça sorulan sorular4

N-Queens II'nin zaman karmaşıklığı nedir?

Geri izleme O(n!) ile sınırlıdır: ilk satırda n seçenek, sonraki satırda en fazla n-1 seçenek vardır ve bu böyle devam eder. Köşegen kontrolleri, arama alanını bu sınırın çok altına indirerek n = 12 için 856.189 kısmi tahtaya düşürür. Çözümleri saymak için bilinen bir polinom zamanlı yöntem olmadığından, bu tür bir arama standart yaklaşımdır. Alan kullanımı O(n)’dir.

Bir karenin hangi köşegeni üzerinde olduğunu nasıl anlarsınız?

/ çaprazında bir adım ilerlemek satıra 1 ekler ve sütundan 1 çıkarır; bu nedenle row + col hiç değişmez. \ çaprazında ilerlemek her ikisine de 1 ekler; bu nedenle row - col hiç değişmez. Her toplam bir çaprazı tanımlar ve farka n-1 eklemek, onu 0 ile 2n-2 arasında bir dizi indeksine dönüştürür.

N-Queens ile N-Queens II arasındaki fark nedir?

N-Queens, metin satırları olarak çizilmiş tüm tahtaları ister. N-Queens II ise yalnızca kaç tane olduklarını sorar. Arama aynı geri izleme yöntemidir, ancak sayma için bellekte bir tahta tutmaya gerek yoktur; yalnızca sütun ve köşegen kümeleri yeterlidir, bu yüzden daha hızlı ve daha hafiftir. Bit maskesi sürümünü burada doğal kılan da budur.

Simetriyi kullanarak N-Queens II’yi hızlandırabilir misin?

Evet. Bir tahtayı soldan sağa yansıtmak başka bir geçerli tahta verir; bu nedenle ilk veziri sol yarıda olan tahtalar, ilk veziri sağ yarıda olan tahtalarla eşleşir. İlk veziri 0 ile n/2 - 1 sütunlarında olan tahtaları say ve bu sayıyı ikiyle çarp. n tek olduğunda, ilk veziri orta sütunda olan tahtaları bir kez ekle. Böylece arama yarıya iner.

Python

def totalNQueens(n):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Girdi

n = 4

Beklenen

N-Queens II

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her satıra bir vezir koyarak tüm yerleşimleri deneyin

Sütun ve köşegen kümeleriyle geri izleme

Bit maskelerle geri izleme

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler