Und wieder mal die Damen…

Ja, ich weiß, ich habe versprochen, die 8 Damen in Ruhe zu lassen. Aber als das geschrieben hatte, war funktionale Programmierung in Java so unbequem, dass ich nicht gedacht hätte, dass man auch nur ansatzweise einmal eine Übersetzung aus Haskell wagen kann. Zur Erinnerung, das hier was mein Ausgangspunkt:

nqueens :: Int -> [[(Int,Int)]] 
nqueens n = foldr qu [[]] [1..n]
    where qu k qss = [ ((j,k):qs) | qs <- qss, j <- [1..n], all (safe (j,k)) qs ]
          safe (j,k) (l,m) = j /= l && k /= m && abs (j-l) /= abs (k-m)

Und das hier war meine Scala-Version:

object queens {
   def nqueens(n: Int) = {
      import math.abs
      type Pos = (Int, Int)
      def safe(p:Pos, q:Pos) = p._1 != q._1 && p._2 != q._2 && 
                               abs(p._1 - q._1) != abs(p._2 - q._2)
      def qu(k: Int, qss:List[List[Pos]]) =
        for(qs <- qss; j <- (1 to n) if qs.forall(safe(_ ,(j,k)))) yield ((j,k) :: qs)
      (1 to n).foldRight(List(List[Pos]()))(qu)
   }
   def main(args:Array[String]) = println(nqueens(8).mkString("\n"))
}

Die folgende Java 8-Version ist beiliebe nicht allein auf meinem eigenen Mist gewachsen. Ich habe nämlich feststellen müssen, dass meine Kentnisse über die javanischen Lambdas zwar recht gut sind, bei der Stream-API aber doch noch einige Bildungslücken vorhanden sind. Danke an alle „Mitwirkenden“ 🙂

Zuerst einmal brauchen wir ein Äquivalent zu Pos, wie gewohnt etwas länglicher in Java:

public class Pos {
    public final int x;
    public final int y;

    public Pos(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public String toString() {
        return String.format("(%d,%d)",x,y);
    }
}

Nun die eigentliche Berechnung, die strukturell immmer noch recht dicht am Original liegt – nur auf mehrere Methoden verteilt und mit etwas sprechenderen Bezeichnern:

import static java.lang.Math.abs;
 
import java.util.*;
import java.util.stream.*;
 
public class Queens {

    private static boolean safe(Pos p, Pos q) {
        return p.x != q.x && p.y != q.y && 
            abs(p.x - q.x) != abs(p.y - q.y);
    }

    private static <T> List<T> snoc(List<T> ts, T t) {
        List<T> result = new LinkedList<>(ts);
        result.add(t);
        return result;
    }

    private static Stream<Integer> range(int fromInclusive, int toInclusive) {
        return IntStream.rangeClosed(fromInclusive, toInclusive).boxed();
    }

    private static Stream<List<Pos>> solveRow(int row, int boardSize, 
                                              Stream<List<Pos>> solutions) {
        return solutions.flatMap(solution ->
            range(1, boardSize).flatMap(column ->
                solution.stream().allMatch(pos ->
                    safe(pos, new Pos(row, column)))
                    ? Stream.of(snoc(solution, new Pos(row, column)))
                    : Stream.empty()));
    }

    public static Stream<List<Pos>> nqueens(int boardSize) {
        return range(1, boardSize).reduce(
            Stream.of(Collections.emptyList()),
            (solutions, row) -> solveRow(row, boardSize, solutions),
            Stream::concat);
    }

