Schiebepuzzle


Hier eine neue Aufgabe von The Daily WTF: Schreibe ein Programm, das die 3×3 Version eines Schiebepuzzles lösen kann. Achtung: Die Hälfte aller „Konfigurationen“ ist unlösbar, wenn ihr also eine Minute auf die Lösung gewartet habt, wird das bestimmt nichts mehr. In so einem Fall hat es bisher bei mir geholfen, die erste und dritte Zahl zu vertauschen (aber ich weiß nicht, ob das immer funktioniert).

//Scala 2.8
object slide {

  case class Pos(pos:String) {
    def neighbors = {
      val p = pos.indexOf('0');  val x = p % 3;  val y = p / 3
      def swap(xn:Int, yn:Int):Option[Pos] =
      if((xn+1) % 4 == 0 || (yn+1) % 4 == 0) None
      else {
        val tiles = pos.toArray
        val temp = tiles(p); tiles(p) = tiles(xn+3*yn); tiles(xn+3*yn) = temp
        Some(Pos(new String(tiles)))
      }
      List(swap(x-1,y), swap(x+1,y), swap(x,y-1),swap(x,y+1)).flatMap(s => s)
    }
  }

  def solve(p1:Pos, p2:Pos = Pos("123456780")):List[Pos] = {

    def hull(list:List[Set[Pos]]):List[Set[Pos]] = {
      val second = if (list.tail.isEmpty) Set[Pos]() else list.tail.head
      list.head.foldLeft(Set[Pos]())((s,p) => s ++ p.neighbors.filter{
          n => ! list.head.contains(n) && ! second.contains(n)}) :: list
    }

    def reconstructPath(path:List[Pos], hulls:List[Set[Pos]]):List[Pos] =
      hulls match {
         case Nil => path
         case head :: tail => reconstructPath(head.find(
                          path.head.neighbors.contains(_)).get :: path, tail)
    }

    def solve(list1:List[Set[Pos]], list2:List[Set[Pos]]):List[Pos] =
    list1.head.find(list2.head.contains(_)) match {
      case None =>  val lenIsEqual = list1.length == list2.length
        solve(if (lenIsEqual) hull(list1) else list1,
              if (lenIsEqual) list2 else hull(list2))
      case Some(link) =>  
        reconstructPath(List(link),list1.tail) :::
        reconstructPath(List(link),list2.tail).reverse.tail
    }
    solve(List(Set(p1)),List(Set(p2)))
  }

  def main(args:Array[String]) {
    val time = System.currentTimeMillis
    solve(Pos("738046512")).foreach(println)
    println("" + (System.currentTimeMillis-time) + "ms")
  }

}

Der Code ist etwas komplizierter, als er sein müsste, denn er sucht gleichzeitig von der Start- wie von der Endposition aus. Dabei wird in jedem Schritt eine neue „Hülle“ um die Start- oder Endposition gelegt, und wenn sich beide Hüllen „berühren“, werden von der Berührungspostion (die im Programm „link“ heißt) aus die Wege zu den Ausgangspositionen zurückgerechnet und die beiden „Pfade“ aneinandergeklebt und zurückgegeben.

Die Details: Zuerst einmal benötigen wir eine Klasse zur Beschreibung einer Position. Dort können wir auch gleich die neighbors-Methode unterbringen, die alle Positionen auflistet, die mit einem Zug erreicht werden können. Die Position selbst wird durch einen String repräsentiert, der einfach alle drei Zeilen aneinanderreiht – ich schätze, ein 3×3 Array wäre hier mit Kanonen auf Spatzen geschossen.

Die neighbors-Methode sieht schwieriger aus, als sie ist: zuerst suchen wir die Position der 0 (die für das leere Feld steht). Dann berechnen wir durch Vertauschung alle 4 Nachbarpositionen, die allerdings nicht immer „erlaubt“ sind (der Test (xn+1) % 4 == 0 ist übrigens nur eine Abkürzung für xn == -1 || xn == 3). swap liefert deshalb eine Option[Pos] zurück, die bei ungültigen Positionen None ist. Hat man eine Kollektion von Optionen, kann man diese durch flatMap „aussortieren“ lassen, so dass nur noch die gültigen Werte übrigbleiben. Man kann hier übrigens sehen, dass swap auch auf die „umgebenden“ Variablen (hier p) Zugriff hat.

Die solve Methode macht nicht viel, sie deligiert die Arbeit an ihre innere Version. Diese arbeitet mit zwei Listen der bereits erwähnten Hüllen. Berühren sich diese, muss man nur noch den Pfad zurückrechnen (was reconstructPath übernimmt, man muss die Teilpfade nur noch geeignet aneinanderkleben), ansonsten wird mit hull eine neue Hülle hinzugefügt (und zwar abwechselnd um die Start- oder Endposition).

Übrigens besitzt die äußere solve-Methode ein Default-Argument – eines der neuen Features von Scala 2.8, über das ich mich besonders freue.

Die Methode hull nimmt die „äußerste“ Hülle, berechnet alle ihrer Nachbarpositionen, filtert alle schon bekannten (das sind die, die schon in der äußersten oder der darunterliegenden Hülle vorkommen) heraus und gibt die verbleibenden Positionen als neue Außenhülle zurück.

reconstructPath geht die Hüllen von außen nach innen durch, und baut dabei schrittweise den Pfad auf, der zur „Berührungsposition“ geführt hat.

Auf meinem Rechner dauert eine Suche 0.3 bis 0.5 Sekunden, was ich für akzeptabel halte – zumal der Algorithmus ja auch noch garantiert eine kürzeste Zugfolge liefert.

Scala nimmt einem die Arbeit nicht ab, einen geeigneten Algorithmus zu finden, aber wenn man eine ungefähre Idee hat, wird es einem leicht gemacht, diese zu strukturieren. Ich habe wirklich nicht viel an diesem Beispiel herumgewurstelt, sondern mich einfach Schritt für Schritt vorangetastet. Man sieht hier übrigens auch, wie nützlich es ist, kleine und selbständige Methoden zu benutzen: Sowohl hull wie auch reconstructPath werden mehrfach aufgerufen, und das klappt nur deshalb so gut, weil sie eben kleine, aber klar umrissene Aufgaben besitzen. Dabei ist es die Sprache selbst, die einen zu diesem Stil „verleitet“: So zu programmieren fühlt sich einfach „natürlich“ an, als ob man „mit dem Strom schwimmt“, und das finde ich großartig – selbst wenn es dabei nur um ein bescheidenes Schiebepuzzle geht.

Advertisements

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s