Matlab Kakuro
Inhaltsverzeichnis
Inhalt
Ziel des Projektes ist die Erstellung eines Lösungsprogramms für Kakuros belieber Größe mit den Zahlen 1 bis9. Dazu werden eine Reihe von Hilfsroutinen und ein Lösungsprogramm benötigt.
Für alle Teile gibt es Anregungen und Tipps wie ich es gemacht habe.
Eine Beschreibung, was Kakuros sind, findet man unter [1].
Bitte lesen sie auch die Beschreibung von Matlab Sudoku, da es auch dort wertvolle allgemeine Hinweise gibt.
Schwierigkeit
Das Problem ist ideal für Matlab, setzt aber gute Kenntnisse der Sprache voraus. Im Prinzip reicht sicher der Inhalt der ersten sechs Übungen, man muss aber die Syntax und die logischen Zusammenhänge gut beherschen. Die Aufgabe ist also auf keinen Fall leicht und stellt durchaus hohe Anforderungen an die Teilnehmer.
Ziel
Ziel ist die Lösung des Problems unter vorwiegender Verwendung von Array-Operationen in Matlab. D.h., die Verrwendung von for-Schleifen sollte so weit als möglich vermieden werden. Sie sind aber schon erlaubt, wenn man etwas nicht anders lösen kann oder keine andere Idee hat. Bei diesem Programmen scheinen sie mir aber unvermeidlich. Typischerweise werden die Programme langsamer, wenn man zu viele Schleifen verwendet. Die Programmstruktur mit einigen Hilfsprogrammen und einem rekursiven Lösungsprogramm wie ich es geschrieben habe, gibt es weiter unten. Ihr müsst und sollt euch nichtt sklavisch daran halten. Man kann von den Tipps etwas lernen bzw. sehen, wie eine Strategie aussehen kann, es muss aber nicht so gemacht werden. Oft gibt es viele Möglichkeiten und wir können sie ja am Ende bei einer Kakuro-Party vergleichen.
Prüfung
Die Teilnehmer erledigen mit der Fertigstellung des Projektes die Prüfung.
Die Lösungen können durchaus zwischen den Teilnehmern besprochen und diskutiert werden, es sollte aber jeder seine Variante abliefern, die er dann auch genau erklären kann. Es gibt also kein Problem mit Zusammenarbeit. Kopierversuche von Personen, die es nicht selbst machen können, sollten aber von den Teilnehmern verhindert werden. Ich persönlich hätte dafür kein Verständnis und würde derartige Angebote für Prüfungen nicht mehr anbieten.
Involvierte Personen
Hier kann sich jeder Teilnehmer leicht eintragen. Man braucht sich nur im Wiki anmelden (rechts oben) und den File editieren. Die Syntax ist extrem einfach.
- Leiter:
- Teilnehmer:
Matlab Programme zur Lösung des Problems
Hier gibt es den Hilfetext meiner Routinen und Anmerkungen wieso und warum ich sie gemacht habe. Es gliedert sich in Hilfsroutinen und den eigenlichen Solver.
Grundlagen
Das im folgenden Bild dargestellte Kakuro
ist durch die Struktur
hm: [9x9 double] hv: [16 6 18 20 11 3 4 12 33 9 11 33 6 9 17 16 8 22 5 7] vm: [9x9 double] vv: [16 4 12 17 9 21 4 17 7 7 5 17 9 8 14 14 17 15 12 20 12 9]
representiert. Im Detail schaut der Inhalt der Struktur so aus (die erste Zeile (Spalte) findet sich dort nicht wieder, da diese Plätze ja alle Null beinhalten müssten):
K.mh % Matrix horizontal
0 0 1 1 0 2 2 0 0
0 3 3 3 0 4 4 4 0
5 5 0 6 6 0 0 7 7
8 8 8 0 9 9 9 9 9
0 0 10 10 0 11 11 0 0
12 12 12 12 12 0 13 13 13
14 14 0 0 15 15 0 16 16
0 17 17 17 0 18 18 18 0
0 0 19 19 0 20 20 0 0
K.hv % Vektor horizontal
16 6 18 20 11 3 4 12 33 9 11 33 6 9 17 16 8 22 5 7
K.vm % Matrix vertikal
0 0 5 8 0 13 16 0 0
0 3 5 8 0 13 16 19 0
1 3 0 8 11 0 0 19 21
1 3 6 0 11 14 17 19 21
0 0 6 9 0 14 17 0 0
2 4 6 9 12 0 17 20 22
2 4 0 0 12 15 0 20 22
0 4 7 10 0 15 18 20 0
0 0 7 10 0 15 18 0 0
K.vv % Vektor vertikal
16 4 12 17 9 21 4 17 7 7 5 17 9 8 14 14 17 15 12 20 12 9
In K.hm (K.vm) sind zusammengehörige Felder durch gleiche positive ganze Zahlen markiert, der Wert Null hingegen besagt, dass dort nicht gesetzt werden darf. Der entsprechende notwendige Summenwert folgt dann aus dem Vektor K.hv (K.vv), also für die mit zwei markierten Felder ist das 6 (horizontal) bzw. 4 (vertikal).
Eine alternative Darstellung eines Kakuros kann mit Hilfe einer 3-dimensionalen Matrix erfolgen. Für das obige Beispiel wäre das für die horizontalen Summen
K(:,:,1) =
NaN NaN 16 0 NaN 6 0 NaN NaN
NaN 18 0 0 NaN 20 0 0 NaN
11 0 NaN 3 0 NaN NaN 4 0
12 0 0 NaN 33 0 0 0 0
NaN NaN 9 0 NaN 11 0 NaN NaN
33 0 0 0 0 NaN 6 0 0
9 0 NaN NaN 17 0 NaN 16 0
NaN 8 0 0 NaN 22 0 0 NaN
NaN NaN 5 0 NaN 7 0 NaN NaN
und für die vertikalen Summen
K(:,:,2) =
NaN NaN 9 17 NaN 9 14 NaN NaN
NaN 12 0 0 NaN 0 0 12 NaN
16 0 NaN 0 5 NaN NaN 0 12
0 0 21 NaN 0 8 17 0 0
NaN NaN 0 7 NaN 0 0 NaN NaN
4 17 0 0 17 NaN 0 20 9
0 0 NaN NaN 0 14 NaN 0 0
NaN 0 4 7 NaN 0 15 0 NaN
NaN NaN 0 0 NaN 0 0 NaN NaN
hier sind alle NaN verbotene Positionen. Die richtigen Bereiche beginnen immer links oder oben mit der Summe und dann folgen rechts oder unten Nullen. Ein Bereich wird dabei durch NaN oder den Rand der Matrix begrenzt.
Lösung
Die Lösung für das obige Kakuro sollte man mit
Kres = kakuro_solve(K)
Kres =
0 0 7 9 0 1 5 0 0
0 9 2 7 0 8 9 3 0
9 2 0 1 2 0 0 1 3
7 1 4 0 3 6 7 8 9
0 0 8 1 0 2 9 0 0
3 7 9 6 8 0 1 3 2
1 8 0 0 9 8 0 9 7
0 2 1 5 0 5 9 8 0
0 0 3 2 0 1 6 0 0
erhalten. Graphisch dargestellt schaut die Lösung so aus:
Andere Beispiele und Rechenzeiten
Die Rechentzeiten für die drei gezeigten Beispiele liegen auf einem Mac Min (Intel Core Duo 1.83 GHz) bei:
| Nummer | Rechenzeit |
|---|---|
| 1 | 0.18 sec |
| 2 | 0.35 sec |
| 3 | 0.34 sec |
Bereitgestellte Routinen
Einige Routinen werden von mir bereitgestellt. Bitte laden sie diese herunter und lesen sie den entsprechenden Hilfetext am Anfang.
kakuro.m zeigt Ablauf des Hauptprogrammes.
kakuro_example.m liefert Beispiele.
kakuro_convert.m konvertiert zwischen den beiden Formen.
kakuro_correct.m überprüft Lösung.
kakuro_show.m stellt Kakuro graphisch dar.
Praktische Hilfsroutinen
kakuro_possum
Diese Routine wird am Anfang verwendet und berechnet einaml alle möglichen Summanden für die Zahlen 1 bis 45 (=sum(1:9)). Ich habe mich dabei für eine Zelle mit 45 Spalten entschieden und diese als globale Variable gespeichert.
Alle Inhalte in dieser Zelle sind logische Felder der Größe (m x 9), wobei m für die Anzahl der Möglichkeiten steht, mit denen eine bestimmt Summe durch Summation der Zahlen 1 bis 9 gebildet werden kann, wobei jede Zahl nur einmal vorkommen kann. Die einzelnen Zeilen dieser logischen Felder enthalten an jenen Positionen Einsen, wo die entsprechenden Zahlen zur Summe beitargen können.
Die Summe 1 kann nur so gebildet werden:
cl{1}
1 0 0 0 0 0 0 0 0
Für die Summe 6 gibt es 4 Möglichkeiten (6, 1+5, 2+4, 1+2+3):
cl{6}
0 0 0 0 0 1 0 0 0
1 0 0 0 1 0 0 0 0
0 1 0 1 0 0 0 0 0
1 1 1 0 0 0 0 0 0
Die höchste mögliche Zahl ergibt sich mit 45:
cl{45}
1 1 1 1 1 1 1 1 1
Sehr hilfreich für diese Aufgabe ist der Matlab-Befehl nchoosek. Für einen Vektor v mit n Elementen und ein Skalar k liefert nchoosek(v,k) alle möglichen Kombinationen von k Elementen aus v ohne Wiederholung.
So liefert nchoosek(1:9,1)
1
2
3
4
5
6
7
8
9
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 9
1 2 3 4 5 6 8 9
1 2 3 4 5 7 8 9
1 2 3 4 6 7 8 9
1 2 3 5 6 7 8 9
1 2 4 5 6 7 8 9
1 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9
und nchoosek(1:9,9)
1 2 3 4 5 6 7 8 9
Nun kann man die Summe über die zweite Dimension bilden sum(nchoosek(1:9,9),2)
36 37 38 39 40 41 42 43 44
Für z.B. die Summe 40 ergibt sich dann die Kombination:
1 2 3 4 6 7 8 9
Die Zahl 40 kann auch noch mit 7 Zahlen gebildet werden:
1 4 5 6 7 8 9
2 3 5 6 7 8 9
Gemeinsam ergibt das dann das logische Feld:
cl{40}
1 0 0 1 1 1 1 1 1
0 1 1 0 1 1 1 1 1
1 1 1 1 0 1 1 1 1
In dieser Routine kommt man nicht um die Verwendung von for Schleifen herum.
kakuro_possum_fast
Diese Routine sollte unter den Randbedingungen zu welcher horizontalen und vertikalen Summe eine Position gehört und welche Zahlen dort schon gesetzt sind, rasch die noch möglichen Zahlen an dieser Position berechnen. Mit dieser Information kann man dann setzen und die logische Matrix updaten.
kakuro_logical
Diese Routine erzeugt eine logische Matrix L der Größe (m x n x 9), wobei (m x n) die Größe des Kakuros K ist. An den Stellen L(3,4,:) sollen dabei jene Positionen logisch 1 (true) sein, wo die zugehörige Zahl noch gestezt werden darf, alle anderen Positionen sollen logisch 0 (false) sein.
Muss man also z.B. mit zwei Zahlen die Summe 6 erreichen, wären die entsprechenden Einträge an diesen beiden Positionen
1 1 0 1 1 0 0 0 0
was den Zahlen
1 2 4 5
entspricht. Ist dann aber an einer Position schon 2 gesetzt, bleibt nur mehr
0 0 0 1 0 0 0 0 0
über, was der Zahl 4 entspricht. Man muss also beim Updaten dieser Matrix sehr vorsichtig sein.
DIese logische Matrix eignet sich auch bestens dafür herauszufinden, ob man auf dem gewählten Weg überhaupt noch zu einer Lösung kommen kann. Wenn nämlich irgendwo, wo man noch setzen muss, die sum(L,3) Null ist, kann es keine Lösung mehr geben.
kakuro_next
Mit dieser Routine wählt man die nächse Position aus, wo gesetzt wird. Dafür nimmt man immer jene Position, wo es die geringste Anzahl von Möglichkeiten gibt. Dies ist für diese rekursiven Verfahren (siehe Solver) die beste Strategie.
Solver
Das hier diskutierte Lösungsprogramm ist ein rekursives Programm, d.h. es ruft sich immer wieder selbst auf. Ein einfaches Beispiel dazu ist ein Programm zur Berechnung der Fakultät einer Zahl [2]. Bei rekursiven Aufrufen, wird immer eine neue Instanz der Routine erzeugt, die bei Fertigstellung ihr Resultat an die vorherige übergibt, bis schlussendlich die nullte Instanz das Resultat an den Benutzer übergibt.
Der Solver sollte für beide Kakuro-Typen (Struktur und 3D-Matrix) funktionieren, man kann dafür [http://itp.tugraz.at/~kernbich/download/kakuro/kakuro_convert.m kakuro_convert.m verwenden.
kakuro_solve
% [Kres,ready,tim] = kakuro_solve(K) % % solves a Kakuro K with recursion. For the recursive call of kakuro_solve % one needs additional input: % % [Kres,ready] = kakuro_solve(K,Kres,L,ready,count) % % Input: % % K : Kakuro (both forms: structure or 3D) % % Additional input (for the recursive calls): % This is not specified by the user. % % Kres : intermediate solution in form of a 2D-matrix % (m x n)-matrix (size if K.hm, K.vm) % 0 - values not set % > 0 - intermediate guess % % L : 3-dimensional logical array of size (m x n x 9) % it is not specified when the user calls the routine and it % should be computed and updated during recursive calls. % % For each position [m,n] the nine logical values are: % false if this number can not be set at position [m,n] % true if this number can be set at position [m,n] % Examples: % % L(3,4,:) is [0 0 1 0 1 0 0 0 1] means that at position % Kres(3,4) the values 3, 5 or 9 are possible. % % L(2,1,:) is [1 0 0 0 0 0 0 0 0] means that at position % Kres(2,1) only the value 1 is possible. % % L(5,6,:) is [0 0 0 0 0 0 0 0 0] means that at position % Kres(5,6) nothing can be set anymore. % % ready : a logical status variable (default value: 0) % 0 - Kakuro is not ready % 1 - Kakuro is ready % % count : a counter for the recursion depth % should be zero at the beginning and again zero at the end. % % Output: % % Kres : Solution-Matrix for Kakuro % (m x n)-matrix (size if K.hm, K.vm) % 0 - values not to be set (forbidden positions) % > 0 - solution % % ready : status variable % 0 - not solveable % 1 - solved % % tim : Overall soultion time in seconds % % Warning: % % There is a warning message: % Kakuro not correct! % when Kakuro could not be solved. % % Winfried Kernbichler 13.07.2007
Strategie: Der Solver ist jetzt eigentlich ein sehr kurzes Programm. Beim Aufruf durch den Benutzer, der ja nur K übergibt, müssen die Defaultwerte gesetzt werden,
die möglichen Bestandteile von Summen vorbereitet werden, und die 3-dimensionale logische Matrix vorbereitet werden.
Der Algorithmus bedient sich der Tiefensuche. Ich habe hier zur Erläuterung ein Bild aus Wikipedia eingefügt.
Das Problem bei der Tiefensuche ist, dass man nicht weiss, wo sich die gewünschte Lösung verbirgt und man muss oft viele der Wege gehen, bis man die Lösung erreicht. Nehmen wir der Einfachheit halber an, die Lösung ist im Bild bei 10 erreicht. Startet man nun die Suche, steht das Programm bei 1 (Instanz 0). Beim Kakuro würde man nun mit sudoku_next herausfinden, dass es an der besten Position drei Möglichkeiten gibt. Nun wählt man die Möglichkeit 2 (setzt den Wert und modifiziert das logische Feld L) und ruft wiederum den Solver (Instanz 1).
Diese Instanz findet 2 Möglichkeiten, wählt 3, ruft die nächste Instanz (2). Die findet zwei Möglichkeiten, wählt 4 und ruft die dritte Instanz. Dann erkennt man, dass nichts mehr geht (keine M[glichkeit zu setzen) und kehrt "not ready" zur Instanz 2 zurück. Diese probiert nun die zweite Möglichkeit, auch diese kommt mit "not ready" zurück.
Nun kehrt der Algorthmus zur Instanz 1 zurück, ein weiterer Versuch mit 6 schlägt fehl. Dadurch Rückkehr zur Instanz 0. Diese probiert 7 dann 8. Bei 8 geht es weiter und die erste Instanz probiert 9, die zweite Instanz probiert 10, bekommt von der dritten Instanz die Antwort "ready". Nun kehrt alles mit der Antwort "ready" über die zweite, zur ersten und schließlich zur nullten Instanz zurück.
Ganz zum Schluss (wenn count wieder bei Null ist) muss man überprüfen, ob das Kakuro nun korrekt gelöst ist.
Da die Wege lang sein können, ist es wichtig, dass man clevere Entscheidungen trifft. Das heisst, das man dort beginnt, wo es die wenigsten Möglichkeiten gibt, und dass man sofort in einem Zweig aufhört, wenn klar ist, dass man irgendwo sowieso nicht mehr setzen kann, auch wenn diese Position noch gar nicht dran ist.
Bei meiner Lösung ist das Durchprobieren der Möglichkeiten in einer Instanz, der einzige Fall, wo eine Schleife eingesetzt wird. Bei dieser Schleife muss man nur aufpassen, dass der nächsten Instanz des Solvers das richtige logische Array übergeben wird. Da in der Schleife nacheinander verschiedene Werte an einer Position gesetzt werden, muss immer jene Instanz von L anwenden, die vor der Schleife vorhanden war.
Von mir verwendete Befehle: nargin, error, warning, if, else, for, return, Vergleichsoperatoren.
Nochmals, dies ist eine mögliche Lösung unter vielen. Meine Lösung soll daher ein Hinweis sein, wenn ihr Hilfe braucht, aber nicht die exakte Vorgabe, wie sie aussehen muss.
