Sekiz kraliçe yapboz - Eight queens puzzle

a B C NS e F G H
8
Chessboard480.svg
f8 beyaz kraliçe
d7 beyaz kraliçe
g6 beyaz kraliçe
a5 beyaz kraliçe
h4 beyaz kraliçe
b3 beyaz kraliçe
e2 beyaz kraliçe
c1 beyaz kraliçe
 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a B C NS e F G H
Sekize sadece simetrik çözeltisi (bulmacayı kraliçeler kadar rotasyon ve yansıma)

Sekiz kraliçe bulmaca sekiz yerleştirilmesi problemi ile ilgilidir olan satranç kraliçe 8 x 8 satranç tahtası nedenle iki kraliçe birbirine tehdit eden; bu nedenle, bir çözüm, iki vezirin aynı satırı, sütunu veya köşegeni paylaşmamasını gerektirir. Sekiz kraliçe bulmaca daha genel bir örneğidir n sorunu kraliçelerini yerleştirilmesi , n , bir non-atak kraliçe n x n çözeltiler doğal sayılar ana kadar olan satranç tahtası, n haricinde , n = 2 ve n = 3.

Tarih

Satranç besteci Max Bezzel 1848 yılında sekiz kraliçeler bulmaca yayınlanan Franz Nauck Nauck ayrıca bulmaca uzatıldı 1850 yılında ilk çözüm yayımlandı n ile sorunu Queens n bir satranç tahtası üzerinde kraliçeleri n × n kareler.

O zamandan beri, Carl Friedrich Gauss da dahil olmak üzere birçok matematikçi hem sekiz kraliçe bulmacası hem de genelleştirilmiş n- kraliçe versiyonu üzerinde çalıştı . 1874'te S. Gunther , çözüm bulmak için belirleyicileri kullanan bir yöntem önerdi . JWL Glaisher, Gunther'in yaklaşımını geliştirdi.

1972'de Edsger Dijkstra , yapısal programlama dediği şeyin gücünü göstermek için bu problemi kullandı . Derinlik öncelikli geri izleme algoritmasının oldukça ayrıntılı bir tanımını yayınladı . 2

Çözümleri oluşturma ve sayma

4,426,165,368 olduğu gibi 8-Queens sorununa tüm çözümler bulma problemi, oldukça hesaplama pahalı olabilir (yani 64 ° C 8 ) 8 × 8 gemide sekiz kraliçe olası düzenlemeleri, fakat sadece 92 çözümleri. Hesaplama gereksinimlerini azaltan kısayollar veya kaba kuvvet hesaplama tekniklerinden kaçınan temel kurallar kullanmak mümkündür . Örneğin, her kraliçeyi tek bir sütuna (veya satıra) sınırlayan basit bir kural uygulayarak, yine de kaba kuvvet olarak kabul edilse de, olasılıkların sayısını 16.777.216 (yani, 8 8 ) olası kombinasyona indirmek mümkündür. Permütasyon oluşturmak , olasılıkları yalnızca 40.320'ye (yani, 8! ) düşürür ve daha sonra çapraz saldırılar için kontrol edilir.

Çözümler

Sekiz kraliçe bulmacasının 92 farklı çözümü var. Sadece tahtanın dönme ve yansıma simetri işlemleri ile farklılık gösteren çözümler bir olarak sayılırsa, bulmacanın 12 çözümü vardır. Bunlara temel çözümler denir ; her birinin temsilcileri aşağıda gösterilmiştir.

Temel bir çözüm genellikle 90, 180 veya 270° döndürülerek elde edilen ve daha sonra dört dönme varyantının her birini bir aynada sabit bir konumda yansıtarak elde edilen sekiz varyanta (orijinal formu dahil) sahiptir. Bununla birlikte, bir çözüm kendi 90° dönüşüne eşdeğerse (5×5 tahtada beş vezirli bir çözümde olduğu gibi), bu temel çözümün yalnızca iki varyantı olacaktır (kendisi ve yansıması). Bir çözüm kendi 180° dönüşüne eşitse (ancak 90° dönüşüne değil), dört varyantı olacaktır (kendisi ve yansıması, 90° dönüşü ve bunun yansıması). Eğer n > 1 ise, bir çözümün kendi yansımasına eşdeğer olması mümkün değildir çünkü bu iki vezirin karşı karşıya gelmesini gerektirir. 8×8'lik bir tahtada sekiz vezir ile problemin 12 temel çözümünden tam olarak biri (aşağıda 12. çözüm) kendi 180° dönüşüne eşittir ve hiçbiri 90° dönüşüne eşit değildir; böylece farklı çözümlerin sayısı 11×8 + 1×4 = 92'dir.

