Yap boz çözen program

[Erdem]

8 Bilmece

8 Bilmece problemini A* arama algoritmasını kullanarak çözen bir program yazın.

Problem : 8 bilmece problemi 1870'lerde Noyes Palmer Chapman tarafından icat edilen ve yaygınlaştırılan bir bilmecedir. Üzerinde 8 tane kare taş bulunan 3x3 bir tahta üzerinde  oynanır. Amacınız mümkün olduğunca az hamle yaparak taşları tekrad dizmektir. Boş kare içine yatay veya dikey olarak taşları kaydırabilirsiniz. Aşağıda başlangıçtan (solda) bitişe kadar (sağda) bir dizi geçerli hamle gösterilmektedir.

Kod Seç Genişlet


    1  3        1     3        1  2  3        1  2  3        1  2  3
4  2  5   =>   4  2  5   =>   4     5   =>   4  5      =>   4  5  6
7  8  6        7  8  6        7  8  6        7  8  6        7  8

başlangıç      1 sola          2 yukarı       5 sola         hedef


En iyi öncelikli arama - Şimdi , biz A * arama algoritması olarak da bilinen, genel bir yapay zeka yöntemi kullanan bir çözümü açıklayacağız. Bir tane arama düğümü tanımlıyoruz. Bu arama düğümü bir oyun tahtası, tahta o hale gelene kadar yapılan hamle sayısı ve bir önceki arama düğümünü içeriyor, İlkönce ilk arama düğümünü (tahtanın ilk hali, 0 hamle ve önceki arama düğümü null olacak şekilde)  öncelikli kuyruğa yerleştirin. Daha sonra öncelikli kuyruktan önceliği en düşük olan elemanı silin ve öncelikli kuyruğa komşu arama düğümlerini (bunlar bir hamlede kuyruktan çıkarılan arama düğümünden bulunabilmeli) ekleyin. Bu işleme kuyruktan çıkan düğümün içerdiği tahta hedef tahta olana kadar devam edin. Bu yaklaşımın başarısı arama düğümü için seçilen öncelik işlevinin başarısına bağlı. Biz iki tane öncelik işlevini inceleyeceğiz.

Hamming öncelik işlevi : Yanlış konumda bulunan taşların sayısı ve ek olarak geçerli arama düğümüne gelmek için yapılan hamle sayısı. Sizin de farkedeceğiniz üzere az sayıda yanlış konumda bulunan taşlardan oluşan bir arama düğümü çözüme daha yakındır. Arama düğümü seçerken de az hamleyle ulaşılmış bir arama düğümünü tercih ediyoruz.

Manhattan öncelik işlevi : Taşların bulunduğu konumdan, olmaları gereken konuma kadar olan Manhattan mesafelerinin (dikey ve yatay mesafe toplamı) toplamı, buna ek olarak geçerli arama düğümüne gelmek için yapılan hamle sayısı.

Örneğin aşağıdaki ilk arama düğümünün Manhattan ve Hamming öncelikleri sırasıyla 5 ve 10.

Kod Seç Genişlet



8  1  3        1  2  3     1  2  3  4  5  6  7  8    1  2  3  4  5  6  7  8
4     2        4  5  6     ----------------------    ----------------------
7  6  5        7  8        1  1  0  0  1  1  0  1    1  2  0  0  2  2  0  3

   ilk          hedef         Hamming = 5   0          Manhattan = 10   0


Kritik bir en iyileştirme - En iyi öncelikli aramanın can sıkıcı bir özelliği var. Aynı tahtaya ait arama düğümleri öncelikli kuyruğa birden fazla eklenebiliyor. İşe yaramayan arama düğümlerinin gereksiz olarak açılmasını önlemek için bir arama düğümünün komşularını eklerken eğer komşu bir önceki arama düğümüne eşitse onu eklemeyin.

Kod Seç Genişlet


8  1  3       8  1  3       8  1       8  1  3     8  1  3
4     2       4  2          4  2  3    4     2     4  2  5
7  6  5       7  6  5       7  6  5    7  6  5     7  6

önceki    arama düğümü      komşu      komşu       komşu
                                   (izin vermeyin)


Oyun ağacı : Yapılan hesaplamayı görebilmenin bir yolu oyun ağacını incelemekten geçiyor. Her arama düğümü oyun ağacında bir düğüme karşılık geliyor ve bu ağacın dalları komşu arama düğümlerine tekabül ediyor. Oyun ağacının kökünde ilk arama düğümü var. Beyazla gösterilen düğümler açılan düğümleri, diğer açılmamış dallar öncelikli kuyrukta saklanıyor. A* arama algoritması her adımda önceliği (masrafı) en düşük düğümü çıkarıyor ve gerekli işlemi yapıyor.



