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:

1. 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.
2. 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)