Tüm temel çözümler aşağıda sunulmuştur:

Çözüm 10, hiçbir üç kraliçenin düz bir çizgide olmaması gibi ek bir özelliğe sahiptir . Çözüm 1 ve 8'de 4 kraliçe çizgi vardır.

Çözümlerin varlığı

Çözümlerin sayısını saymak için kullanılan kaba kuvvet algoritmaları, n  = 8 için hesaplama açısından yönetilebilir , ancak n  ≥ 20 olan problemler için 20 olarak inatçı olacaktır ! = 2.433 × 10 18 . Amaç tek bir çözüm bulmaksa, herhangi bir arama yapmadan tüm n ≥ 4 için çözümlerin var olduğu gösterilebilir . Bu çözümler, n = 8, 9 ve 10 için aşağıdaki örneklerde olduğu gibi merdiven basamaklı desenler sergiler :

Yukarıdaki örnekler aşağıdaki formüllerle elde edilebilir. Let ( i , j ) kolonunda kare olarak i ve satır j üzerinde n x n satranç tahtası, k bir tamsayı.

Bir yaklaşım

  1. n'nin 6'ya bölünmesinden kalan 2 veya 3 değilse, o zaman liste basitçe tüm çift sayıların ardından n'den büyük olmayan tüm tek sayılardır .
  2. Aksi takdirde, çift ve tek sayıların (2, 4, 6, 8 – 1, 3, 5, 7) ayrı listelerini yazın.
  3. Kalan 2 ise, tek listede 1 ve 3'ü değiştirin ve 5'i sona ( 3, 1 , 7, 5 ) taşıyın .
  4. Kalan 3 ise, 2'yi çift listenin sonuna ve 1,3'ü tek listenin sonuna (4, 6, 8, 2 – 5, 7, 1, 3 ) taşıyın .
  5. Tek listeyi çift listeye ekleyin ve vezirleri bu sayılarla verilen satırlara soldan sağa doğru yerleştirin (a2, b4, c6, d8, e3, f1, g7, h5).

İçin , n  = 8 , yukarıda temel bir çözüm 1 'de bu sonuçlar. Birkaç örnek daha takip ediyor.

  • 14 kraliçe (kalan 2): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5.
  • 15 kraliçe (kalan 3): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3.
  • 20 kraliçe (kalan 2): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 9, 11, 13, 15, 17, 19, 5.

Sayma çözümleri

Aşağıdaki tablolar, yerleştirilmesi için çözümlerin sayısı elde n bir ile kraliçe n x n tahta, her ikisi de temel (dizi A002562 olarak OEIS ) ve (dizi A000170 olarak OEIS ).

n temel herşey
1 1 1
2 0 0
3 0 0
4 1 2
5 2 10
6 1 4
7 6 40
8 12 92
9 46 352
10 92 724
11 341 2.680
12 1.787 14.200
13 9,233 73.712
14 45.752 365.596
15 285.053 2.279.184
16 1.846.955 14,772,512
17 11.977.939 95.815.104
18 83.263.591 666.090.624
19 621.012.754 4.968.057.848
20 4,878,666,808 39.029.188.884
21 39.333.324.973 314.666.222.712
22 336.376.244,042 2.691.008.701.644
23 3.029.242.658.210 24.233.937.684.440
24 28.439.272.956.934 227.514.171.973.736
25 275.986.683.743.434 2.207.893.435.808.352
26 2.789.712.466.510.289 22.317.699.616.364.044
27 29.363.495.934.315.694 234.907.967.154.122.528

Altı vezir bulmacasının beş vezir bulmacasından daha az çözümü vardır.

Kesin çözüm sayısı için bilinen bir formül yoktur. 27 × 27 tahta, tamamen numaralandırılmış en yüksek dereceli tahtadır.