    public static void main(String[] args) {
        nqueens(8).forEach(System.out::println);
    }
}

Was an diesem Code meiner Meinung nach am unschönsten ist, ist der Einsatz von reduce für foldLeft. Sicher, es funktioniert hier, aber nur weil es sich um einen sequentiellen Stream handelt. Genaugenommen ist das Stream::concat also gelogen, und ein paralleler Aufruf würde bestimmt lustige Ergebnisse liefern. Es scheint aber keine wirklich „saubere“ Alternative zu geben, die gleichzeitig praktikabel und funktional ist.

Weniger schön ist auch, dass andauernd Listen kopiert werden müssen, weil es leider immer noch keine „richtigen“ immutablen Collections in Java gibt.

Dann hat sich herausgestellt, dass die Benutzung von IntStream ziemlich unbequem ist – hier hatte wohl Performance Vorrang vor Benutzerfreundlichkeit.

Und natürlich merkt man deutlich, wieviel bequemer und übersichtlicher List-Comprehensions in Haskell oder For-Comprehensions in Scala im Vergleich zu handgedrechselten Trainwrecks aus map, flatMap und filter sind.

Trotz aller Kritikpunkte sollte man aber anerkennen, dass es jetzt zumindest möglich ist, solchen funktionalen Code auch in Java zu schreiben, auch wenn er deutlich länger und etwas schlechter zu lesen ist.

Der Aufwand, um zu diesem Ergebnis zu kommen, war recht hoch, und wie schon gesagt, eine kollektive Anstrengung. Ich denke aber, dass das auch eine Gewohnheitsfrage ist, und sehr viel leichter fällt, wenn man sich erst einmal an die Stream-API gewöhnt hat. Außerdem hoffe ich, dass die nächsten Java-Versionen an der Lambda- und vor allem der Stream-Front noch ein wenig nachbessern, um die Programmierung ein wenig intuitiver zu gestalten.

Nochmal die Damen

Die berühmten 8 Damen hatte ich schon mal abgehandelt, aber das folgende Stückchen Haskell hat es mir angetan:

--http://www.reddit.com/r/programming/comments/62j4m/nqueens_in_haskell/

nqueens :: Int -> [[(Int,Int)]]
nqueens n = foldr qu [[]] [1..n]
    where qu k qss = [ ((j,k):qs) | qs <- qss, j <- [1..n], all (safe (j,k)) qs ]
      safe (j,k) (l,m) = j /= l && k /= m && abs (j-l) /= abs (k-m)

Das sieht ein ganzes Stück besser aus als mein eigener Versuch, und die Logik dahinter ist bestechend einfach: safe testet, ob zwei Positionen „sicher“ sind (sich also nicht in der gleichen Reihe, Spalte oder Diagonale befinden). qu nimmt eine Liste mit allen Teillösungen für die Reihen kleiner als k, und prüft dann für jede Liste qs, welche Spalten j in der Reihe k „sicher“ sind, und sammelt alle entsprechenden Listen mit den neuen Positionen. Nun wird qu für 1 bis n aufgerufen, und dabei jeweils die Teillösung des letzten Aufrufs übergeben, was man mit foldr realisieren kann.

Und hier meine Scala-Übersetzung, die sich wieder möglichst nah ans Original halten soll:

object queens {

   def nqueens(n: Int) = {
      import math.abs
      type Pos = (Int, Int)
      def safe(p:Pos, q:Pos) = p._1 != q._1 && p._2 != q._2 && abs(p._1 - q._1) != abs(p._2 - q._2)
      def qu(k: Int, qss:List[List[Pos]]) = 
        for(qs <- qss; j <- (1 to n) if qs.forall(safe(_ ,(j,k)))) yield ((j,k) :: qs)
      (1 to n).foldRight(List(List[Pos]()))(qu)
   }

