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. Budama, gerçek iş yükünü çok daha aşağıya, n = 12 için 856,189 kısmi tahtaya indirir. Alan karmaşıklığı O(n) 'dir.

ZorGeri izleme

+10

Bir vezir, ne kadar uzakta olursa olsun kendi satırındaki, sütunundaki ve iki köşegenindeki tüm karelere saldırır. Bir n tam sayısı verildiğinde, hiçbir iki vezirin birbirine saldırmadığı şekilde n × n boyutundaki bir tahtaya n vezir yerleştirmenin kaç yolu olduğunu döndürün.

Herhangi bir karede farklılık gösteren tahtalar ayrı sayılır; ayna görüntüleri de buna dahildir.

Fonksiyon

totalNQueens(n: integer) → integer

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

Kısıtlar

1 ≤ n ≤ 12
n = 12 için yanıt 14,200’dür; bu nedenle 32 bitlik bir tamsayıya sığar.

Örnekler

Girdi: n = 4
Çıktı: 2
Açıklama: Her satırın vezir sütunu yukarıdan aşağıya yazıldığında, tahtalar 1, 3, 0, 2 ve 2, 0, 3, 1 olur: birbirlerinin ayna görüntüleridir ve iki çözüm olarak sayılırlar. Diğer tüm seçimlerde iki vezir aynı sütunu veya çaprazı paylaşır.

Ek soru

Tahtayı döndürüp yansıttığında birbirinden farklı kalan tahtaları sayabilir misin? n = 8 için 92 tahta, bu türden 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

Aynı satırdaki iki vezir her zaman birbirini tehdit eder; bu nedenle tahtada her satır için bir sütun seçimi vardır: n^n liste, n = 12 için yaklaşık 8.9 × 10^12. Bunun yerine tahtayı satır satır oluşturun, bir vezir tehdit edilir edilmez kısmi tahtayı bırakın ve dolu sütunları ve köşegenleri işaretleyin; böylece bir kareyi denetlemek üç arama gerektirir.

Her satırda bir vezir olacak şekilde tüm yerleşimleri dene

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

Sezgi

Bir yerleşimi, her satırın vezirinin sütununu belirten cols listesi olarak yaz ve bir sayaç gibi tüm n^n listeleri sırayla dolaş. i < j satırlarındaki vezirler, cols[i] == cols[j] veya |cols[i] - cols[j]| == j - i olduğunda birbirlerine saldırır; çünkü bir çapraz, satır başına bir sütun ilerler. Her liste bir kez kontrol edilir, dolayısıyla hiçbir tahta atlanmaz veya iki kez sayılmaz.

İşlem erkenden durmaz: İlk iki satırdaki bir çakışma bile geriye n^(n-2) liste bırakır. n = 8 için bu, 92 tahta için 16.777.216 listedir; n = 12 içinse 8.9 × 10^12, yani her liste için bir nanosaniyede yaklaşık 2.5 saat sürer.

Algoritma

cols tümü sıfır olacak şekilde başla.
Hiçbir satır çifti i < j için cols[i] == cols[j] veya |cols[i] - cols[j]| == j - i koşulu sağlanmıyorsa sayacı 1 artır.
Bir kilometre sayacı gibi ilerle: son satırdan başlayarak, n-1 değerindeki her girdiyi 0'a sıfırla, ardından n-1'den küçük olan ilk girdiyi 1 artır.
Tüm girdiler n-1 olduğunda dur ve 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 satır satır yerleştir ve her birini yerleştirirken test et. Aşağıdaki satırları doldurmak saldırı altındaki bir veziri kurtaramaz, bu yüzden o kareyi atla. Güvenli bir vezir sonraki satıra özyinelemeli olarak geçer ve çağrı döndüğünde kaldırılır; n satırına ulaşmak bir tahtayı sayar.

