Sekiz vezir bulmacası

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.

Tarihi

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]

Çözüm yöntemi

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 (8⁸) düzeyine indirilebilir.

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

n sayısını 12'ye böl. Kalanı aklında tut. (n sayısı sekiz vezir bulmacasında 8'dir).
2'den n sayısına kadar olan bütün çift sayıları sırayla yaz.
Eğer kalan 3 ya da 9 ise 2'yi listenin en sonuna koy.
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, …).
Eğer kalan 2 ise, 1 ile 3'ün yerlerini değiştir ve 5'i listenin en sonuna al.
Eğer kalan 3 ya da 9 ise, 1 ve 3'ü listenin sonuna al.
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

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.

Çözümleri

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.

Eşsiz Çözüm - 1

Eşsiz Çözüm - 2

Eşsiz Çözüm - 3

Eşsiz Çözüm - 4

Eşsiz Çözüm - 5

Eşsiz Çözüm - 6

Eşsiz Çözüm - 7

Eşsiz Çözüm - 8

Eşsiz Çözüm - 9

Eşsiz Çözüm - 10

Eşsiz Çözüm - 11

Eşsiz Çözüm - 12

Değişik n değerleri için çözüm sayıları

Ö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	29.363.495.934.315.694	234.907.967.154.122.528

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.

Kaynakça

^ O.-J. Dahl, E. W. Dijkstra, C. A. R. Hoare Structured Programming, Academic Press, London, 1972 ISBN 0-12-200550-3 72-82 sayları arasında Dijkstra'nın 8 Vezir bulmacası için önerdiği çözüm bulunmaktadır.

Dış bağlantılar

An Applet simulating the random-greedy solution for the n-queen problem
MathWorld article3 Temmuz 2019 tarihinde Wayback Machine sitesinde arşivlendi.
Solutions to the 8-Queens Problem
Walter Koster's N-Queens Page
Durango Bill's N-Queens Page
On-line Guide to Constraint Programming14 Şubat 2008 tarihinde Wayback Machine sitesinde arşivlendi.
n-Queens in C++; Implementation & analysis of several heuristics to speed up solving the n-queens problem
NQueen@home Boinc project

Çözüm İçeren Bağlantılar

N Queens solutions on Sloane's On-Line Encyclopedia of Integer Sequences13 Mayıs 2001 tarihinde Wayback Machine sitesinde arşivlendi.
N Queens solutions achieved on the NQueen@home Boinc project
N-Queens solvers in many programming languages
A Koalog Constraint Solver model20 Şubat 2008 tarihinde Wayback Machine sitesinde arşivlendi.
Find your own solution12 Mart 2008 tarihinde Wayback Machine sitesinde arşivlendi.
J Somers N-Queen code
Atari BASIC3 Mart 2008 tarihinde Wayback Machine sitesinde arşivlendi.
Genetic algorithms2 Nisan 2008 tarihinde Wayback Machine sitesinde arşivlendi.
Haskell/Java hybrid
Java8 Mart 2008 tarihinde Wayback Machine sitesinde arşivlendi.
Java2 Nisan 2008 tarihinde Wayback Machine sitesinde arşivlendi.
Standard ML12 Mart 2008 tarihinde Wayback Machine sitesinde arşivlendi.
Integer Sequences
Quirkasaurus' 8 Queens Solution
LISP solution for N-Queens Problem15 Nisan 2008 tarihinde Wayback Machine sitesinde arşivlendi.
ANSI C (recursive, congruence-free NxN-size queens problem solver with conflict heuristics)20 Şubat 2008 tarihinde Wayback Machine sitesinde arşivlendi.
javascript solution for 8-Queens Problem^{[ölü/kırık bağlantı]}
Abhinanth's Simple Javascript application for quick view - chess 8 queen problem
Brute-force solution for eight queens in a web based interactive classic BASIC environment17 Mayıs 2008 tarihinde Wayback Machine sitesinde arşivlendi.
Conflict heuristics solution for the eight queens in a web based interactive classic BASIC environment9 Şubat 2008 tarihinde Wayback Machine sitesinde arşivlendi.
A Simple PHP Solution19 Eylül 2008 tarihinde Wayback Machine sitesinde arşivlendi.
Standart C Programlama Dili / Bir Örnek—Sekiz Vezir Problemi17 Ekim 2008 tarihinde Wayback Machine sitesinde arşivlendi.

[1] O.-J. Dahl, E. W. Dijkstra, C. A. R. Hoare Structured Programming, Academic Press, London, 1972 ISBN 0-12-200550-3 72-82 sayları arasında Dijkstra'nın 8 Vezir bulmacası için önerdiği çözüm bulunmaktadır.

[1]