Sekiz vezir bulmacası

Vikipedi, özgür ansiklopedi
Atla: kullan, ara
Chess zhor 26.png
Chess zver 26.png
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 26.png
Chess zhor 26.png
8 Vezir Bulmacası'nın örnek bir çözümü


8 Vezir Bulmacası, 8x8'lik bir satranç tahtasına 8 adet vezirin hiçbiri olağan vezir hamleleriyle birbirini alamayacak biçimde yerleştirmesi sorunudur. Her bir vezirin konumunun diğer bir vezire saldırmasına engel olması için hiçbir vezir başka bir vezirle aynı satıra, aynı kolona ya da aynı köşegene yerleştirilemez. 8 Vezir Bulmacası daha genel olan n Vezir Bulmacası'nın özel bir durumudur.

n Vezir Bulmacası, n ≥ 4 için n×n boyutunda bir satranç tahtasına n adet vezirin birbirini alamayacak biçimde yerleştirilmesi sorunudur.

Bulmacanın Geçmişi[değiştir | kaynağı değiştir]

8 Vezir Bulmacası (ve genel haliyle n Vezir Bulmacası) ilk olarak 1848 yılında satranç oyuncusu Max Bezzel tarafından ortaya atılmış ve yıllar içinde Gauss ve Georg Cantor gibi pek çok matematikçi tarafından incelenmiştir. İlk çözüm Franz Nauck tarafından 1850'de ortaya atılmıştır. Franz Nauck aynı zamanda bulmacayı nxn'lik bir tahta üzerinde uygulanmak üzere n vezir bulmacası haline getirmiştir.

Edsger Dijkstra 1972 yılında sekiz vezir bulmacası sorununu yapısal programlama adını verdiği yöntemin gücünü göstermek için yarattığı bir algoritmada kullanmıştır. 1

Bulmacanın Çözümü[değiştir | kaynağı değiştir]

Toplamda 283.274.583.,552 (64x63x..x58x57/8!) olasılık bulunmasına karşın yalnızca 92 çözüm bulunduğu için bulmacanın çözümü yüksek miktarda hesaplama gerektirir. Gereksiz yere yapılan hesaplamaların sayısını azaltmak için bazı kısayolların kullanılması mümkündür. Örneğin her bir satırda ya da sütunda tek bir vezirin olabileceği kısıtı uygulanarak çözüm sayısı 16.777.216 (88) düzeyine indirilebilir.

Aşağıdaki adımlar sırasıyla izlenerek n vezir bulmacası'nın bir çözümü bulunabilir:

  1. n sayısını 12'ye böl. Kalanı aklında tut. (n sayısı sekiz vezir bulmacasında 8'dir).
  2. 2'den n sayısına kadar olan bütün çift sayıları sırayla yaz.
  3. Eğer kalan 3 ya da 9 ise 2'yi listenin en sonuna koy.
  4. 1'den n'ye kadar olan tek sayıları listeye ekle; eğer kalan sekizse her bir çiftin kendi arasında yerlerini değiştir (örnek: 3, 1, 7, 5, 11, 9, …).
  5. Eğer kalan 2 ise, 1 ile 3'ün yerlerini değiştir ve 5'i listenin en sonuna al.
  6. Eğer kalan 3 ya da 9 ise, 1 ve 3'ü listenin sonuna al.
  7. Ortaya çıkan listedeki her bir sayı ilgili için ilgili kolonun listedeki sayının gösterdiği satırına bir vezir koy. Örneğin listedeki ilk sayı 2 ise satranç tahtasında ilk kolonun ikinci sırasına bir vezir konmalıdır.

Bazı örnekler[değiştir | kaynağı değiştir]

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

Sekiz Vezir Bulmacasının Çözümleri[değiştir | kaynağı değiştir]

Sekiz vezir bulmacasının 92 ayrı çözümü vardır. Ancak bu çözümlerin çoğu birbirinden yalnızca döndürme ve yansıma gibi simetri işlemleriyle üretilebilir. Bu nedenle, eğer simetriden doğan bu fazla çözümler birleştirilip tek çözüm olarak sayılırsa, bulmacanın aslında aşağıda gösterilen 12 eşsiz çözümü vardır.

