Hallo und Hurra,

ich habe im Laufe des Studiums gerade einen Backtracksolver für das  Logikrätsel Kakurasu programmieren dürfen. Ich möchte hier einmal kurz  meine Herangehensweise erläutern.

Kakurasu

Das Kakurasu Board besteht aus drei Bereichen:

  • Der zentrale Bereich besteht aus einer n*n Matrix. Jedes Feld in  der Matrix kann einen von drei Werten annehmen. Es kann entweder  neutral, nicht erreichbar oder aber aktiv sein.
  • Links und Oberhalb des zentralen Bereichs wird den einzelnen  Feldern ein Wert zugewiesen. Üblicherweise wird der ersten Spalte der  Wert 1 zugewiesen, der Spalte zwei der Wert 2, und so weiter bis zur  n-ten Spalte mit den Wert n. Genauso gilt das für die Zeilen. Diese  Werte sind zur Laufzeit nicht mehr veränderbar.
  • Rechts und unterhalb des zentralen Bereichs wird der Zeile bzw.  Spalte eine Zielwert festgelegt. Diese Werte sind ebenfalls  unveränderbar.
  | 1| 2| 3| 4| 5|
--+--+--+--+--+--+--
 1|  |  |  |  |  | 1
--+--+--+--+--+--+--
 2|  |  |  |  |  | 5
--+--+--+--+--+--+--
 3|  |  |  |  |  | 6
--+--+--+--+--+--+--
 4|  |  |  |  |  |10
--+--+--+--+--+--+--
 5|  |  |  |  |  | 6
--+--+--+--+--+--+--
  |13| 3| 3| 4|11|

Lösungsansatz und Implementierung

Als Lösungsansatz habe ich hier den Backtracking-Algorithmus gewählt. Kurz beschrieben geht es darum, die Lösung durch ausprobieren  zu finden. Da das jedoch bei großen Rätseln zu lange dauert, optimiert  man den Algorithmus soweit, dass er möglichst frühzeitig einen  Lösungsweg abbricht, wenn dieser keinen Sinn ergibt.

Zuerst der rekursive Brute-Force Algorithmus:

public boolean solve(int row, int column) {

    //Hier fügen wir die Bedingungen ein

    if(row == (size + 1))
        return board.validateBoard();

    int nextRow = (column == size) ? row + 1 : row;
    int nextColumn = (column == size) ? 1 : column + 1;

    board.markPositionNeutral(row, column);

    if(solve(nextRow, nextColumn)) {
        return true;
    } else {
        board.markPositionActive(row, column);
        return solve(nextRow, nextColumn);
    }
}

Nur wann kann man einen Lösungsweg als fehlerhaft abrechen? Wenden  wir die Regeln oben an, so ist die erste Stufe nach einer Zeile zu  schauen, ob diese Zeile Sinn ergibt. Der Code ist in diesem speziellen  Fall:

if((row != 1 && column == 1) && board.invalidateRow(row-1))
        return false;

Genauer gesagt springt diese Bedingung immer zu Beginn einer neuen Zeile an.

Die dritte Möglichkeit ist ein bisschen komplexer. Es gibt jetzt  sowohl unten als auch rechts in den beiden Ergebnismengen Ergebnisse die  die Anzahl der möglichen Felder einschränken. Wenn wir diese von  vorneherein aussortieren, sinkt die Komplexität des Logikrätsels  signifikant. Ich habe den dafür nötigen Code in eine Funktion  ausgelagert:

public void markAllUnreachableFields() {
    for(int i = (size-1); i >= 0; i--) {
        if(rightColumn[i] < size) {
            for(int n = (size-1); n >= rightColumn[i]; n--) {
                board.markPositionUnreachable((i+1), (n+1));
            }
        }
        if(bottomRow[i] < size) {
            for(int n = (size-1); n >= bottomRow[i]; n--) {
                board.markPositionUnreachable((n+1), (i+1));
            }
        }
    }
}

Die letzte Optimierungsebene beruht auch auf diesem Prinzip. In der  zweiten Spalte steht unten eine drei. Wir wissen also, dass wenn wir die  dritte Reihe befüllt haben, die dritte Spalte bereits komplett sein  muss. Dies machen wir uns zu nutze und prüfen beim Erreichen von der  dritten Spalte in der vierten Reihe, ob die Spalte bereits komplett ist,  sonst brechen wir den Lösungsweg ab:

if(row == (bottomRow[(column-1)] + 1) && board.invalidateColumn(column))
    return false;

Aufgrund dieser Optimierungen steigt die Laufzeit des Algorithmuses  nicht proportional zur Größe des Rätsels. Der gesamte Quellcode ist auf GitLab zu finden.

Wenn euch noch Optimierungsstrategien einfallen, würde ich mich über eine kurze Mail oder einen Pull-Request sehr freuen.

Ergebnis

Wendet man den Algorithmus auf das obige Rätsel an, so erhält man dann folgendes Ergebnis:

  | 1| 2| 3| 4| 5|
--+--+--+--+--+--+--
 1|##|--|--|--|--| 1
--+--+--+--+--+--+--
 2|  |  |  |  |##| 5
--+--+--+--+--+--+--
 3|##|##|##|  |  | 6
--+--+--+--+--+--+--
 4|##|--|--|##|##|10
--+--+--+--+--+--+--
 5|##|--|--|--|##| 6
--+--+--+--+--+--+--
  |13| 3| 3| 4|11|

Auf meinem Rechner dauert dies deutlich weniger als eine Sekunde.

Over and Out.