Sekiz vezir bulmacası

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şiDüzenle

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üDüzenle

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ı örneklerDüzenle

  • 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ümleriDüzenle

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.

Değişik n Değerleri için Çözüm SayılarıDüzenle

 
Ö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.

Bulmacayı Çözen C# console uygulaması kaynak koduDüzenle

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _8vezir
{
    class Program
    {
        static int[] myArray = new int[getNumber()];

        static char[] alphabe = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".ToCharArray();

        static int counter = myArray.Count();
        static void Main(string[] args)
        {
            List<String[]> ApproachList = new List<String[]>();

            for (int i = 0; i < System.Math.Pow(counter, counter); i++)
            {
                if (IsAllDifferentAndNotCross(myArray))
                {
                    int k = 0;
                    String[] tempArray = new String[counter];
                    foreach (int item in myArray)
                    {
                        k++;
                        tempArray[k - 1] = (k) + alphabe[item].ToString();
                        Console.Write(tempArray[k - 1] + "  ");

                    }

                    System.Console.WriteLine();

                    ApproachList.Add(tempArray.Clone() as String[]);

                }

                myArray[counter - 1]++;

                setArray();
            }

            System.Console.WriteLine("There is " + ApproachList.Count() + " different combination");

            System.Console.ReadLine();

        }

        static Boolean IsAllDifferentAndNotCross(int[] myArray)
        {
            for (int i = 0; i < counter; i++)
            {
                for (int j = i + 1; j < counter; j++)
                {
                    if (myArray[i] == myArray[j] || (myArray[i] - i) == (myArray[j] - j) || (myArray[i] + i) == (myArray[j] + j))
                        return false;
                }

            }

            return true;
        }

        static void setArray()
        {
            for (int j = 0; j < counter; j++)
            {
                if (myArray[j] == counter)
                {
                    if (j == 0)
                        break;
                    myArray[j] = 0;
                    myArray[j - 1]++;
                    break;
                }
            }

            foreach (int item in myArray)
                if (item == counter)
                    if (myArray[0] != counter)
                        setArray();
        }

        static int getNumber()
        {
            System.Console.WriteLine("Please insert number: ");
            return int.Parse(System.Console.ReadLine());
        }

    }
}

KaynakçaDüzenle

Dış bağlantılarDüzenle

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