function SudokuSolverGUI(EntscheidungVar) global figureEingabeHandle listboxDimension editEingabe figureMainHandle HandleVektor Dim figureFehler... buttonCloseHandle buttonSolveHandle buttonBackHandle Startzeit figureLoesung buttonSizeHandle clc %Header('SudokuSolver - Programm zur Lösung von Sudokus',0,0,0); if (nargin == 0) EntscheidungVar = 0; ScreenDim = get(0,'screensize'); xDim = ScreenDim(3); yDim = ScreenDim(4); figureEingabeHandle = figure('name','Eingabe der Sudokudimension','Position',[xDim/2-200 yDim/2-100 400 250],'MenuBar','none',... 'numbertitle','off','resize','off'); frameRahmen = uicontrol('style','frame','position',[30 30 340 200]); textAufforderung = uicontrol('style','text','Position',[50 200 300 20],'string','Bitte wählen Sie die Größe des Sudokus aus.'); listboxDimension = uicontrol('style','listbox','string',{'9x9 Sudoku' '16x16 Sudoku' '25x25 Sudoku'},... 'Position',[300/2 110 100 70],'tag','Auswahlbox'); buttonStart = uicontrol('style','pushbutton','string','SudokuSolver starten','position',[200-75 50 150 30],... 'Callback','SudokuSolverGUI(''Auswahl'')','tag','Startbutton'); end if (strcmp(EntscheidungVar,'Auswahl') == 1) Auswahl = get(listboxDimension,'value'); Dim = (Auswahl+2)^2; close(figureEingabeHandle); ScreenDim = get(0,'screensize'); xDim = ScreenDim(3); yDim = ScreenDim(4); switch Dim case 9 Size = Dim*70; Schriftgroesse = 15; Faktor = 0.3; case 16 Size = Dim*50; Schriftgroesse = 12; Faktor = 0.3; case 25 Size = Dim*30; Schriftgroesse = 9; Faktor = 0.3; end figureMainHandle = figure('name','SudokuSolver','Position',[xDim/2-Size/2 yDim/2-Size/2 Size Size],'MenuBar','none',... 'numbertitle','off','tag','Hauptprogramm','resize','off'); Breite = 0.8*Size/Dim; HandleVektor = 0; for (i1 = 0:1:Dim-1) Abschnitt1 = floor(i1/sqrt(Dim)); for (i2 = 0:1:Dim-1) Abschnitt2 = floor(i2/sqrt(Dim)); editEingabe = uicontrol(figureMainHandle,'style','edit','Position',... [Abschnitt1*Faktor*Breite+0.1*Size+i1*Breite -Abschnitt2*Faktor*Breite+Size-0.1*Size-i2*Breite Breite Breite],... 'fontsize',Schriftgroesse,'tag',[num2str(i1),' ',num2str(i2),' ','EingabeText'],'string',0); HandleVektor(i1+1,i2+1) = editEingabe; end end buttonSolveHandle = uicontrol('style','pushbutton','string','Eingegebenes Sudoku Lösen','position',[Size/2-300 0.05*Size 150 30],... 'Callback','SudokuSolverGUI(''Solve'')'); buttonSizeHandle = uicontrol('style','pushbutton','string','Sudokugröße ändern','position',[Size/2-150 0.05*Size 150 30],... 'Callback','SudokuSolverGUI(''Neu'')'); buttonBackHandle = uicontrol('style','pushbutton','string','Zürücksetzen','position',[Size/2 0.05*Size 100 30],... 'Callback','SudokuSolverGUI(''Back'')'); buttonCloseHandle = uicontrol('style','pushbutton','string','Programm schließen','position',[Size/2+150 0.05*Size 150 30],... 'Callback','SudokuSolverGUI(''Close'')'); end if (strcmp(EntscheidungVar,'Back') == 1) for (i1 = 1:1:Dim) for (i2 = 1:1:Dim) set(HandleVektor(i1,i2),'string',0,'foregroundcolor','k'); end end end if (strcmp(EntscheidungVar,'Solve') == 1) Startzeit = clock; %Auslesen der Dimension der eingegebenen Matrix DimMatrix = size(HandleVektor); DimQuad = abs(sqrt(size(HandleVektor))); for (i1 = 1:1:DimMatrix(1)) for (i2 = 1:1:DimMatrix(1)) if (isempty(str2num(get(HandleVektor(i1,i2),'string'))) == 1) EingabeMatrix(i1,i2) = -1; else EingabeMatrix(i1,i2) = str2num(get(HandleVektor(i1,i2),'string')); end end end %Mit Hilfe der Variablen Ausschluss können fehlerhafte Eingaben aussortiert %werden Ausschluss = 0; for (i1 = 1:1:DimMatrix(1)) for (i2 = 1:1:DimMatrix(1)) if (EingabeMatrix(i1,i2) < 0 || EingabeMatrix(i1,i2) > DimMatrix(1)) Ausschluss = Ausschluss + 1; end end end if (Ausschluss == 0) %Initialisieren der Variablen MinAnzahlBackup = zeros(1,DimMatrix(1)); %Initialisieren eines Sudoku-Feld-'Vektors' SudokuFelder = cell(DimMatrix(1),DimMatrix(1)); SudokuLsg = cell(DimMatrix(1),DimMatrix(1)); SudokuBackup = cell(DimMatrix(1),DimMatrix(1)); SudokuUrbild = cell(DimMatrix(1),DimMatrix(1)); %Füllen des 'Vektors' mit 1-er Elementen (binäre Darstellungsweise: %Bsp: Ziffern 1 2 3 4 5 % erlaubte Ziffern des Feldes 0 1 1 0 1 %bedeutet, dass in dem betrachteten Feld aufgrund der äußeren %Bedingungen entweder die Ziffer 2,3 oder 5 steht for (i1 = 1:1:DimMatrix(1)) for (i2 = 1:1:DimMatrix(2)) %Wenn in dem betrachteten Feld eine 0 steht, so wird ein %liegender Vektor mit lauter 1en produziert if (EingabeMatrix(i1,i2) == 0) SudokuFelder{i1,i2} = ones(1,DimMatrix(1)); %Ansonsten wird an der jeweiligen Stelle eine 1 und ansonsten %nur 0en produziert else SudokuFelder{i1,i2} = zeros(1,DimMatrix(1)); SudokuFelder{i1,i2}(1,EingabeMatrix(i1,i2)) = 1; end %Desweietern wird ein zweiter 'Vektor' für Zwischenlösungen %erstellt SudokuLsg{i1,i2} = ones(1,DimMatrix(1)); SudokuBackup{i1,i2} = zeros(1,DimMatrix(1)); end end %Das Entscheidungskriterium zum Durchlaufen des Algorithmus wird %initialisiert Entscheidung = 0; %Solange das Abbruchkriterium nicht erfüllt ist, wird der Algorithmus %ausgeführt while(Entscheidung == 0) %Die Elemente der Matrix werden Zeilen und Spaltenweise ausgewertet und %die binärcodierten Lösungen in dem Zwischenlösungsvektor gespeichert for (i1 = 1:1:DimMatrix(1)) for (i2 = 1:1:DimMatrix(1)) if (sum(SudokuFelder{i1,i2}) == 1) for (i3 = 1:1:DimMatrix(1)) if (i3 == i2) SudokuLsg{i1,i3} = SudokuFelder{i1,i2}; else SudokuLsg{i1,i3} = SudokuLsg{i1,i3} - SudokuFelder{i1,i2}; end if (i3 == i1) SudokuLsg{i3,i2} = SudokuFelder{i1,i2}; else SudokuLsg{i3,i2} = SudokuLsg{i3,i2} - SudokuFelder{i1,i2}; end end %Die folgende Funktion ermittelt mit Hilfe der jeweils %aktuell betrachteten Zeilen- bzw Spaltenzahl das zZ. %betrachtete Quadrat, dessen Einträge ggf. aktualisiert %werden müssen ZeilenZahl = (ceil(i1/DimQuad(1)) - 1)*DimQuad(1); SpaltenZahl = (ceil(i2/DimQuad(1)) - 1)*DimQuad(1); for (i4 = 1:1:DimQuad(1)) for (i5 = 1:1:DimQuad(1)) if (ZeilenZahl + i4 == i1 && SpaltenZahl + i5 == i2) SudokuLsg{ZeilenZahl + i4,SpaltenZahl + i5} = SudokuFelder{i1,i2}; else SudokuLsg{ZeilenZahl + i4,SpaltenZahl + i5} = SudokuLsg{ZeilenZahl + i4,SpaltenZahl + i5} - SudokuFelder{i1,i2}; end end end end end end for (i1 = 1:1:DimMatrix(1)) for (i2 = 1:1:DimMatrix(1)) for (i3 = 1:1:DimMatrix(1)) %Sofern aufgrund der vorangegangenen Operationen eine von 0 %bzw 1 verschiedene Ziffer in einem Lösungskandidatenvektor %für eine Zelle steht, wird diese durch eine 0 ersetzt if(SudokuLsg{i1,i2}(1,i3) < 0) SudokuLsg{i1,i2}(1,i3) = 0; end end end end %Zeilen und Spaltenweises Analysieren auf eindeutig identifizierbare %Zifferpositionen for (i1 = 1:1:DimMatrix(1)) LZeile = 0; LSpalte = 0; for (i2 = 1:1:DimMatrix(1)) %Aufaddieren der jeweiligen Zeilen bzw %Spaltenlösungskandidatenvektoren LZeile = LZeile + SudokuLsg{i1,i2}; LSpalte = LSpalte + SudokuLsg{i2,i1}; end for (i3 = 1:1:DimMatrix(1)) %Wenn in der Summe aller Lösungskandidatenvektoren einer Spalte für %eine bestimmte Ziffer die 1 als Ergebnis geliefert wird, so %bedeutet dies, dass diese Ziffer nur an einer einzigen Stelle der %Zeile stehen kann if (LZeile(1,i3) == 1) for (i4 = 1:1:DimMatrix(1)) %Die entsprechende Zeile wird durchgegangen und der %entsprechende Eintrag aktualisiert if (SudokuLsg{i1,i4}(1,i3) == 1) SudokuLsg{i1,i4} = zeros(1,DimMatrix(1)); SudokuLsg{i1,i4}(1,i3) = 1; end end end %Analogie zur Zeilenweisen Analyse (s.oben) if (LSpalte(1,i3) == 1) for (i5 = 1:1:DimMatrix(1)) if (SudokuLsg{i5,i1}(1,i3) == 1) SudokuLsg{i5,i1} = zeros(1,DimMatrix(1)); SudokuLsg{i5,i1}(1,i3) = 1; end end end end end %Quadratweises Analysieren auf eindeutig identifizierbare Zifferpositionen for (i1 = 1:1:DimQuad(1)) VertikalesQuadrat = (i1 - 1)*DimQuad(1); for (i2 = 1:1:DimQuad(1)) HorizontalesQuadrat = (i2 - 1)*DimQuad(1); LQuadrat = 0; for (i3 = 1:1:DimQuad(1)) for (i4 = 1:1:DimQuad(1)) LQuadrat = LQuadrat + SudokuLsg{VertikalesQuadrat + i3,HorizontalesQuadrat + i4}; end end %Wenn die Summe aller Lösungskandidatenvektoren an eine bestimmten %Stelle den Wert 1 besitzt, so kann die entsprechende Ziffer nur an %einer Stelle im Quadrat stehen for (i5 = 1:1:DimMatrix(1)) if (LQuadrat(1,i5) == 1) for (i6 = 1:1:DimQuad(1)) for (i7 = 1:1:DimQuad(1)) if (SudokuLsg{VertikalesQuadrat + i6,HorizontalesQuadrat + i7}(1,i5) == 1) SudokuLsg{VertikalesQuadrat + i6,HorizontalesQuadrat + i7} = zeros(1,DimMatrix(1)); SudokuLsg{VertikalesQuadrat + i6,HorizontalesQuadrat + i7}(1,i5) = 1; end end end end end LQuadratAktualisiert = 0; for (i8 = 1:1:DimQuad(1)) for (i9 = 1:1:DimQuad(1)) LQuadratAktualisiert = LQuadratAktualisiert + SudokuLsg{VertikalesQuadrat + i8,HorizontalesQuadrat + i9}; end end for (i10 = 1:1:DimQuad(1)) LQuadSumZeile = 0; LQuadSumSpalte = 0; for(i11 = 1:1:DimQuad(1)) LQuadSumZeile = LQuadSumZeile + SudokuLsg{VertikalesQuadrat + i10,HorizontalesQuadrat + i11}; LQuadSumSpalte = LQuadSumSpalte + SudokuLsg{VertikalesQuadrat + i11, HorizontalesQuadrat + i10}; end %Anhand der folgenden Variablen lässt sich feststellen, ob die %gesamten Lösungskandidaten für eine Ziffer aus einer %bestimmten Quadratzeile bzw -spalte stammen DiffZeile = LQuadratAktualisiert - LQuadSumZeile; DiffSpalte = LQuadratAktualisiert - LQuadSumSpalte; %Ist dies der Fall, so muss in der jeweiligen Zeile bzw Spalte %in jedem Lösungskandidatenvektor (bis auf diejenigen aus dem %zZ betrachteten Quadrat) die entsprechende Stelle auf 0 %gesetzt werten for (i12 = 1:1:DimMatrix(1)) if (DiffZeile(1,i12) == 0) for (i13 = 1:1:DimMatrix(1)) if ((ceil(i13/DimQuad(1)) - 1)*DimQuad(1) == HorizontalesQuadrat) else SudokuLsg{VertikalesQuadrat + i10,i13}(1,i12) = 0; end end end if (DiffSpalte(1,i12) == 0) for (i14 = 1:1:DimMatrix(1)) if ((ceil(i14/DimQuad(1))-1)*DimQuad(1) == VertikalesQuadrat) else SudokuLsg{i14,HorizontalesQuadrat + i10}(1,i12) = 0; end end end end end end end %Initialisieren einer Zählvariablen Counter = 0; for (i1 = 1:1:DimMatrix(1)) for (i2 = 1:1:DimMatrix(1)) %Wenn der Eintrag des Lösungskandidatensudokus des vorherigen %Schleifendurchgangs mit dem aktuellen Lösungskandidatensoduko %übereinstimmt, so wird mit Hilfe der Variablen Counter die Anzahl %dieses Ereignisses gezählt if (sum(SudokuFelder{i1,i2} == SudokuLsg{i1,i2}) == DimMatrix(1)) Counter = Counter + 1; end end end %Wenn der Counter genau n^2 Übereinstimmungen gezählt hat, so hat sich %durch den letzten Schleifendurchgang mit Hilfe der logischen Operationen %Zeilen-, Spalten- und Quadratweises eliminieren keine neue Information %über die Lösung ergeben if (Counter == DimMatrix(1)*DimMatrix(1)) %Prüfen der Variablen SudokuBackup n1 = 0; for (i1 = 1:1:DimMatrix(1)) for (i2 = 1:1:DimMatrix(1)) n1 = n1 + sum(SudokuBackup{i1,i2}); end end %Wenn die Variable SudokuBackup keine Informationen erhält, so muss sie %initialisiert werden if (n1 == 0) %Auslesen der kleinsten Menge an möglichen Lösungskandidaten in einer %Zelle n2 = 0; for (i1 = 1:1:DimMatrix(1)) for (i2 = 1:1:DimMatrix(1)) n2 = n2 + sum(SudokuUrbild{i1,i2}); end end %Sofern das Urbild noch nicht existiert, wird es angelegt if(n2 == 0) for (i1 = 1:1:DimMatrix(1)) for (i2 = 1:1:DimMatrix(1)) SudokuUrbild{i1,i2} = SudokuLsg{i1,i2}; KAnz = sum(SudokuUrbild{i1,i2}); MinAnzahlBackup(1,KAnz) = MinAnzahlBackup(1,KAnz) + 1; end end end %Ggf. wird die Variable MinAnzahlBackup aktualisiert, welche die %Anzahl der Felder mit der jeweiligen Anzahl der möglichen %Lösungskandidaten enthält Counter1 = 1; while (Counter1 <= DimMatrix(1)) if (MinAnzahlBackup(1,Counter1) ~= 0) MinAnzahlBackup(1,Counter1) = 0; Counter1 = DimMatrix; end Counter1 = Counter1 + 1; end Counter2 = 1; Zeiger = 0; while (Counter2 <= DimMatrix(1)) if (MinAnzahlBackup(1,Counter2) ~= 0) Zeiger = Counter2; Counter2 = DimMatrix(1); end Counter2 = Counter2 + 1; end %Wenn alle möglichen Kombinationen des Ursudokus (eindeutiger %Lösungsgrad aufgrund der logischen Operationen) zu keiner %eindeutigen Lösung führten, wird der Algorithmus abgebrochen if (Zeiger == 0) Entscheidung = 2; end %Auslesen der Zellen, welche die entsprechende Anzahl von %Lösungskandidaten enthalten for (i3 = 1:1:DimMatrix(1)) for (i4 = 1:1:DimMatrix(1)) if (sum(SudokuUrbild{i3,i4}) == Zeiger) SudokuBackup{i3,i4} = SudokuUrbild{i3,i4}; end end end end %Wenn der Algorithmus nach der Auswahl einer nicht eindeutig bestimmten %Ziffer wieder an den Punkt kommt, an dem die logischen Operationen zu %keiner Lösung führen, so muss das Ausgangssudoku dieses Schrittes %widerhergestellt werden und eine andere Ziffer ausprobiert werden for (i1 = 1:1:DimMatrix(1)) for (i2 = 1:1:DimMatrix(1)) SudokuLsg{i1,i2} = SudokuUrbild{i1,i2}; end end Counter1 = 1; while (Counter1 <= DimMatrix(1)) Counter2 = 1; while (Counter2 <= DimMatrix(1)) Counter3 = 1; if (sum(SudokuBackup{Counter1,Counter2}) ~= 0) while (Counter3 <= DimMatrix(1)) %Wenn in der Speichervariablen SudokuBackup eine 1 %vermerkt ist, so ist dies ein Lösungskandidat aus einer %mehrdeutigen Zelle, der nun eingesetzt wird und mit dieser %neuen Information versucht wird, das Sudoku zu lösen if (SudokuBackup{Counter1,Counter2}(1,Counter3) == 1) SudokuLsg{Counter1,Counter2} = zeros(1,DimMatrix(1)); SudokuLsg{Counter1,Counter2}(1,Counter3) = 1; %Der entsprechende Eintrag wird aus der %Speichervariablen SudokuBackup gelöscht, sodass er %nicht nocheinmal ausprobiert wird SudokuBackup{Counter1,Counter2}(1,Counter3) = 0; Counter3 = DimMatrix(1); Counter2 = DimMatrix(1); Counter1 = DimMatrix(1); end Counter3 = Counter3 + 1; end end Counter2 = Counter2 + 1; end Counter1 = Counter1 + 1; end end for (i1 = 1:1:DimMatrix(1)) for (i2 = 1:1:DimMatrix(1)) SudokuFelder{i1,i2} = SudokuLsg{i1,i2}; end end x = 0; for (i1 = 1:1:DimMatrix(1)) for (i2 = 1:1:DimMatrix(1)) %Aktualisierung der Entscheidungsvariablen x = x + SudokuLsg{i1,i2}; end end %Wenn die Summe aller Einträge der Lösungskandidatenvektoren mit n^2 (n: %Zeilen bzw Spaltenanzahl) übereinstimmt, so ist das Sudoku eindeutig %gelöst (in jeder Zelle steht genau eine Zahl) if (sum(x) == DimMatrix(1)*DimMatrix(1)) Entscheidung = 1; end end %Umwandlung der binärcodierten Lösungen for (i1 = 1:1:DimMatrix(1)) for (i2 = 1:1:DimMatrix(1)) Erg = 0; %Wenn es sich um einen eindeutigen Eintrag handelt, so wird der %entsprechende Wert ausgelesen if (sum(SudokuLsg{i1,i2}) == 1) for (i3 = 1:1:DimMatrix(1)) Erg = Erg + SudokuLsg{i1,i2}(1,i3)*i3; end end B(i1,i2) = Erg; end end if (Entscheidung == 2) Screensize = get(0,'screensize'); xSize = Screensize(3); ySize = Screensize(4); figureFehler = figure('name','Fehler','menubar','none','numbertitle','off','position',[xSize/2-200 ySize/2-75 400 150],... 'resize','off'); uicontrol('style','text','string','Das eingegebene Sudoku konnte nicht gelöst werden.','position',[50 25 300 100],... 'fontsize',12,'HorizontalAlignment','left'); uicontrol('style','pushbutton','string','Eingabe kontrollieren!','position',[400/2-70 30 140 30],'Callback','SudokuSolverGUI(''Fehler'')'); set(buttonCloseHandle,'enable','off'); set(buttonBackHandle,'enable','off'); set(buttonSolveHandle,'enable','off'); set(buttonSizeHandle,'enable','off'); else Endzeit = clock; Gesamtzeit = Endzeit - Startzeit; for (i1 = 1:1:DimMatrix(1)) for (i2 = 1:1:DimMatrix(1)) if(B(i1,i2) == EingabeMatrix(i1,i2)) set(HandleVektor(i1,i2),'string',B(i1,i2),'foregroundcolor','k'); else set(HandleVektor(i1,i2),'string',B(i1,i2),'foregroundcolor','r'); end end end Screensize = get(0,'screensize'); xSize = Screensize(3); ySize = Screensize(4); figureLoesung = figure('name','Lösung','menubar','none','numbertitle','off','position',[xSize/2-200 ySize/2-75 400 150],... 'resize','off'); deltaT = Gesamtzeit(4)*3600 + Gesamtzeit(5)*60 + Gesamtzeit(6); uicontrol('style','text','string',['Das eingegebene Sudoku wurde in ',num2str(deltaT),' Sekunden gelöst.'],'position',[50 25 300 100],... 'fontsize',12,'HorizontalAlignment','left'); uicontrol('style','pushbutton','string','Ergebnis.','position',[400/2-70 30 140 30],'Callback','SudokuSolverGUI(''Erg'')'); set(buttonCloseHandle,'enable','off'); set(buttonBackHandle,'enable','off'); set(buttonSolveHandle,'enable','off'); set(buttonSizeHandle,'enable','off'); end else Screensize = get(0,'screensize'); xSize = Screensize(3); ySize = Screensize(4); figureFehler = figure('name','Fehler','menubar','none','numbertitle','off','position',[xSize/2-200 ySize/2-75 400 150],... 'resize','off'); uicontrol('style','text','string','Das eingegebene Sudoku enthält unzulässige Eingabewerte.','position',[50 25 300 100],... 'fontsize',12,'HorizontalAlignment','left'); uicontrol('style','pushbutton','string','Eingabe kontrollieren!','position',[400/2-70 30 140 30],'Callback','SudokuSolverGUI(''Fehler'')'); set(buttonCloseHandle,'enable','off'); set(buttonBackHandle,'enable','off'); set(buttonSolveHandle,'enable','off'); set(buttonSizeHandle,'enable','off'); for (i1 = 1:1:Dim) for (i2 = 1:1:Dim) if (EingabeMatrix(i1,i2) < 0 || EingabeMatrix(i1,i2) > DimMatrix(1)) set(HandleVektor(i1,i2),'foregroundcolor','r'); end end end end end if (strcmp(EntscheidungVar,'Fehler') == 1) close(figureFehler); set(buttonCloseHandle,'enable','on'); set(buttonBackHandle,'enable','on'); set(buttonSolveHandle,'enable','on'); set(buttonSizeHandle,'enable','on'); end if (strcmp(EntscheidungVar,'Erg') == 1) close(figureLoesung); set(buttonCloseHandle,'enable','on'); set(buttonBackHandle,'enable','on'); set(buttonSolveHandle,'enable','on'); set(buttonSizeHandle,'enable','on'); end if (strcmp(EntscheidungVar,'Neu')) close(figureMainHandle); SudokuSolverGUI(); end if (strcmp(EntscheidungVar,'Close') == 1) close(figureMainHandle); end end