Chess zhor 22.png
Chess zver 22.png a8 __ b8 __ c8 __ d8 ql e8 __ f8 __ g8 __ h8 __ Chess zver 22.png
a7 __ b7 __ c7 __ d7 __ e7 __ f7 __ g7 ql h7 __
a6 __ b6 __ c6 ql d6 __ e6 __ f6 __ g6 __ h6 __
a5 __ b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 ql
a4 __ b4 ql c4 __ d4 __ e4 __ f4 __ g4 __ h4 __
a3 __ b3 __ c3 __ d3 __ e3 ql f3 __ g3 __ h3 __
a2 ql b2 __ c2 __ d2 __ e2 __ f2 __ g2 __ h2 __
a1 __ b1 __ c1 __ d1 __ e1 __ f1 ql g1 __ h1 __
Chess zhor 22.png
Eşsiz Çözüm - 1
Chess zhor 22.png
Chess zver 22.png a8 __ b8 __ c8 __ d8 __ e8 ql f8 __ g8 __ h8 __ Chess zver 22.png
a7 __ b7 ql c7 __ d7 __ e7 __ f7 __ g7 __ h7 __
a6 __ b6 __ c6 __ d6 ql e6 __ f6 __ g6 __ h6 __
a5 __ b5 __ c5 __ d5 __ e5 __ f5 __ g5 ql h5 __
a4 __ b4 __ c4 ql d4 __ e4 __ f4 __ g4 __ h4 __
a3 __ b3 __ c3 __ d3 __ e3 __ f3 __ g3 __ h3 ql
a2 __ b2 __ c2 __ d2 __ e2 __ f2 ql g2 __ h2 __
a1 ql b1 __ c1 __ d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 22.png
Eşsiz Çözüm - 2
Chess zhor 22.png
Chess zver 22.png a8 __ b8 __ c8 __ d8 ql e8 __ f8 __ g8 __ h8 __ Chess zver 22.png
a7 __ b7 ql c7 __ d7 __ e7 __ f7 __ g7 __ h7 __
a6 __ b6 __ c6 __ d6 __ e6 __ f6 __ g6 ql h6 __
a5 __ b5 __ c5 ql d5 __ e5 __ f5 __ g5 __ h5 __
a4 __ b4 __ c4 __ d4 __ e4 __ f4 ql g4 __ h4 __
a3 __ b3 __ c3 __ d3 __ e3 __ f3 __ g3 __ h3 ql
a2 __ b2 __ c2 __ d2 __ e2 ql f2 __ g2 __ h2 __
a1 ql b1 __ c1 __ d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 22.png
Eşsiz Çözüm - 3
Chess zhor 22.png
Chess zver 22.png a8 __ b8 __ c8 __ d8 ql e8 __ f8 __ g8 __ h8 __ Chess zver 22.png
a7 __ b7 __ c7 __ d7 __ e7 __ f7 ql g7 __ h7 __
a6 __ b6 __ c6 __ d6 __ e6 __ f6 __ g6 __ h6 ql
a5 __ b5 __ c5 ql d5 __ e5 __ f5 __ g5 __ h5 __
a4 ql b4 __ c4 __ d4 __ e4 __ f4 __ g4 __ h4 __
a3 __ b3 __ c3 __ d3 __ e3 __ f3 __ g3 ql h3 __
a2 __ b2 __ c2 __ d2 __ e2 ql f2 __ g2 __ h2 __
a1 __ b1 ql c1 __ d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 22.png
Eşsiz Çözüm - 4
Chess zhor 22.png
Chess zver 22.png a8 __ b8 __ c8 ql d8 __ e8 __ f8 __ g8 __ h8 __ Chess zver 22.png
a7 __ b7 __ c7 __ d7 __ e7 __ f7 ql g7 __ h7 __
a6 __ b6 __ c6 __ d6 __ e6 __ f6 __ g6 __ h6 ql
a5 ql b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 __
a4 __ b4 __ c4 __ d4 ql e4 __ f4 __ g4 __ h4 __
a3 __ b3 __ c3 __ d3 __ e3 __ f3 __ g3 ql h3 __
a2 __ b2 __ c2 __ d2 __ e2 ql f2 __ g2 __ h2 __
a1 __ b1 ql c1 __ d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 22.png
Eşsiz Çözüm - 5
Chess zhor 22.png
Chess zver 22.png a8 __ b8 __ c8 __ d8 __ e8 ql f8 __ g8 __ h8 __ Chess zver 22.png
a7 __ b7 __ c7 ql d7 __ e7 __ f7 __ g7 __ h7 __
a6 __ b6 __ c6 __ d6 __ e6 __ f6 __ g6 __ h6 ql
a5 __ b5 __ c5 __ d5 ql e5 __ f5 __ g5 __ h5 __
a4 __ b4 __ c4 __ d4 __ e4 __ f4 __ g4 ql h4 __
a3 ql b3 __ c3 __ d3 __ e3 __ f3 __ g3 __ h3 __
a2 __ b2 __ c2 __ d2 __ e2 __ f2 ql g2 __ h2 __
a1 __ b1 ql c1 __ d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 22.png
Eşsiz Çözüm - 6
Chess zhor 22.png
Chess zver 22.png a8 __ b8 __ c8 __ d8 __ e8 ql f8 __ g8 __ h8 __ Chess zver 22.png
a7 __ b7 __ c7 __ d7 __ e7 __ f7 __ g7 ql h7 __
a6 __ b6 __ c6 __ d6 ql e6 __ f6 __ g6 __ h6 __
a5 ql b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 __
a4 __ b4 __ c4 ql d4 __ e4 __ f4 __ g4 __ h4 __
a3 __ b3 __ c3 __ d3 __ e3 __ f3 __ g3 __ h3 ql
a2 __ b2 __ c2 __ d2 __ e2 __ f2 ql g2 __ h2 __
a1 __ b1 ql c1 __ d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 22.png
Eşsiz Çözüm - 7
Chess zhor 22.png
Chess zver 22.png a8 __ b8 __ c8 __ d8 ql e8 __ f8 __ g8 __ h8 __ Chess zver 22.png
a7 ql b7 __ c7 __ d7 __ e7 __ f7 __ g7 __ h7 __
a6 __ b6 __ c6 __ d6 __ e6 ql f6 __ g6 __ h6 __
a5 __ b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 ql
a4 __ b4 __ c4 __ d4 __ e4 __ f4 ql g4 __ h4 __
a3 __ b3 __ c3 ql d3 __ e3 __ f3 __ g3 __ h3 __
a2 __ b2 __ c2 __ d2 __ e2 __ f2 __ g2 ql h2 __
a1 __ b1 ql c1 __ d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 22.png
Eşsiz Çözüm - 8
Chess zhor 22.png
Chess zver 22.png a8 __ b8 __ c8 ql d8 __ e8 __ f8 __ g8 __ h8 __ Chess zver 22.png
a7 __ b7 __ c7 __ d7 __ e7 __ f7 ql g7 __ h7 __
a6 __ b6 __ c6 __ d6 ql e6 __ f6 __ g6 __ h6 __
a5 ql b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 __
a4 __ b4 __ c4 __ d4 __ e4 __ f4 __ g4 __ h4 ql
a3 __ b3 __ c3 __ d3 __ e3 ql f3 __ g3 __ h3 __
a2 __ b2 __ c2 __ d2 __ e2 __ f2 __ g2 ql h2 __
a1 __ b1 ql c1 __ d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 22.png
Eşsiz Çözüm - 9
Chess zhor 22.png
Chess zver 22.png a8 __ b8 __ c8 __ d8 __ e8 __ f8 ql g8 __ h8 __ Chess zver 22.png
a7 __ b7 ql c7 __ d7 __ e7 __ f7 __ g7 __ h7 __
a6 __ b6 __ c6 __ d6 __ e6 __ f6 __ g6 ql h6 __
a5 ql b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 __
a4 __ b4 __ c4 __ d4 ql e4 __ f4 __ g4 __ h4 __
a3 __ b3 __ c3 __ d3 __ e3 __ f3 __ g3 __ h3 ql
a2 __ b2 __ c2 __ d2 __ e2 ql f2 __ g2 __ h2 __
a1 __ b1 __ c1 ql d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 22.png
Eşsiz Çözüm - 10
Chess zhor 22.png
Chess zver 22.png a8 __ b8 __ c8 __ d8 ql e8 __ f8 __ g8 __ h8 __ Chess zver 22.png
a7 __ b7 __ c7 __ d7 __ e7 __ f7 __ g7 ql h7 __
a6 ql b6 __ c6 __ d6 __ e6 __ f6 __ g6 __ h6 __
a5 __ b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 ql
a4 __ b4 __ c4 __ d4 __ e4 ql f4 __ g4 __ h4 __
a3 __ b3 ql c3 __ d3 __ e3 __ f3 __ g3 __ h3 __
a2 __ b2 __ c2 __ d2 __ e2 __ f2 ql g2 __ h2 __
a1 __ b1 __ c1 ql d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 22.png
Eşsiz Çözüm - 11
Chess zhor 22.png
Chess zver 22.png a8 __ b8 __ c8 __ d8 __ e8 __ f8 ql g8 __ h8 __ Chess zver 22.png
a7 __ b7 __ c7 __ d7 ql e7 __ f7 __ g7 __ h7 __
a6 __ b6 __ c6 __ d6 __ e6 __ f6 __ g6 ql h6 __
a5 ql b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 __
a4 __ b4 __ c4 __ d4 __ e4 __ f4 __ g4 __ h4 ql
a3 __ b3 ql c3 __ d3 __ e3 __ f3 __ g3 __ h3 __
a2 __ b2 __ c2 __ d2 __ e2 ql f2 __ g2 __ h2 __
a1 __ b1 __ c1 ql d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 22.png
Eşsiz Çözüm - 12

Değişik n Değerleri için Çözüm Sayıları[değiştir | kaynağı değiştir]

Özyinelemeli bir algoritmayla Sekiz Vezir Bulmacası'nın Çözümü

Aşağıdaki tablo değişik n değerleri için çözüm sayılarını göstermektedir.

n Eşsiz Çözüm Sayısı Ayrı Çözüm Sayısı
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 ? ?

Not: 6×6'lık bir satranç tahtasında bulunan çözüm sayısının 5×5 boyutundaki bir satranç tahtasında bulunan çözüm sayısından az oluşu dikkat çekicidir.

n vezir bulmacası'nın en son n = 26 değeri için çözümü bulunmuştur. Ancak, çok yüksek hesaplama gücüne gereksinim duyulduğundan n = 27 için çözüm henüz bulunamamıştır.

Kaynakça[değiştir | kaynağı değiştir]

Dış bağlantılar[değiştir | kaynağı değiştir]

Çözüm İçeren Bağlantılar[değiştir | kaynağı değiştir]