Çözülemeyen bulmacaların tespiti : Tüm tahtalar çözülemiyor. Bunlardan iki tanesini aşağıda görebilirsiniz.

Kod Seç Genişlet



1  2  3         1  2  3  4
4  5  6         5  6  7  8
8  7            9 10 11 12
                13 15 14
çözülemiyor
                çözülemiyor


Bu tür durumları tespit edebilmek için çözülebilirlik bakımından bulmacaların ikiye ayrıldığını düşünebilirsiniz. (i) Normal olarak çözülebilen tahtalar  (ii) Eğer ilk baştaki tahtada herhangi iki taşı (boş kare olan 0'ı taş olarak kabul etmiyoruz) yerdeğiştirdiğimizde çözüme ulaşan tahtalar. Bunu denemek için A* arama algoritmasını iki tahta --bir tanesi başlangıçtaki tahtayı diğeri tahtanın herhangi iki taşının yer değiştirilmesi sonucunda oluşan tahta-- üzerinde deneyin.  İki tahtadan biri çözüme ulaşacak.

Tahta ve Çözücü sınıfları : Tahta sınıfını aşağıdaki işlevleri gerçekleştirecek şekilde tasarlayın.

Kod Seç Genişlet


public class Tahta
{
    public Tahta(int[][] taşlar)           // N-N diziden oluşan taşlardan (taşlar[i][j] = i. satır ve j.sütünda
                                           // bulunan bir taş olacak şekilde) bir tahta oluşturun
    public int boyut()                     // tahta boyutu N
    public int hamming()                   // olması gerektiği yerde olmayan taş sayısı
    public int manhattan()                 // taşların hedef konuma olan Manhattan uzaklıklarının toplamı
    public boolean hedefMi()               // bu tahta hedef tahta mı?
    public Tahta ikiz()                    // herhangi iki taşın yerdeğiştirilmesiyle elde edilen tahta
    public boolean equals(Object diğer)    // bu tahta diğer tahtaya eşit mi?
    public Iterable<Tahta> komşular()      // tüm komşu tahtalar
    public String toString()               // bu tahtanın string (katar) olarak gösterimi

    public static void main(String[] args) // birim testleri (kendi denemeleriniz için)
}


Tahta sınıfının kurucu işlevinin N'e N boyunda, 0 ve N² - 1 arasında N² tamsayı içeren bir dizi aldığını kabul edebilirsiniz. 0 boş kareyi ifade ediyor.

Ayrıca çözücü sınıfını da aşağıdaki işlevleri yerine getirecek şekilde tasarlayın.

Kod Seç Genişlet


public class Çözücü
{
    public Çözücü(Tahta ilk)                // ilk tahta için bir çözüm bul(A* algoritmasını kullanarak)
    public boolean çözülebilirMi()          // ilk tahta çözülebilir mi?
    public int hamleler()                   // tahtayı çözmek için yapılması gereken en düşük hamle sayısı; eğer çözülemezse -1
    public Iterable<Tahta> çözüm()          // en kısa çözümü gösteren tahta dizilimi; eğer çözülemiyorsa null döndürmeli
    public static void main(String[] args)  // bulmacayı çöz (aşağıda bulabilirsiniz)
}

A* algoritmasını gerçekleştirmek için öncelikli kuyruk olarak MinPQ.java dosyasını kullanabilirsiniz.

Çözücü test programı : Bir bulmacayı (komut satırında belirtilen) kütükten okuyup çözümü ekrana yazan aşağıdaki test programını kullanabilirsiniz.

Kod Seç Genişlet

public static void main(String[] args)
{
    // ilk tahtayı bir kütükten oluştur
    In giriş = new In(args[0]);
    int N = giriş.readInt();
    int[][] taşlar = new int[N][N];
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            taşlar[i][j] = giriş.readInt();
    Tahta ilk = new Tahta(taşlar);

    // bulmacayı çöz
    Çözücü çözücü = new Çözücü(ilk);

    // çözümü standart çıkışa yaz
    if (!çözücü.çözülebilirMi())
        StdOut.println("Çözüm yok");
    else
{
        StdOut.println("En düşük hamle sayısı = " + çözücü.hamleler());
        for (Tahta tahta : çözücü.çözüm())
            StdOut.println(tahta);
    }
}

Girdi çıktı biçemleri : Bir tahtanın giriş çıkış biçemi en üstte tahta boyutunu gösterecek N ve N'e N'lik tahtayı gösterecek şekilde olmalı. Örneğin,

Kod Seç Genişlet


% more bilmece04.txt
3
0  1  3
4  2  5
7  8  6

% java Çözücü bilmece04.txt
En düşük hamle sayısı = 4

3
0  1  3
4  2  5
7  8  6

3
1  0  3
4  2  5
7  8  6

3
1  2  3
4  0  5
7  8  6

3
1  2  3
4  5  0   
7  8  6

3
1  2  3
4  5  6
7  8  0
% more bilmece3x3-cozumuyok.txt
3
1  2  3
4  5  6
8  7  0

% java Çözücü bilmece3x3-cozumuyok.txt
Çözüm yok


Yazdığınız program N'e N boyutunda (2 ≤ N < 128) tüm tahtalar için, bazılarını çözmek zaman alsa ve yavaş çalışsa bile doğru olarak çalışabilmeli.

Yazdığınız programı test etmek için 8bilmece.zip kütüğünü indirerek örnek bilmeceler üzerinde denemeler yapabilirsiniz.

[ahmet_matematikci]

Matris sıralama algoritması )

