Backtracking: Kendoku
Kendoku gehört zu den Zahlenrätseln. Hier ein Beispiel aus der Webseite von Angela und Orro Janko https://www.janko.at/Raetsel/Kendoku.
Die Aufgabe
Zwei Bedingungen sind zu erfüllen:
- In die Felder sind natürliche Zahlen von 1 bis zur Größe des Quadrats einzutragen. Wie üblich muss in dem Quadrat jede Zahl in jeder Spalte und in jeder Zeile genau einmal vorkommen.
- Unregelmäßig geformte Bereiche in einem Quadrat enthalten einen Wert und eine Rechenoperation (+,-,*,/). Die Zahlen in dem Bereich müssen zusammen mit der Rechenoperation den angegebenen Wert ergeben.
Die erste Herausforderung für Mathematiker besteht darin, dass die Zahlen bei “-” und “/” vertauscht werden können: wenn beispielsweise die Angabe “2/” lautet, wären (6,3), (3,6), (4,2), (2,4), (2,1) und (1,2) gültige Lösungsansätze.
Hier die Lösung der Beispielaufgabe:
Die Lösung per Programm
Dateiname: kendoku.py. Wie üblich verwenden wir einen vector, der Schritt für Schritt gefüllt wird. Mit jedem Schritt wird der level erhöht.
Die erste Bedingung ist leicht zu erfüllen. Wie im Königinnenproblem verwenden wir Mengen (rset und cset).
Die zweite Bedingung kann erst dann geprüft werden, wenn das letzte Element eines Bereichs zu füllen ist. Dazu bestimmen wir den höchsten Index jedes Bereichs. Wenn beim Füllen eines Bereichs level diesen Index erreicht, startet in valid die Prüfung des errechneten Wertes.
Um die Aufgabe zu beschreiben, verwenden wir ein Tupel kendoku, das seinerseits für jeden Bereich ein Tupel enthält: Jedes dieser Tupel enthält den Wert, den die Rechnung ergeben soll, die Rechenoperation und die Nummer der Felder, die zu dem Bereich gehören. Natürlich beginnt die Nummerierung der Felder mit 0. Statt der Tupel können auch Listen verwendet werden.
In der Beispielaufgabe sieht das dann so aus:
kendoku = (
(16, “x”, ( 0, 1, 6)),
( 7, “+”, ( 2, 3, 9)),
( 1, “-“, ( 4, 5)), …
)
Diese Darstellungsform ermöglicht, das Rätsel mit geringem Schreibaufwand zu formulieren. Da wir den höchsten Wert der Feldnummer brauchen, wird kendoku mit der Methode convert in die interne Darstellung _kendoku umgewandelt. Die ist auch leichter lesbar. _kendoku enthält dann in unserem Beispiel
_kendoku = {
6: {“value”:16, “op”:“x”, “members”🙁0, 1, 6)},
9: {“value”:7, “op”:“+”, “members”🙁2, 3, 9)},
5: {“value”:1, “op”:“-“, “members”🙁4, 5)}, …
}
Das Programm
Der Ablauf des Programms ist im Programmtext ausführlich kommentiert.
# File kendoku.py
from backtrack import Backtrack
class Kendoku(Backtrack):
# Beispiel: https://www.janko.at/Raetsel/Kendoku/009.a.htm
import functools
from functools import reduce
from operator import abs, add, sub, mul, floordiv
size = 6
"""
Jeder Kendoku-Bereich wird durch ein Tupel codiert:
– Der erwartete Wert
– Die Rechenoperation (zulässig: + – x X * / )
– Die Nummern der Felder, die zu dem Bereich gehören, als Tupel.
Jede Feldnummer muss in genau einem der Tupel genau einmal vorkommen
"""
kendoku = (
(16, "x", ( 0, 1, 6)),
( 7, "+", ( 2, 3, 9)),
( 1, "-", ( 4, 5)),
(25, "x", ( 7, 8, 13)),
( 2, "/", (10, 11)),
( 2, "/", (12, 18)),
( 2, "-", (14, 20)),
( 4, "-", (15, 21)),
( 6, "x", (16, 17)),
( 4, "-", (19, 25)),
( 2, "/", (22, 28)),
( 5, "+", (23, 29)),
( 3, "-", (24, 30)),
( 9, "x", (26, 31, 32)),
( 2, "-", (27, 33)),
( 1, "-", (34, 35))
)
_kendoku = {} # Interne Darstellung als dict
# Zwischenergebnisse und Lösung
# Obwohl eine Zahlenmatrix gesucht wird, wird zur internen Berechnung
# ein eindimensionaler Vektor verwerdet.
# Zeilen- und Spaltennummern werden mit der Funktion rowAndCol
# aus der Platznummer (level) errechnet
vector = [None for i in range(size*size)]
# Welche Werte können in den einzelnen Feldern stehen?
values = set(range(1, size+1))
# In rset und cset werden jene Werte gespeichert, die in der jeweiligen Zeile
# oder Spalte schon vorkommen und daher in moves nicht mehr zur Auswahl stehen
rset = [set() for i in range(size)] # row sets
cset = [set() for i in range(size)] # column sets
# Zählen der Lösungen
solutionNr = 0
# Typbeschreibungen
Places = tuple[int]
Kendokutuple = tuple[int, str, Places]
Moves = list[int]
def __init__(self, test:bool= False, showAttempts:bool = False):
self.convert ()
super().__init__(test, showAttempts)
# Für die Prüfung eines Bereichs wird die Variable kendoku in eine
# interne Darstellung (_kendoku) als dict mit dem höchsten Index
# als key umgewandelt
def convert(self):
# suche die höchste Feldnummer und verwende sie als Index
for k in self.kendoku:
# Höchste Platznummer als key festlegen
key = max(k[2])
# Durch die Verwendung eines dict lesbarer machen
self._kendoku[key] = {"value":k[0], "op":k[1], "members":k[2]}
# Die Hilfsfunktion roeAndCol errechnet aus der Platznummer (where)
# die Zeilennummer (r) und die Spaltennummer (c)
def rowAndCol(self, where: int):
s = self.size
r = where // s
c = where % s
return (r, c)
# Bestimme die Werte, die für den Platz (level) zulässig sind
def moves(self, level: int) -> Moves:
r, c = self.rowAndCol(level)
# Werte, die in derselben Spalte oder Zeile vorkommen, werden ausgeschlossen
return list(self.values – self.rset[r] – self.cset[c])
# Ist der Wert (move) auf dem vorgesehenen Platz (level) erlaubt?
def valid(self, level: int, move: int) -> bool:
# Falls der Platz nicht der letzte des Bereichs ist: weitersuchen!
# Dazu prüft get, ob level ein gültiger Key von _kendoku ist.
k = self._kendoku.get(level, False)
# Wenn nein, kann die Rechenopration in dem
# Bereich noch nicht ausgeführt werden. Weitersuchen!
if not k:
return True
# Ist der key vorhanden, dann kann der Test beginnen
# Die Nummern der Felder des Bereichs sind in members zu finden.
# Nun müssen zur Berechnung alle Werte des Bereichs
# (ohne das letzte) in der Liste area zwischengespeichert werden.
area = []
for i in k["members"][0:-1]:
area.append(self.vector[i])
# Das letzte Feld wird probeweise dazu genommen
area.append(move)
# Nun wird die Berechnung in dem Bereich ausgeführt.
# Berechnungen, abhängig vom Operator (+ – …)
value = k["value"]
match(k["op"]):
case "*" | "x" | "X":
return self.reduce(self.mul, area)==value
case "/" | ":":
return self.floordiv(*area)==value or\
self.floordiv(*area[-1:-3:-1])==value
case "+":
return self.reduce(self.add, area)==value
case "-":
return self.abs(self.sub(*area))==value
case _: # Keine Operation angegeben
return True
# Überprüften (validierten) Wert (move) auf den Platz (level) speichern
def record(self, level: int, move: int):
self.vector[level]=move
r, c = self.rowAndCol(level)
self.rset[r].add(move) # Wert zur Menge der Zeilenwerte hinzufügen
self.cset[c].add(move) # Wert zur Menge der Spaltenwerte hinzufügen
# Der Wert (move) passt nicht, daher vom Platz (level) entfernen
def undo(self, level: int, move: int):
self.vector[level]=None
r, c = self.rowAndCol(level)
self.rset[r].remove(move) # Wert aus der Menge der Zeilenwerte entfernen
self.cset[c].remove(move) # Wert aus der Menge der Spaltenwerte entfernen
# Wurde eine Lösung gefunden?
def done(self, level: int):
if level==self.size*self.size-1:
self.solutionNr += 1
print(f“"Lösung {self.solutionNr:4}")
for r in range(self.size):
for c in range(self.size):
print(f"{self.vector[r*self.size + c]:4} ", end="")
print()
return True
return False
if __name__ == "__main__":
Kendoku(showAttempts=True)
Besonderheiten von Python
Hier ein paar Hinweise auf Besonderheiten und auf die verwendeten Version 3.10.6:
In Python können die Typen von Variablen, Parametern und Funktionsergebnissen angegeben werden, sogenannte type hints (https://docs.python.org/3/library/typing.html). Es ist aber nicht verpflichtend, sondern dient der besseren Lesbarkeit und der Kontrolle durch das externe Programm. In den Programmen werden diese type hints mehrmals beispielhaft verwendet.
Beispiele
# Typbeschreibungen
Places = tuple[int]
Kendokutuple = tuple[int, str, Places]
Moves = list[int]
def moves(self, level: int) -> Moves:
…
Da bei “+” und “x” mehr als zwei Zahlen in einem Bereich vorkommen können, wird zur Berechnung reduce eingesetzt. reduce wendet eine Funktion (hier eine Rechenoperation) der Reihe nach auf alle Elemente der Zahlenliste an. Die Argumente von reduce sind:
- Die Funktion, die anzuwenden ist (hier sind es die Rechenoperationen).
- Die Liste der Werte, auf die die Funktion anzuwenden ist.
reduce kennt aber die Operatoren “+“, “x” nicht. Sie werden durch die Funktionen add, mul ersetzt. Ebenso werden sub und floordiv (für die ganzzahlige Division) verwendet. Die vier Funktionen werden von operator importiert.
Statt dieser Funktionen könnte auch die lambda-Funktion eingesetzt werden. Die Anwendung lautet bei der Addition: reduce(lambda(x,y): x+y, area). Die lambda-Funktion ist eine anonyme Funktion, die sinnvoll dort eingesetzt wird, wo eine Funktion nur einmal gebraucht wird.
Die Schreibweise liste[0:-1] bedeute: alle Elemente der Liste, ausgenommen das letzte.
In Python 3.10 wurde match eingeführt. match kann zwar mit switch-Befehlen anderer Sprachen verglichen werden, ist aber viel mächtiger. match wird in vielen Artikeln im Internet erklärt, zum Beispiel hier: https://hellocoding.de/blog/coding-language/python/pattern-matching. Ich empfehle, dieses neue Sprachelement genau zu studieren – es ist eine wirklich nützliche Erweiterung.
Da in Kendoku auch Bereiche ohne Rechenaufgaben zulässig sind, diese Bereiche also beliebig gefüllt werden können, endet die match-Auswahl mit
case _: # Keine Operation angegeben
return True
Wird bei einem Funktionsaufruf als Argument eine Liste mit vorangestelltem * angegeben, ist das gleichwertig zur Angabe aller Listenelemente als einzelne Argumente:
self.floordiv(*area)==value
Auch hier können size und kendoku als Argumente beim Aufruf übergeben werden. Eine Version mit diesen Argumenten und mit lambda-Funktionen sind in der Datei kenduku_2.py zu finden.
Lösung
Hier die Lösung, vom Programm errechnet:
Lösung 1
1 4 2 3 5 6
4 1 5 2 6 3
6 5 4 1 3 2
3 2 6 5 1 4
5 6 3 4 2 1
2 3 1 6 4 5
4.343 attempts in 0.20 seconds
Lust auf mehr? Hier kommt ein Rätsel mit Hochhäusern.
Links
- Alle Dateien
- Was ist eigentlich ‘Backtracking’? (clubcomputer.at)
- Backtracking: Königinnenproblem (clubcomputer.at)
- Backtracking: Sudoku (clubcomputer.at)
- Backtracking: Kendoku (clubcomputer.at)
- Backtracking: Skyline (clubcomputer.at)
- Backtracking: Zeltlager (clubcomputer.at)
Martin Weissenböck
Letzte Artikel von Martin Weissenböck (Alle anzeigen)
- ZigBee, Zwischenstecker und Tasmota - 6. Mai 2023
- Python - 20. Oktober 2022
- Backtracking: Zeltlager - 29. August 2022
Neueste Kommentare