Aufgabe 3

Gegeben ist eine Aufteilung in Regionen und die Wörter in den Regionen.

Es soll jetzt überprüft werden, ob das Puzzle eine eindeutige Lösung hat.

Dazu wird ein Algorithmus gesucht, der systematisch das Puzzle versucht zu lösen, indem dieser sämtliche Möglichkeiten durchprobiert. Sobald eine zweite Lösung gefunden wurde, kann der Algorithmus abgebrochen werden. Ansonsten muss er fertig laufen.

«Alles durchprobieren» ist je nach Definition von «alles» praktisch schlicht unmöglich. Die Idee ist, möglichst früh sagen zu können, dass mit der bereits getroffenen Wahl keine Lösung möglich ist.

Dazu verwenden wir folgende zwei Eigenschaften:

• Nur Wörter aus der Wortliste sind zugelassen.
• Die Region, die von einem Wort belegt wird, muss zusammenhängend und zwischen 4 und 8 Felder umfassen.

git fetch --all --tags
git checkout tags/a3
git switch -c dev

Folgende Feststellung ist zentral für den Algorithmus:

• Das Feld am meisten link in der obersten Zeile, die noch freie Zellen hat, ist zwingend ein Wortanfang (vorausgesetzt, die bereits platzierten Wörter sind korrekt).

Die Idee ist, alle Wörter der Wortliste möglichst schnell und effizient durchprobieren zu können. Da jeweils der, bzw. die ersten Buchstaben gegeben sind, brauchen wir schnellen Zugriff auf alle Wörter die mit gegebenen Buchstaben beginnent. Dazu wird die Liste in einem Baum gespeichert, modelliert mit JavaScript Objects (key-value pairs).

Jeder Knoten hat maximal 27 Einträge, 'a'-'z' und '_', um ein Wortende zu markieren.

Die Liste [“aber”, “apfel”, “abend”, “bla”] sieht als Baum wie folgt aus:

{'a': {'b': {'e': {'n': {'d': {'_'}}}, 'r':{'_'}}}}, 'p':{'f':{'e':{'l':{'_'}}}}}, 'b':{'l':{'a':{'_'}}}}

Der Clue ist, dass einfach bei dem Unterbaum weitergearbeitet werden kann, der durch die bereits gegebenen Buchstaben erreicht werden kann. Dazu reicht es, die Referenz auf den Unterbaum zu haben, es brauchen keine weiteren Daten kopiert oder gespeichert zu werden.

Dieser Baum muss nur einmal aus der Wortliste erstellt werden.

Diese Funktion liefert ein Array von möglichen Wörtern, die bei der obersten, am meisten links liegenden freien Zellen starten. Ein Wort ist wie die Variable curUsed (siehe unten) codiert. Ist das Array leer, heisst das, dass die vorhergehende Platzierung nicht möglich ist und diese schrittweise rückgängig gemacht werden muss.

• used[x][y]: -1 wenn frei, sonst die Nummer der Region, zu der die Zelle gehört.
• curUsed: Ein Array von Koordinaten, z.B. [[0,0],[1,0], [0,1], [1,1]], gibt die Reihenfolge der Buchstaben mit ihren Positionen an.
• pft: Wortbaum (der relevante Unterbaum)

Beim ersten Aufruf wird die Funktion mit curUsed = [[x,y]] und pft = wortbaum[buchstabe] aufgerufen, wobei x,y die Koordinaten der ersten Zelle und buchstabe der entsprechende Buchstabe ist.

Die Funktion initialisiert das Array found=[] und geht dann alle möglichen Buchstaben letter in pft durch:

• Ist letter=='_' , ist das ein potentielles Wort. Dann erst wird mit der Funktion connected(curUsed) (siehe unten) überprüft, ob die Koordinaten in curUsed eine zusammenhängede Region darstellen. Wenn ja, wird die aktuelle Lösung dem Array found hinzugefügt.
• Bei einem normalen Buchstaben letter werden im Feld ab der Zelle rechts der aktuellen Position und in der Zeile darunter für alle Zellen mit diesem Buchstaben:
  • Position zu curUsed hinzugefügt.
  • tryNextLetter mit curUsed und pft[letter] aufrufen und erhaltene Lösungen dem Array found hinzufügen.
  • Position wieder aus curUsedentfernen.