Çözeltilerin sayısı formunun asimptotikler sahip olan toroidal bir satranç tahtası için asimptotikler ise eşit zaman ile

İlgili sorunlar

  • Daha yüksek boyutlar
n boyutunda d boyutlu bir satranç uzayına yerleştirilebilecek saldırmayan vezir sayısını bulun . Bazı yüksek boyutlara n'den fazla vezir yerleştirilebilir (en küçük örnek 3×3×3 satranç alanında dört saldırmayan vezirdir) ve aslında herhangi bir k için , n k'nin olduğu yerde daha yüksek boyutların olduğu bilinmektedir. kraliçeler tüm boşluklara saldırmak için yeterli değildir.
  • Vezirler dışındaki parçaları kullanma
8×8 tahtaya 32 şövalye veya 14 fil , 16 kral veya sekiz kale yerleştirilebilir , böylece iki taş birbirine saldırmaz. Vezirler için peri satranç taşları da değiştirildi. Şövalyeler söz konusu olduğunda, yalnızca zıt renge hareket ettikleri için belirli bir rengin her karesine bir tane yerleştirmek kolay bir çözümdür. Çözüm, kaleler ve şahlar için de kolaydır. Sekiz kale uzun bir köşegen boyunca (diğer binlerce çözüm arasında) yerleştirilebilir ve 16 şah, 2'ye 2 kareye bölünerek ve şahları her karede eşdeğer noktalara yerleştirerek tahtaya yerleştirilir.
  • satranç çeşitleri
Shogi gibi satranç çeşitleri için ilgili problemler sorulabilir . Örneğin, n + k ejderha kralları problemi , bir n × n shogi tahtasına k adet shogi piyonunu ve n + k adet karşılıklı saldırmayan ejderha kralını yerleştirmeyi ister .
Matematik olarak, bir permütasyon matrisi bir dizi geometrik olarak kabul edilebilir , n bir karelerinin üzerinde bulunan noktalar n x n her sıra veya sütun tek nokta ihtiva etmekte olduğu şekilde satranç tahtası. Böylece, n sıralı bir permütasyon matrisi, bir n - kale bulmacasının çözümüdür.
  • Standart olmayan panolar
Polya çalışılan n bir sorunu kraliçelerini toroidal ( "halka şeklinde") kartı ve bir çözüm olduğunu göstermiştir n x n , ancak ve ancak kurulu n Pearson ve Pearson algoritmik doldurulur 2009 2 veya 3 ile bölünebilir değildir n 2 kraliçeli üç boyutlu tahtalar ( n × n × n ) ve bunların katlarının bulmacanın dört boyutlu bir versiyonu için çözümler üretebileceğini önerdi.
  • Egemenlik
Bir n × n tahtası verildiğinde , hakimiyet sayısı , her kareye saldırmak veya işgal etmek için gereken minimum vezir (veya diğer taşlar) sayısıdır. İçin n = 8 kraliçenin hakimiyeti sayısı 5'tir.
  • Kraliçeler ve diğer parçalar
Varyantlar, kraliçeleri diğer parçalarla karıştırmayı içerir; örneğin, m vezirleri ve m atları n × n'lik bir tahtaya yerleştirmek, böylece hiçbir taş diğerine saldırmaz veya vezirleri ve piyonları hiçbir iki vezirin birbirine saldırmaması için yerleştirmek.
1992'de Demirörs, Rafraf ve Tanik, bazı sihirli kareleri n -vezir çözümlerine dönüştürmek için bir yöntem yayınladılar .
Bir n × n matrisinde, 1'den n'ye kadar olan her basamağı , aynı basamakta veya sütunda aynı basamağın iki örneği olmayacak şekilde matristeki n konuma yerleştirin.
Tahtanın n sıralarının her biri için bir birincil sütun, n dosyalarının her biri için bir birincil sütun ve tahtanın 4 n - 6 önemsiz köşegenlerinin her biri için bir ikincil sütun içeren bir matris düşünün . Matris sahiptir n 2 satır: her olası kraliçe yerleşim için bir tane ve her satır o meydanın rütbe, dosyaya gelen sütunlar ve Çapraz olarak bir 1 ve tüm bir 0 diğer sütunlar vardır. O zaman n kraliçe problemi, bu matrisin satırlarının bir alt kümesini seçmeye eşdeğerdir, öyle ki her birincil sütun tam olarak seçilen satırlardan birinde 1'e sahiptir ve her ikincil sütun, seçilen satırlardan en fazla birinde 1'e sahiptir; bu, sudoku'nun başka bir örneği olduğu genelleştirilmiş bir tam örtük probleminin bir örneğidir.
  • n -Queens Tamamlama