   def main(args:Array[String]) = println(nqueens(8).mkString("\n"))
}

Zuerst importiere ich die abs-Methode und definiere den Typ (Int,Int) als Pos, weil ich ihn häufiger benötige. Lokale Hilfsfunktionen schreibt man in Scala besser zuerst, so dass man im Beispiel die umgekehrte Reihenfolge wie in Haskell hat. Bei safe gibt es kaum eine Änderung, wenn man davon absieht, dass in Scala leider kein Pattern Matching in der Argumentliste funktioniert. Die Methode qu wird im Prinzip unverändert übernommen, auch wenn die Syntax deutlich abweicht. Ich denke man sieht hier gut, wie stark Haskell den Entwurf von Scala beeinflusst hat, auch wenn man das Scala nicht unbedingt auf den ersten Blick ansieht. Zu guter Letzt kommt der Aufruf von qu über foldRight. In Scala ist foldLeft üblicher und auch performanter (da Haskell „lazy“ ist, scheint es dort umgekehrt zu sein), aber ich will ja dicht am Original bleiben. Da die Argumente für qu in der richtigen Reihenfolge geliefert werden, läßt sich das (k,l) => qu(k,l) wahlweise mit qu(_,_) oder schlicht mit qu abkürzen. Die main-Methode testet den klassischen 8×8-Fall.

Wie ich schon im oben genannten Artikel erwähnt habe, kann man mit Scala normalerweise sehr dicht an einer Vorlage in einer funktionalen Sprache wie Haskell, Clean oder ML bleiben. Natürlich wird durch die unvollständige Typinferenz und ausführlichere „Zeichensetzung“ in Scala alles ein wenig länglicher, aber strukturell ähneln sich die beiden Programme sehr stark. Auch die „Werkzeugkisten“ der beiden Sprachen haben viel gemeinsam, während Dinge wie Tupel, foldRight, Pattern Matching und List Comprehensions in Java fehlen.

So, in Zukunft werde ich die Damen in Ruhe lassen, zumindest hier im Blog… Hatte ich eigentlich schon erwähnt, dass ich Single bin? 😛

Backtracking

Eine der Stärken von Scala ist, dass man recht einfach Algorithmen auf sehr abstraktem Niveau definieren kann. Nehmen wir zum Beispiel allgemeines Backtracking, eine beliebte Strategie zur Lösungssuche. Fast 1:1 aus Wikipedia übernommen ist dieses trait, das das Problem und seinen Lösungsbaum beschreibt:

trait Backtrackable[S] {
    def root:S  //die Teillösung, mit der gestartet werden soll
    def reject(s:S):Boolean //Ist diese Teilösung ungültig?
    def accept(s:S):Boolean //Ist das eine gültige (fertige) Lösung?
    def first(s:S):Option[S] //Gib mir das erste "Kind" der Teillösung
    def sibling(s:S):Option[S] //Gib mir die nächste "parallele" Teillösung
}

Die Methoden root, first und sibling dienen dazu, den zu untersuchenden „Lösungsbaum“ zu definieren: root ist der Startpunkt, first geht eine „Ebene“ tiefer und sibling geht dann alle weiteren Teillösungen „neben“ der ersten durch. reject und accept regeln den „Verkehr“ in diesem Lösungsbaum: Wo ist gesperrt, wann haben wir eine gültige Lösung gefunden.

Nun kann man – ganz abstrakt – dafür einen „Löser“ schreiben. Die geeignete Datenstrukturen sind hier aber keine Listen (bei denen man ja unbedingt alles berechnen muss), sondern Streams, von denen ich im letzten Post geschrieben habe: Der Kopf steht sofort zur Verfügung, der Rest ist wieder ein Stream, der aber erst ausgerechnet wird, wenn er wirklich gebraucht wird. Wir produzieren sozusagen „just in time“.

Die Verwendung der apply-Methode ist übrigens ein wenig syntaktischer Zucker, denn statt foo.apply(bar) darf man einfach schreiben foo(bar). Ansonsten verhält sie sich wie eine normale Methode.

object Backtracker {
    def apply[S](bt:Backtrackable[S]):Stream[S] = {
        def getStream(path:List[S]):Stream[S] = path match {
            case head :: _ =>
                def backtrack(path:List[S]):List[S] = path match {
                    case head :: tail => bt.sibling(head) match {
                            case None => backtrack(tail)
                            case Some(sib) => sib :: tail
                        }
                    case Nil => Nil
                }

                val rejected = bt.reject(head)
                if(!rejected && bt.accept(head)) {
                    Stream.cons(head, getStream(backtrack(path)))
                } else getStream {
                    if (rejected) {
                        backtrack(path)
                    } else bt.first(head) match {
                        case None => backtrack(path)
                        case Some(f) =>  f :: path
                    }
                }
            case Nil => Stream.empty
        }
        getStream(List(bt.root))
    }
}

Keine Angst, das muss man nicht unbedingt verstehen. Am Ende kommt ein Stream raus, und der liefert auf Nachfrage Ergebnis für Ergebnis – und das ist alles, was man wissen muss. Trotzdem ein kleiner Erklärungsversuch: apply ruft getStream mit der Anfangslösung auf. path ist dabei Pfad vom aktuellen „Lösungsbaumknoten“ bis zur Wurzel. Wenn der pfad leer ist, gibt es keine weiteren Lösungen. Ansonsten schauen wir, ob unsere aktuelle Lösung (der Knoten, wo wir gerade sind) zurückgewiesen wird. Dann gehen wir wieder zurück (mit backtrack) und suchen andere Lösungen. Ist unsere Teillösung gültig, schauen wir, ob es eine fertige Lösung ist. Wenn ja, packen wir diese Lösung in einen Stream, dessen Rest ein Stream ist, der schon die nächste Lösung sucht (mit backtrack). Wenn nein, schauen wir, ob wir mit first tiefer in den Baum hineinsteigen können, ansonsten backtracken wir auch hier. Am besten malt man sich das ganze Verfahren einmal auf, denn eigentlich ist es nicht so kompliziert, wie es klingen mag …

Probieren wir dieses seltsame Gerät einmal am allseits beliebten Acht-Damen-Problem aus. Unsere Lösung ist dabei eine Liste von Zahlen, die die Positionen der Damen in den einzelnen Reihen angeben:

object Queens extends Backtrackable[List[Int]] {
    def root:List[Int] = List()
    def reject(list:List[Int]):Boolean = list match {
        case Nil => false
        case head :: tail => tail.zip(tail.indices).exists{
                case (pos, index) => pos == head ||
                    Math.abs(pos - head) == index + 1 }
    }
    def accept(list:List[Int]):Boolean = list.length == 8
    def first(list:List[Int]):Option[List[Int]] = Some(1 :: list)
    def sibling(list:List[Int]):Option[List[Int]] = list match {
        case head :: tail if head < 8 => Some((head + 1) :: tail)
        case _ => None
    }
}

//und starten
Backtracker(Queens).foreach(println)

Als Ausgabe bekommen wir alle 92 Lösungen:

List(4, 2, 7, 3, 6, 8, 5, 1)
List(5, 2, 4, 7, 3, 8, 6, 1)
List(3, 5, 2, 8, 6, 4, 7, 1)
List(3, 6, 4, 2, 8, 5, 7, 1)
usw…

Natürlich hätten wir auch vorher abbrechen können, nach bestimmten Kriterien filtern oder ähnliches. Gerade bei Backtracking ist es wichtig, dass man nicht einfach stur alle Lösungen ausrechnet, was sehr lange dauern kann, sondern dem Nutzer die Freiheit gibt, einzugreifen. Die Klasse Stream besitzt durch ihre „Faulheit“ (siehe z.B. lazy evaluation) die dazu nötige Flexibilität.

Wer zuviel Zeit hat, kann ja mal versuchen, das hier in Java nachzubasteln, aber mich graust es schon, wenn ich nur daran denke…