Diese Funktion überprüft, ob die Koordinaten im Array coords eine zusammenhängende Region bilden.

Dabei wird wie folgt vorgegangen:

• ok[i]=false für alle i von 0 bis coords.length-1.
• ok[0] = true: Erste Koordinate kann erreicht werden.
• todo = [0]: Erste Koordinate muss noch bearbeitet werden.
• okCount=1: Anzahl erreichbare Koordinaten (wenn bei Koordinate 0 gestartet wird)
• Solange todo.length>0:
  • Sei i==todo.pop() (Entferne letztes Element von todo und speichere es in i)
  • Für jeden Index j von 0 bis coords.length-1:
    • Wenn ok[j]==false und Koordinaten i und j sind benachbart:
      • ok[j]=true markiere j als erreichbar
      • todo.push(j) und füge j der Todo-liste hinzu.
• return coords.length==okCount Die Region ist zusammenhängend, wenn alle Koordinaten erreicht wurden.

Diese Funktion ermittelt die aktuelle Startposition für das nächste mögliche Wort und platziert alle möglichen Wörter und ruft sich dabei wieder auf. Als Resultat liefert die Funktion die Anzahl Lösungen (0,1 oder 2, mehr werden nicht gesucht).

• used[x][y]: -1 wenn frei, sonst die Nummer der Region, zu der die Zelle gehört.
• pft: Die komplette Wortliste als Baum.
• curRegion: Die Nummer der nächsten Region.

Zuerst wird die Startzelle gesucht. Gibt es keine solche, ist das Puzzle voll und die Funktion gibt als Resultat 1 Lösung zurück.

Ab der Startzelle wird für alle möglichen Wörter gesucht und in words gespeichert.

Ist words leer, hat das Puzzle so keine Lösung und die Funktion gibt als Resultat 0 zurück.

numSol=0, die Anzahl möglicher Lösungen bis jetzt.

Sonst wird für jedes word in words folgendes gemacht:

• Das Wort word wird platziert und die entsprechenden Zellen used auf curRegion gesetzt.
• Es wird placeNextWord(used, pft, curRegion+1) aufgerufen und das Resultat zu numSolhinzugezählt.
• Ist numSol>1 wird numSol als Resultat zurückgegeben und die Funktion beendet.
• Die dem word entsprechenden Felder in used werden wieder auf -1 gesetzt.

Die Funktion erstellt den Wortbaum pft, initialisiert alle used[x][y] auf -1 und ruft placeNextWord(used, pft) auf und meldet das Resultat (1 oder 2) zurück. Das Puzzle hat einen eindeutige Lösung wenn 1 gemolden wird. (0 ist nicht möglich, weil das Puzzle ja mit einer Lösung generiert wurde).

Es gibt erstaunlich wenige Wörter, die jeweils überhaupt platziert werden können (durchschnittlich unter zwei, wenn man alle Fälle weglässt, wo kein Wort platziert werden kann). Der Algorithmus funktioniert auch noch einigermassen gut bei 4x so grossen Feldern (14×24) mit einer Wortliste von 23k Wörtern.

Darum funktioniert der hier vorgestellte Algorithmus auch. Es ist nicht klar, ob sich eine frühe Feststellung von nicht-zusammenhängenden Regionen überhaupt lohnen würde.

Wenn es mehrere Lösungen gibt, sind es fast immer Fälle der folgenden Art:

+---+---+ 
| A   B |
+   +   +
| E   R |
+---+---+
| R   A |
+   +   +
| B   E |
+---+---+
 
oder
 
+---+---+ 
| A   B |
+   +---+
| E | R |
+   +   +
| R | A |
+---+   +
| B   E |
+---+---+

Vor allem bei grösseren Felder würde es sich wohl lohnen, solche Fälle zum vornherein zu finden und neue Wörter zu wählen.