2017 tarihli bir makale, " Bazı vezirlerin zaten yerleştirildiği bir n × n satranç tahtası verildiğinde , iki vezirin birbirine saldırmaması için kalan her sıraya bir vezir yerleştirebilir misiniz?" ve ilgili birkaç sorun. Yazarlar, bu sorunların NP-complete ve #P-complete olduğunu iddia ettiler .

Algoritma tasarımında alıştırma

Sekiz vezir bulmacasının tüm çözümlerini bulmak, basit ama önemsiz bir problemin güzel bir örneğidir. Bu nedenle, genellikle kısıt programlama , mantıksal programlama veya genetik algoritmalar gibi geleneksel olmayan yaklaşımlar dahil olmak üzere çeşitli programlama teknikleri için örnek bir problem olarak kullanılır . Çoğu zaman, bir n'ye n -1 kraliçe yerleştirme sorununa herhangi bir çözüme tek bir kraliçe eklemek açısından n kraliçe problemini tümevarımsal olarak ifade ederek özyinelemeli bir algoritma ile çözülebilecek bir problem örneği olarak kullanılır. × n satranç tahtası. İndüksiyon boş satranç tahtası satranç tahtası, 0 kraliçe yerleştirme 'problem' çözelti ile dibe.

Bu teknik,  sekiz vezirin tüm 64 8  = 2 48 = 281.474.976.76.710.656 olası kör yerleşimini göz önünde bulunduran ve daha sonra iki vezirin tüm yerleşimlerini kaldırmak için bunları filtreleyen saf kaba kuvvet arama algoritmasından çok daha verimli bir şekilde kullanılabilir. vezirler ya aynı karede (sadece 64!/56! = 178.462.987.637.760 olası yerleşim bırakarak) ya da karşılıklı hücum pozisyonlarında. Bu çok zayıf algoritma, diğer şeylerin yanı sıra, sekiz kraliçenin atamalarının tüm farklı permütasyonlarında aynı sonuçları tekrar tekrar üretecek ve aynı hesaplamaları her birinin farklı alt kümeleri için tekrar tekrar tekrar edecektir. çözüm. Daha iyi bir kaba kuvvet algoritması, her sıraya tek bir kraliçe yerleştirir ve yalnızca 8 8  = 2 24  = 16.777.216 kör yerleşime yol açar .

Bundan çok daha iyisini yapmak mümkündür. Bir algoritma, 1'den 8'e kadar olan sayıların (8! = 40.320 vardır) permütasyonlarını üreterek sekiz kale bulmacasını çözer ve her sıraya bir vezir yerleştirmek için her permütasyonun öğelerini indeks olarak kullanır. Ardından çapraz hücum pozisyonlarına sahip tahtaları reddeder. Permütasyon yönteminde küçük bir iyileştirme olan geri izleme derinlik öncelikli arama programı, her seferinde bir tahta sırasını dikkate alarak arama ağacını oluşturur ve çözüm olmayan tahta konumlarının çoğunu yapımlarının çok erken bir aşamasında ortadan kaldırır. Eksik tahtalarda bile kale ve çapraz saldırıları reddettiği için, yalnızca 15.720 olası vezir yerleşimini inceler. Yalnızca 5.508 olası kraliçe yerleşimini inceleyen bir başka gelişme, permütasyona dayalı yöntemi erken budama yöntemiyle birleştirmektir: permütasyonlar önce derinlik oluşturulur ve kısmi permütasyon bir diyagonal saldırı üretirse arama alanı budanır . Kısıtlı programlama da bu problem üzerinde çok etkili olabilir.

8 kraliçeye min-çatışma çözümü

