Matlab Sudoku: Unterschied zwischen den Versionen

Aus Physik
Zur Navigation springen Zur Suche springen
Zeile 168: Zeile 168:
   
 
Von mir verwendete Befehle: [http://itp.tugraz.at/matlab/techdoc/ref/logical.html logical], [http://itp.tugraz.at/matlab/techdoc/ref/zeros.html zeros], [http://itp.tugraz.at/matlab/techdoc/ref/ones.html ones], [http://itp.tugraz.at/matlab/techdoc/ref/find.html find], [http://itp.tugraz.at/matlab/techdoc/ref/sub2ind.html sub2ind], [http://itp.tugraz.at/matlab/techdoc/ref/repmat.html repmat], [http://itp.tugraz.at/matlab/techdoc/ref/reshape.html reshape], [http://itp.tugraz.at/matlab/techdoc/ref/logicaloperatorselementwise.html logische Operatoren], [http://itp.tugraz.at/matlab/techdoc/ref/relationaloperators.html Vergleichsoperatoren].
 
Von mir verwendete Befehle: [http://itp.tugraz.at/matlab/techdoc/ref/logical.html logical], [http://itp.tugraz.at/matlab/techdoc/ref/zeros.html zeros], [http://itp.tugraz.at/matlab/techdoc/ref/ones.html ones], [http://itp.tugraz.at/matlab/techdoc/ref/find.html find], [http://itp.tugraz.at/matlab/techdoc/ref/sub2ind.html sub2ind], [http://itp.tugraz.at/matlab/techdoc/ref/repmat.html repmat], [http://itp.tugraz.at/matlab/techdoc/ref/reshape.html reshape], [http://itp.tugraz.at/matlab/techdoc/ref/logicaloperatorselementwise.html logische Operatoren], [http://itp.tugraz.at/matlab/techdoc/ref/relationaloperators.html 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 [http://itp.tugraz.at/matlab/techdoc/ref/and.html 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 [http://itp.tugraz.at/LV/kernbich/AppSoft-1/Uebung/Sudoku/test_ex1.m].
   
 
== Diskussion und Fragen ==
 
== Diskussion und Fragen ==

Version vom 7. April 2006, 12:27 Uhr

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. Sie werden heir im Wiki und im MLTutor zur Verfügung stehen. Ich brauche dafür aber noch sicher die nächste Woche.

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 einen Großteil der Verpflichtungen für die Prüfung. Es sollte nur mehr eine viel kleinere Ergänzung über Pfingsten geben. Man kann sich also damit die Teilnahme an der Übunsgklausur ersparen.

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.

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].

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.

Soduko

Matlab