Matlab Sudoku
Inhaltsverzeichnis
Inhalt
Ziel des Projektes ist die Erstellung eines Lösungsprogramms für Sudokus belieber Größe, z.B. 9x9 oder 16x16, und beliebigen Schwierigkeitsgrades. Dazu werden eine Reihe von Hilfsroutinen und ein Lösungsprogramm benötigt.
Für alle Teile gibt es Vorgaben, Anregungen und Tipps wie ich es gemacht habe.
Eine Beschreibung, was Sudokus sind, findet man unter [1].
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 schonerlaubt, wenn man etwas niicht anders lösen kann oder keine andere Idee hat. 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 Sudoku-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
In der hier gewählten Darstellung ist ein Sudoku ein [math](n^2 \times n^2)[/math]-Feld mit Zahlen zwischen 1 und [math]n^2[/math]. An jenen Stellen, wo Zahlen gesetzt werden müssen steht eine Null. In jeder Zeile (row), in jeder Spalte (column) und in jedem Block (sub-square) darf eine Zahl nur einmal vorkommen.
Hilfsroutinen
sudoku_sub
Dies ist eine Routine, die für beliebige Positionen in einem Sudoku die entsprechende Nummer des Blockes berechnet.
function loc = sudoku_sub(n,iz,is) % % loc = sudoku_sub(n,iz,is) % % Computes the number of the local sub-square of the Sudoku from the row % indices iz and the column indices of the Sudoku. % % Input: % % n : size of a subsquare of a Sudoku, 3 for (9 x 9) or 4 for (16 x 16) % iz, is : row and column indices in arrays of same size % % Output: % % loc : numbers of local sub-squares for positions iz and is % array with same size as arrays iz and is % % Winfried Kernbichler 31.03.2006
Die Nummerierung der Blöcke ist wie bei Matlab üblich zuerst entlang der Zeilen und dann entlang der Spalten. In einem (n=3)-Sudoku gibt es neun Blöcke:
1 4 7 2 5 8 3 6 9
Von mir verwendete Befehle: ind2sub, sub2ind und ceil
Typisches Resultat:
loc = sudoku_sub(3,[1,4,4],[2,4,8]) loc = 1 5 8
sudoku_loc
Dieses Programm soll eine Matrix SI erzeugen, die in jeder Zeile die einfachen Indices des entsprechenden Blockes enthält.
function SI = sudoku_loc(n) % % SI = sudoku_loc(n) % % Computes an (n^2 x n^2)-array where each line contains the % single indices of the local sub-square of the Sudoku. % % Input: % % n : size of the Sudoko; 3 for (9 x 9), 4 for (16 x 16), ... % % Output: % % SI : (n^2 x n^2)-array where each row holds the single indices of the % positions in the pertinent local sub-square % % Sub-squares are numbered as follows (here for (n=3)-Sudoku (9 x 9) % % 1 4 7 % 2 5 8 % 3 6 9 % % where each number represents a (n x n)-square. All single indices of % positions belonging to the first sub-square are in line one of SI, and so % on. % % Winfried Kernbichler 31.03.2006
Ein typisches Resultat lautet
SI = sudoku_loc(3)
SI =
1 2 3 10 11 12 19 20 21
4 5 6 13 14 15 22 23 24
7 8 9 16 17 18 25 26 27
28 29 30 37 38 39 46 47 48
31 32 33 40 41 42 49 50 51
34 35 36 43 44 45 52 53 54
55 56 57 64 65 66 73 74 75
58 59 60 67 68 69 76 77 78
61 62 63 70 71 72 79 80 81
d.h., in der ersten Zeile stehen nun die Indices der neun Positionen des ersten Blocks, usw..
Dies ist extrem praktisch, da man jedes Sudoku mit S(SI) damit so umsortieren kann, dass die Werte in den einzelnen Blöcken nun in einzelnen Zeilen stehen.
Von mir verwendete Befehle: colon, reshape, repmat, ceil, sub2ind, transpose.
Die Strategie von mir war, einen Vektor der Zeilenindices der Blöcke zu erzeugen, hier am Beispiel (n=2):
erster zweiter dritter vierter Block 1 2 1 2 3 4 3 4 1 2 1 2 3 4 3 4
und danach eine Vektor der Spaltenindices der Blöcke
erster zweiter dritter vierter Block 1 1 2 2 1 1 2 2 3 3 4 4 3 3 4 4
und diese dann mit sub2ind umzurechnen und entsprechend darzustellen.
1 2 5 6
3 4 7 8
9 10 13 14
11 12 15 16
sudoku_all_possible
Das Ziel hier ist für ein beliebiges Sudoku ein dreidimensionales logisches Feld zu erstellen, das bei jeder Position (Zeile, Spalte) in der dritten Dimension an jenen Stellen einen Einser stehen hat, wo die entspechende Zahl im Sudoku noch gesetzt werden kann.
Stellen sie sich vor an der Position (5,4) können noch die Zahlen 1,4,5, 8 und 9 gesetzt werden, dann soll der Inhalt der logischen Matrix an dieser Stelle so aussehen:
L(5,4,:) -> 1,0,0,1,1,0,0,1,1
DIes soll für die gesamte Matrix gelten. Wenn die Stelle schon besetzt ist, bzw. wenn man dort nichts setzen kann, sollen alle Werte in der dritten Dimension Null sein.
function L = sudoku_all_possible(S,SI) % % L = sudoku_all_possible(S,SI) % % computes a logical (n^2 x n^2 x n^2)-array L where n^2 in a (9 x 9)-Sudoku % is 9. Such a Sudoku is called a (n=3)-Sudoku. % % At a positions L(ir,ic,:) those values are 1 where the % corresponding value could be placed in the Sudoku % % e.g.: if the number [2,3,5,7] can be placed at S(3,2) % in a (n=3)-Sudoku, then % L(3,2,:) is [0,1,1,0,1,0,1,0,0] % % Input: % % S : present representation of the Sudoku, (n^2 x n^2)-array % % Optional Input: % % SI : single indices of the local sub-square of the Sudoku produced by % sudoku_loc (see sudoku_loc for an explanation). % if not in the input sudoku_loc should be called to produce SI % % Output: % % L : logical (n^2 x n^2 x n^2)-array % % Winfried Kernbichler 31.03.2006
Von mir verwendete Befehle: logical, zeros, ones, find, sub2ind, repmat, reshape, logische Operatoren, Vergleichsoperatoren.
Strategie: Die von mir verwendete Strategie war intern vier solche 3D-Felder zu erzeugen, für die Zahlen in den Zeilen, in den Spalten, in den Blöcken und wo man überhaupt noch setzen kann. Diese vier Felder werden dann mit and verknüpft. Zur Umwandlung von Zahlenwerten in Feldern in logische Einsen in einem anderen Feld, habe ich ein kleines Beispiel zur Erläuterung geschrieben [2].
sudoku_best_possible
Dieses Programm soll nun unter Verwendung der logischen dreidimensionalen Matrix die beste Position und dei möglichen Werte liefern.
function [iz,is,val,status] = sudoku_best_possible(S,L) % % [iz,is,val,status] = sudoku_best_possible(S,L) % % gives the best possible position (imz,ims) where to place the next % number (val) in the Sudoku. % % Input: % % S : Sudoku array with size (n^2 x n^2) % L : logical array produced by sudoku_all_possible or modified by % sudoku_set with size (n^2 x n^2 x n^2) % % Output: % % iz, is : position for best placement chosen because of: % (1) minimum number possibilities % (2) first along single dimension in S % val : possible values to be placed at (iz,is) given in a column vector % status : logical status variable % 1 if a location is found where to place a new number out of val % 0 if no location is found or if at any free position no value can % be placed % % Winfried Kernbichler 31.03.2006
Von mir verwendete Befehle: logical, sum, any, all, min, ind2sub, find, nan, logische Operatoren, Vergleichsoperatoren.
Strategie: Mit der Summation über die dritte Dimension im logischen Feld L sieht man sofort, ob man nicht mehr setzen kann. Mit Hilfe des Befehls min findet man auch sofort die Positionen, wo man noch die geringste Anzahl von Möglichkeiten hat. Davon wählt man die erste aus. Bei der Suche nach dem Minimum ist es wichtig, dass man die Nullen ausblendet. Ich habe das mit Hilfe von nan gemacht.
Die Statusvariable ist extrem wichtig, da mit ihrer Hilfe der Solver erkennen kann, ob er aufhören kann.
sudoku_set
Nachdem man nun eine neue Zahl im Sudoku gesetzt hat, muss man die entsprechenden Einträge in der logischen 3D-Matrix wieder durch Nullen ersetzen.
function L = sudoku_set(L,iz,is,val,SI) % % L = sudoku_set(L,iz,is,val,SI) % % removes entries from L when the value val is set at position (iz,is). % % Input: % % L : (n2 x n2 x n2)-logical array with possible positions on entry % corrected on exit % iz, is : row and column index % val : value which was placed at (iz,is) % % Optional Input: % % SI : single indices of the local sub-square of the Sudoku % produced by sudoku_loc (see sudoku_loc for an explanation). % if not in the input sudoku_loc should be called to produce SI % % Output: % % L : logical (n^2 x n^2 x n^2)-array with corrected values % % Winfried Kernbichler 31.03.2006
Von mir verwendete Befehle: colon, ind2sub, min, max.
Strategie: Man braucht nicht unbedingt testen, wo ein Wert Eins war. Man kann die entprechenden Zeilen, Spalten, Blockbereiche und Werte in die 3te Dimension (an der neuen Position) einfach auf Null setzen. Das geht mit Hilfe der Doppelpunkt-Notation und mit Hilfe der Resultate von sudoku_sub und sudoku_loc sehr einfach.
sudoku_valid
Diese Funktion soll überprüfen, ob ein Sudoku zumindest von der Angabe her in Ordnung ist. Ob es auch lösbar ist, kann man damit natürlich nicht sagen. Bei ungültigen Sudokus stimmt die Größe nicht, oder sie haben bereits gleiche Zahlen in Zeilen, Spalten oder Blöcken.
function c = sudoku_valid(S) % % c = sudoku_valid(S) % % computes the logical result c wether the Sudoku S is a valid % Sudoku. % % Input: % % S : Sudoku array % % Output: % % c : logical value % 0 - not square, size not power of 2, not valid % 1 - correct % % Winfried Kernbichler 31.03.2006
Von mir verwendete Befehle: colon, size, logical, sqrt, fix, repmat, permute, sum, all, logische Operatoren, Vergleichsoperatoren.
Strategie: Eine wirklich schöne Strategie ohne Schleife habe ich nicht gefunden, daher die große Anzahl von Befehlen. Ich habe versucht herauszufinden, ob in Zeilen, Spalten, Blöcken Duplikate vorkommen. Daher habe ich das Suudoku in die dritte Dimension repliziert und dann mit einer 3D-Matrix verglichen, die auf der ersten Seite nur Eines, auuf de zweiten nur Zweier, usw., hat. Das ist aber sicher nicht die schönste Lösung.
sudoku_correct
Diese Routine soll nun herausfinden, ob ein Sudoku korrekt gelöst ist.
function c = sudoku_correct(S) % % c = sudoku_correct(S) % % computes the logical result c wether the Sudoku S is a correct % Sudoku solution. % % Input: % % S : Sudoku array % % Output: % % c : logical value % 0 - not square, size not power of 2, not correct % 1 - correct % % Winfried Kernbichler 31.03.2006
Von mir verwendete Befehle: colon, size, logical, sqrt, fix, repmat, transpose, sort, all, logische Operatoren, Vergleichsoperatoren.
Strategie: Mir ist am einfachsten vorgekommen, die Zeilen, bzw. Spalten oder Blöcke zu sortieren und mit Matrizen zu vergleichen, die so aussehen:
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
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 [3]. 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.
sudoku_solve
function [S,ready] = sudoku_solve(S,ready,L,count) % % [S,ready] = sudoku_solve(S) % % solves a Sudoku S with recursion. For the recursive call of sudoku_solve % one needs additional input: % % [S,ready] = sudoku_solve(S,ready,L,count) % % Input: % % S : Sudoku array % % Additional input (for the recursive calls): % % ready : a logical status variable (default value: 0) % 0 - Sudoku is not ready % 1 - Sudoku is ready % % L : logical array described in sudoku_all_possible. % it is not specified when the user calls the routine and it % should be computed then by sudoku_all_possible. % for all further recursive calls its modified content is passed on % to the next recursive call of sudoku_solve. % the modification to L is done by sudoku_set. % % count : a counter for the recursion depth % should be zero at the beginning and again zero at the end. % % Output: % % S : Sudoku % % ready : status variable % 0 - not solveable % 1 - solved % % Error: % % There is an error message: % Sudoku can not be solved! % if the Sudoku is not valid (see sudoku_valid) % % Warning: % % There is a warning message: % Sudoku not correct! % when it was a valid Sudoku which could not be solved. % % Winfried Kernbichler 31.03.2006
Strategie: Der Solver ist jetzt eigentlich ein sehr kurzes Programm. Beim Aufruf durch den Benutzer, der ja nur S übergibt, müssen die Defaultwerte gesetzt werden, bzw. mit sudoku_valid überprüft werden, ob es überhaupt ein gültiges Sudoku ist. Natürlich muss man hier auch die logische Matrix L mit sudoku_all_possible ausrechnen. Es ist das einzige Mal, dass man diese Routine wirklich braucht, da der Rest mit sudoku_best_possible gelöst wird.
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 Sudoku würde man nun mit sudoku_best_possible 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. Diese erkennt nun, dass nichts mehr geht (status Variable aus sudoku_best_possible) 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 Sudoku 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 man sudoku_set immer auf 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.
Diskussion und Fragen
Ablauf
Zeitraum
Osterferien, wobei aber nicht alles vorbei ist, wenn man danach noch Fragen an mich oder leichte offene Probleme hat. Wir sollten es aber nicht wirklich in das restliche Semester nach Ostern ausfransen lassen. Die Übungen, die dann kommen, brauchen auch ihre Zeit.
Ratschlag
Machen sie es nur, wenn sie Zeit haben und nicht dringend etwas für das Studium erledigen müssen. Eine Prüfung aus Experimmentalphysik oder Analysis ist sicher wertvoller.
