Kakurasu & Backtracking

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.