Kapsamlı aramaya bir alternatif, tipik olarak tahtadaki tüm kraliçelerle, örneğin sütun başına bir kraliçeyle başlayan bir 'yinelemeli onarım' algoritmasıdır. Daha sonra çatışmaların (saldırıların) sayısını sayar ve vezirlerin yerleşiminin nasıl iyileştirileceğini belirlemek için bir buluşsal yöntem kullanır. ' Minimum-çatışma ' buluşsal yöntemi (en fazla sayıda çakışma içeren parçayı aynı sütundaki çakışma sayısının en küçük olduğu kareye taşımak) özellikle etkilidir: 1.000.000 vezir sorununa 50 adımdan daha kısa sürede bir çözüm bulur ortalamada. Bu, ilk yapılandırmanın 'makul derecede iyi' olduğunu varsayar - bir milyon kraliçenin tümü aynı satırda başlarsa, onu düzeltmek için en az 999.999 adım gerekir. 'Oldukça iyi' bir başlangıç ​​noktası, örneğin, her bir veziri, halihazırda tahtada bulunan en az sayıda vezir ile çelişecek şekilde kendi satır ve sütununa koyarak bulunabilir.

Yukarıda özetlenen geri izleme aramasının aksine, yinelemeli onarım bir çözümü garanti etmez: tüm açgözlü prosedürler gibi , yerel bir optimumda takılıp kalabilir. (Böyle bir durumda, algoritma farklı bir başlangıç ​​konfigürasyonu ile yeniden başlatılabilir.) Öte yandan, derinlik öncelikli arama kapsamının ötesinde birkaç büyüklük mertebesi olan problem boyutlarını çözebilir.

Eight-Queens-animation.gif

Bu animasyon , sorunu çözmek için geri izlemeyi gösterir. Çatışmaya neden olmadığı bilinen bir sütuna bir kraliçe yerleştirilir. Bir sütun bulunamazsa, program son iyi duruma döner ve ardından farklı bir sütun dener.

Geri izlemeye bir alternatif olarak, çözümler, her seferinde bir satır olmak üzere, geçerli kısmi çözümleri yinelemeli olarak numaralandırarak sayılabilir. Tüm pano konumlarını oluşturmak yerine, bloke edilmiş köşegenler ve sütunlar bitsel işlemlerle izlenir. Bu, bireysel çözümlerin kurtarılmasına izin vermez.

Örnek program

Aşağıdaki, 1976'da Niklaus Wirth tarafından hazırlanan bir Pascal programıdır . Sekiz kraliçe sorununa bir çözüm bulur. 

program eightqueen1(output);
 
var i : integer; q : boolean;
    a : array[ 1 ..  8] of boolean;
    b : array[ 2 .. 16] of boolean;
    c : array[−7 ..  7] of boolean;
    x : array[ 1 ..  8] of integer;
 
procedure try( i : integer; var q : boolean);
    var j : integer;
    begin 
    j := 0;
    repeat 
        j := j + 1; 
        q := false;
        if a[ j] and b[ i + j] and c[ i − j] then
            begin 
            x[ i    ] := j;
            a[     j] := false; 
            b[ i + j] := false; 
            c[ i − j] := false;
            if i < 8 then
                begin
                try( i + 1, q);
                if not q then
                    begin 
                    a[     j] := true; 
                    b[ i + j] := true; 
                    c[ i − j] := true;
                    end
                end 
            else 
                q := true
            end
    until q or (j = 8);
    end;
 
begin
for i :=  1 to  8 do a[ i] := true;
for i :=  2 to 16 do b[ i] := true;
for i := −7 to  7 do c[ i] := true;
try( 1, q);
if q then
    for i := 1 to 8 do write( x[ i]:4);
writeln
end.

popüler kültürde

  • Oyunda 7 Misafir , 8 Bulmaca: "Kraliçe'nin İkilemi" Stauf konağı oyun odasında olduğunu fiilen sekiz vezir bulmacası.
  • Profesör Layton ve Meraklı Köy oyununda 130. yapboz: "Too Many Queens 5"(クイーンの問題5 ) sekiz vezirli bir yapbozdur .

Ayrıca bakınız

Referanslar

daha fazla okuma

Dış bağlantılar