[bugra9]

Kod Seç Genişlet


// Oyun Kuralı tanımlanıyor
var kural = [
  [1, 3],
  [0, 2, 4],
  [1, 5],
  [0, 4, 6],
  [1, 3, 5, 7],
  [2, 4, 8],
  [3, 7],
  [4, 6, 8],
  [5, 7]
];
// Hedef tanımlanıyor
var hedef = [1, 2, 3, 4, 5, 6, 7, 8, 0];
// Kural ve hedefe göre bulmaca oluşturuluyor. Satır sayısına göre gösterim ayarlanıyor
var satir = 3;
var bulmaca = new BulmacaCozucu(kural, hedef, satir);

// Çözdürmek istediğimiz bulmacayı çözdürüyoruz.
var baslangic = [0, 1, 3, 4, 2, 5, 7, 8, 6];
bulmaca.coz(baslangic);


// Çekirdek
function BulmacaCozucu(kural, hedef, satir) {
  this.kural = kural;
  this.hedef = hedef;
  this.satir = satir;

  this.coz = function(baslangic) {
    baslangic[this.hedef.length] = this.puanla(baslangic);
    this.coz2(baslangic, this.kural, -1);
    this.yaz(baslangic);
  };

  // Boşluğun nerede olduğunu bulur ve konumunu döndürür
  this.konumBul = function(dizi) {
    for (var i = 0; i < this.hedef.length; ++i)
      if (dizi[i] == 0)
        return i;
    return -1;
  };

  // Verilen matrisin hedef matris ile ne kadar benzer olduğunu döndürür
  this.puanla = function(dizi) {
    var puan = 0;
    for (var i = 0; i < this.hedef.length; ++i)
      if (dizi[i] == this.hedef[i])
        ++puan;
    return puan;
  };

  this.coz2 = function(dizi, kural, eskiKonum) {
    if (dizi[this.hedef.length] == this.hedef.length)
      return true;
    var konum = this.konumBul(dizi);
    var geciciDizi = Array();
    for (var i in kural[konum]) {
      var e = kural[konum][i];
      if (e === eskiKonum)
        continue;

      var i2 = geciciDizi.length + 1;
      geciciDizi[i2] = dizi.slice();
      geciciDizi[i2][konum] = dizi[e];
      geciciDizi[i2][e] = 0;
      geciciDizi[i2][this.hedef.length] = this.puanla(geciciDizi[i2]);
    }
    geciciDizi.sort(function(a, b) {
      return a[a.length - 1] - b[b.length - 1]
    });
    for (var i in geciciDizi)
      if (geciciDizi[i][this.hedef.length] > dizi[this.hedef.length])
        if (this.coz2(geciciDizi[i], kural, konum)) {
          this.yaz(geciciDizi[i]);
          return true;
        }

    return false;
  };
  this.yaz = function(dizi) {
    var cikti = "<table><tr>";
    for (var i in dizi.slice(0, this.hedef.length)) {
      var deger = dizi[i];
      if (deger === 0)
        deger = '';
      cikti += '<td>' + deger + '</td>';
      if ((i*1 + 1) % this.satir == 0)
        cikti += '</tr><tr>';
    }
    cikti += '</tr>';
    $('body').prepend(cikti);

  };
}