(row, c) karesine yalnızca üç çizgi saldırabilir: sütunu, row + c değerinin sabit olduğu / köşegeni ve row - c değerinin sabit olduğu \ köşegeni (n-1 ekleyerek 0'dan başlayan bir dizin elde et). cols, diag ve anti bayrak dizileri, güvenlik testini üç dizi erişimine indirger. Her çizgide en fazla bir vezir bulunur, bu nedenle dönüşte bayrakları temizlemek dizileri tam olarak eski hâline getirir.

k satırında en fazla n - k sütun seçeneği vardır; bu nedenle arama O(n!) ile sınırlıdır ve alan karmaşıklığı O(n)'dir.

Algoritma

n boyutunda cols ve 2n-1 boyutunda diag ve anti bayrak dizileri oluşturun; tüm değerleri kapalı olsun.
place(row): row == n ise 1 döndürün.
Her c sütunu için, cols[c], diag[row + c] veya anti[row - c + n - 1] açıksa sütunu atlayın.
Aksi hâlde üç bayrağı da açın, toplama place(row + 1) değerini ekleyin ve bayrakları kapatın.
Toplamı döndürün. 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 maskeleriyle geri izleme

Sezgi

Bayrak araması her satırın n sütununun tamamını hâlâ sınar; bit maskeleri doğrudan boş olanlara atlar. Bit c, doldurulan satırın c sütunudur: cols alınmış sütunları, left ve right ise her köşegen boyunca saldırı altındaki kareleri tutar. Ardından free = ~(cols | left | right) & full olur; burada full en düşük n bittir ve free & -free en düşük boş karedir. Bir satır aşağıda, sütun alınmış olarak kalır ve her köşegendeki saldırı bir sütun kayar.

n = 4 ve bit = 0010 konumunda ilk vezirle, 1. satır free = 1000 değerini alır: diğerlerini sınamadan bulunan 3. sütun. n = 12 için 856,188 döngü adımı, 10,103,868 kare sınamasının yerini alır. R kodu, özyineleme yapmak yerine kısmi tahtalardan oluşan tam bir satırı aynı anda oluşturur.

Algoritma

full = (1 << n) - 1 olarak ayarla.
count(cols, left, right): eğer cols == full ise, return 1.
free = ~(cols | left | right) & full değerini hesapla.
free 0 değilken, bit = free & -free değerini al, onu free içinden çıkar ve toplama count(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1) değerini ekle.
Toplamı döndür. 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

anti öğesini n-1 eklemeden row - c ile indekslemek. Java hata verir, C dizinin dışını okur ve Python'da anti[-2] sessizce başka bir çaprazın bayrağını okur.
Çapraz dizilerini 2n-1 yerine n boyutunda oluşturmak. row + c değeri 2n-2'ye ulaşır.
Özyinelemeli çağrıdan sonra bayrakları sıfırlamamak. Sonraki dallar artık yerinde olmayan vezirleri görür ve sayı azalır.
free ifadesine & full eklememek. ~x, n-1 sütununun üzerindeki bitleri ayarlar; böylece döngü tahta dışındaki kareleri seçer. Python veya Ruby'de free negatif olur ve döngü hiç bitmez.

Sıkça sorulan sorular3

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. Budama, gerçek iş yükünü çok daha aşağıya, n = 12 için 856,189 kısmi tahtaya indirir. Alan karmaşıklığı O(n)'dir.

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

N-Queens metin satırları olarak çizilmiş tüm tahtaları döndürür; N-Queens II ise yalnızca kaç tane olduğunu döndürür. Arama aynıdır, ancak sayma hiçbir tahta saklamaz; bu da bitmask sürümüne uygundur.

N-Queens II'yi hızlandırmak için simetriden yararlanabilir misin?

Bir tahtayı soldan sağa yansıtmak başka bir geçerli tahta verir; bu nedenle ilk veziri 0 ile n/2 - 1 sütunlarında olan tahtaları sayıp sonucu ikiyle çarp. n tek olduğunda, ilk veziri orta sütunda olan tahtaları bir kez ekle.

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

Test #1

Test #2

Argüman

n = 4

Beklenen Çıktı

N-Queens II

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her satırda bir vezir olacak şekilde tüm yerleşimleri dene

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

Bit maskeleriyle geri izleme

Tuzaklar ve uç durumlar

Sıkça sorulan sorular3

Benzer problemler