8 |__|__|__|ql|__|__|__|__|= 7 |__|__|__|__|__|__|ql|__|= 6 |__|__|ql|__|__|__|__|__|= 5 |__|__|__|__|__|__|__|ql|= 4 |__|ql|__|__|__|__|__|__|= 3 |__|__|__|__|ql|__|__|__|= 2 |ql|__|__|__|__|__|__|__|= 1 |__|__|__|__|__|ql|__|__|= |``8 Vezir Bulmacasının örnek bir çözümü
8 Vezir Bulmacası, 8x8`lik bir satranç tahtasına 8 adet vezir 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`` a‰¥ 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
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ü
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:
- ``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 ``nye 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, a€¦).
- 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.
Sekiz Vezir Bulmacasının Çö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.|
Küçük Satranç Tahtası|=
| tright
|
|=
8 |__|__|__|ql|__|__|__|__|= 7 |__|__|__|__|__|__|ql|__|= 6 |__|__|ql|__|__|__|__|__|= 5 |__|__|__|__|__|__|__|ql|= 4 |__|ql|__|__|__|__|__|__|= 3 |__|__|__|__|ql|__|__|__|= 2 |ql|__|__|__|__|__|__|__|= 1 |__|__|__|__|__|ql|__|__|= |Eşsiz Çözüm - 1 |
Küçük Satranç Tahtası|=
| tright
|
|=
8 |__|__|__|__|ql|__|__|__|= 7 |__|ql|__|__|__|__|__|__|= 6 |__|__|__|ql|__|__|__|__|= 5 |__|__|__|__|__|__|ql|__|= 4 |__|__|ql|__|__|__|__|__|= 3 |__|__|__|__|__|__|__|ql|= 2 |__|__|__|__|__|ql|__|__|= 1 |ql|__|__|__|__|__|__|__|= |Eşsiz Çözüm - 2 |
Küçük Satranç Tahtası|=
| tright
|
|=
8 |__|__|__|ql|__|__|__|__|= 7 |__|ql|__|__|__|__|__|__|= 6 |__|__|__|__|__|__|ql|__|= 5 |__|__|ql|__|__|__|__|__|= 4 |__|__|__|__|__|ql|__|__|= 3 |__|__|__|__|__|__|__|ql|= 2 |__|__|__|__|ql|__|__|__|= 1 |ql|__|__|__|__|__|__|__|= |Eşsiz Çözüm - 3 |
Küçük Satranç Tahtası|=
| tright
|
|=
8 |__|__|__|ql|__|__|__|__|= 7 |__|__|__|__|__|ql|__|__|= 6 |__|__|__|__|__|__|__|ql|= 5 |__|__|ql|__|__|__|__|__|= 4 |ql|__|__|__|__|__|__|__|= 3 |__|__|__|__|__|__|ql|__|= 2 |__|__|__|__|ql|__|__|__|= 1 |__|ql|__|__|__|__|__|__|= |Eşsiz Çözüm - 4 |
|
Küçük Satranç Tahtası|=
| tright
|
|=
8 |__|__|ql|__|__|__|__|__|= 7 |__|__|__|__|__|ql|__|__|= 6 |__|__|__|__|__|__|__|ql|= 5 |ql|__|__|__|__|__|__|__|= 4 |__|__|__|ql|__|__|__|__|= 3 |__|__|__|__|__|__|ql|__|= 2 |__|__|__|__|ql|__|__|__|= 1 |__|ql|__|__|__|__|__|__|= |Eşsiz Çözüm - 5 |
Küçük Satranç Tahtası|=
| tright
|
|=
8 |__|__|__|__|ql|__|__|__|= 7 |__|__|ql|__|__|__|__|__|= 6 |__|__|__|__|__|__|__|ql|= 5 |__|__|__|ql|__|__|__|__|= 4 |__|__|__|__|__|__|ql|__|= 3 |ql|__|__|__|__|__|__|__|= 2 |__|__|__|__|__|ql|__|__|= 1 |__|ql|__|__|__|__|__|__|= |Eşsiz Çözüm - 6 |
Küçük Satranç Tahtası|=
| tright
|
|=
8 |__|__|__|__|ql|__|__|__|= 7 |__|__|__|__|__|__|ql|__|= 6 |__|__|__|ql|__|__|__|__|= 5 |ql|__|__|__|__|__|__|__|= 4 |__|__|ql|__|__|__|__|__|= 3 |__|__|__|__|__|__|__|ql|= 2 |__|__|__|__|__|ql|__|__|= 1 |__|ql|__|__|__|__|__|__|= |Eşsiz Çözüm - 7 |
Küçük Satranç Tahtası|=
| tright
|
|=
8 |__|__|__|ql|__|__|__|__|= 7 |ql|__|__|__|__|__|__|__|= 6 |__|__|__|__|ql|__|__|__|= 5 |__|__|__|__|__|__|__|ql|= 4 |__|__|__|__|__|ql|__|__|= 3 |__|__|ql|__|__|__|__|__|= 2 |__|__|__|__|__|__|ql|__|= 1 |__|ql|__|__|__|__|__|__|= |Eşsiz Çözüm - 8 |
|
Küçük Satranç Tahtası|=
| tright
|
|=
8 |__|__|ql|__|__|__|__|__|= 7 |__|__|__|__|__|ql|__|__|= 6 |__|__|__|ql|__|__|__|__|= 5 |ql|__|__|__|__|__|__|__|= 4 |__|__|__|__|__|__|__|ql|= 3 |__|__|__|__|ql|__|__|__|= 2 |__|__|__|__|__|__|ql|__|= 1 |__|ql|__|__|__|__|__|__|= |Eşsiz Çözüm - 9 |
Küçük Satranç Tahtası|=
| tright
|
|=
8 |__|__|__|__|__|ql|__|__|= 7 |__|ql|__|__|__|__|__|__|= 6 |__|__|__|__|__|__|ql|__|= 5 |ql|__|__|__|__|__|__|__|= 4 |__|__|__|ql|__|__|__|__|= 3 |__|__|__|__|__|__|__|ql|= 2 |__|__|__|__|ql|__|__|__|= 1 |__|__|ql|__|__|__|__|__|= |Eşsiz Çözüm - 10 |
Küçük Satranç Tahtası|=
| tright
|
|=
8 |__|__|__|ql|__|__|__|__|= 7 |__|__|__|__|__|__|ql|__|= 6 |ql|__|__|__|__|__|__|__|= 5 |__|__|__|__|__|__|__|ql|= 4 |__|__|__|__|ql|__|__|__|= 3 |__|ql|__|__|__|__|__|__|= 2 |__|__|__|__|__|ql|__|__|= 1 |__|__|ql|__|__|__|__|__|= |Eşsiz Çözüm - 11 |
Küçük Satranç Tahtası|=
| tright
|
|=
8 |__|__|__|__|__|ql|__|__|= 7 |__|__|__|ql|__|__|__|__|= 6 |__|__|__|__|__|__|ql|__|= 5 |ql|__|__|__|__|__|__|__|= 4 |__|__|__|__|__|__|__|ql|= 3 |__|ql|__|__|__|__|__|__|= 2 |__|__|__|__|ql|__|__|__|= 1 |__|__|ql|__|__|__|__|__|= |Eşsiz Çözüm - 12 |
Değişik ``n`` Değerleri için Çözüm Sayıları
" target="_blank"> 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. align="right" align="right" align="right" align="right" align="right" align="right" align="right" align="right" align="right" align="right" align="right" align="right" align="right" align="right" align="right" align="right" align="right" align="right" align="right" align="right" align="right" align="right" align="right" align="right" align="right" align="right"| ``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 | 357 |
| 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 | ? | ? |
n vezir bulmacası'''nın en son 2005 yılında ``n`` = 25 değeri için çözümü bulunmuştur. Ancak, çok yüksek hesaplama gücüne gereksinim duyulduğundan ``n`` = 26 için çözüm henüz bulunamamıştır.
Referanslar
- 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.
Linkler
- An Applet simulating the random-greedy solution for the n-queen problem
- MathWorld article
- Solutions to the 8-Queens Problem
- Walter Koster`s N-Queens Page
- Durango Bill`s N-Queens Page
- On-line Guide to Constraint Programming
- 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 Sequences
- N Queens solutions achieved on the NQueen@home Boinc project
- N-Queens solvers in many programming languages
- A Koalog Constraint Solver model
- Find your own solution
- J Somers N-Queen code
- Atari BASIC
- Genetic algorithms
- Haskell/Java hybrid
- Java
- Java
- Standard ML
- Integer Sequences
- Quirkasaurus` 8 Queens Solution
- LISP solution for N-Queens Problem
- ANSI C (recursive, congruence-free NxN-size queens problem solver with conflict heuristics)
- javascript solution for 8-Queens Problem
- 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 environment
- Conflict heuristics solution for the eight queens in a web based interactive classic BASIC environment
- A Simple PHP Solution
- 64 Kare 8 Vezir