Canlı canlı denemek için,
https://jsfiddle.net/bmvtkreb/3/

[Erdem]

@Buğra teşekkürler.

Kuralları nasıl tespit ediyoruz acaba? Örneğin yapbozumuz 4x4 ya da 5x5 olsaydı kuralları nasıl belirleyecektik.

[bugra9]

0 1 2
3 4 5
6 7 8

şeklinde numaralandırdığımızı düşünelim.
- Eğer boşluk 0 ise 1 ve 3'e hareket edebilir.
kural[0] = [1,3]
- Eğer boşluk 1 ise 0, 2 ve 4'e hareket edebilir. 
kural[1] = [0, 2, 4]

Bu şekilde tüm elemanlar için doldurarak kuralı tanımlamış oluyoruz.

Ben kodu yazdığımda senin örneğini denedim ve çalıştığını gördüm. Başka örneklerle test etmedim. Belki karmaşık verilerle ya da daha yüksek boyutlularda doğru çalışmaz ve kodun geliştirilmesi gerekebilir.

Gerçi yazmışken başka bir örnek ile deneyeyim. 4-4 boyutlu test ettim ve düzgün çalışıyor.
https://jsfiddle.net/bmvtkreb/2/

NOT: kodda düzenlemeler yaptım.

[Erdem]

@Buğra tebrikler! Ben de denedim bazı bulmacaları çözebiliyor.

Tabi bu problem aslında bir yapay zeka problemi olduğu için zor bulmacalar da var. Örneğin:

Kod Seç Genişlet


4
2  6  4  8
1 10  7  3
5 13 11 15
12 14  9  0


Kod Seç Genişlet

4
2  4  1  6
12 13  5  3
14  7 11 15
0  9  8 10


Şu bulmacanın da özellikle zor olduğunu söylemişler.

Kod Seç Genişlet

4
3 14  2  4
9  1  7  8
0 12  6 10
13  5 11 15


Ama baktım bunu da çok kısa sürede bazıları çözmüş.

Benim yaptığım program da henüz basit bulmacaları çözebiliyor. En iyileştirme yapmam gerekecek.

Kod Seç Genişlet

$ more puzzle4x4-03.txt
4
1  2  3  4
5  6  0  8
9 10  7 12
13 14 11 15


Kod Seç Genişlet

$ java-algs4 Solver puzzle4x4-09.txt
4
2  3  4  0
1  6  7  8
5 10 11 12
9 13 14 15

4
2  3  0  4
1  6  7  8
5 10 11 12
9 13 14 15

4
2  0  3  4
1  6  7  8
5 10 11 12
9 13 14 15

4
0  2  3  4
1  6  7  8
5 10 11 12
9 13 14 15

4
1  2  3  4
0  6  7  8
5 10 11 12
9 13 14 15

4
1  2  3  4
5  6  7  8
0 10 11 12
9 13 14 15

4
1  2  3  4
5  6  7  8
9 10 11 12
0 13 14 15

4
1  2  3  4
5  6  7  8
9 10 11 12
13  0 14 15

4
1  2  3  4
5  6  7  8
9 10 11 12
13 14  0 15

4
1  2  3  4
5  6  7  8
9 10 11 12
13 14 15  0



[bugra9]

Sağol.

Aslında olay çok başka. Deneme yanılma yapma ve bu olayı daha kısa sürede tamamlamasına çalışmak dışında sanki daha net bir çözüm varmış gibi geliyor. Hani bu şekilde ne yaparsan yap, çalışma zamanı tüm olasılıkları denemekten daha az olmayacak.

Hiç denemedim ama dinamik programlama yöntemiyle bu işlem çok çok az sürede halledilebilir gibi duruyor. İlk dizilim ne kadar zor olursa olsun yine de çok az süre içerisinde bitirilebilir. Sadece arasındaki matematiksel ilişkiyi tanımlasan yeter.

[Erdem]

@Buğra soruyu yazıyorum. Henüz bitmedi programı yazmak sanırım çevirmekten daha kolay oluyor 

Şimdilik çevirdiğim kısmı gönderiyorum.


Mesaj tekrarı yüzünden mesajınız birleştirildi. Bu mesajın gönderim tarihi : 13 Mart 2016 - 09:20:07
Soruyu tamamladım. Aslında buradaki örnek Java ama C, C++, D ya da herhangi bir dilde çözümleri gönderebilirsiniz.