<HTML>
<HEAD>
<TITLE>Sudoku Solver</TITLE>
</HEAD>
<BODY TEXT="#000000" BGCOLOR="#F8F8FC">
<H1>Sudoku Solver</H1>
<H3><FONT COLOR="#FF0000">NEU: Auflistung aller Einzelschritte inklusive genauer Erklärungen und Punkte-Bewertung - und mit Goldenen Ketten; jetzt auch mit Eindeutigkeitstest</FONT></H3>
<?
// Einfachste Programmierloesung mit einem einzeiligen (alle Zeilen nebeneinander) Array (mit Index 0 - 80),
// wobei ueber die Funktion row/col/box zu einem gegebenen Index alle (jeweils 9) zu einer
// Zeile, Spalte oder Box gehoerenden Indizes berechnet und als Array zurueckgegeben werden.
// Also: Berechne aus dem Index (0 - 80) eines Feldes die Indizes der zugehoerigen Zeile, Spalte, Box.
// Dabei kann der Eingabe-Index irgendein Element des Feldes sein! D.h. man findet zu einem
// beliebigen Element damit alle Indizes einer Zeile, Spalte und/oder Box, in der das Element steht.
// Die Funktionen row_number, col_number, box_number_x sind nur fuer besser lesbare Ausgabetexte.
function row($index) {
// Pattern: r*9 + i
$r = floor($index/9);
for ($i = 0; $i < 9; $i++) $k[$i] = $r*9 + $i;
return $k;
}
function row_number($index) {
$r = floor($index/9);
return $r;
}
function col($index) {
// Pattern: s + i*9
$c = fmod($index,9);
for ($i = 0; $i < 9; $i++) $l[$i] = $c + $i*9;
return $l;
}
function col_number($index) {
$c = fmod($index,9);
return $c;
}
function box($index) {
// Pattern: (u*3 + t*27) + (i*9 + j)
$r = floor($index/9);
$c = fmod($index, 9); // $index - $r*9;
$t = floor($r/3);
$u = floor($c/3);
$v = $t*27 + $u*3;
$w = 0;
for ($i = 0; $i < 3; $i++) {
for ($j = 0; $j < 3; $j++) {
$m[$w] = $v + $i*9 + $j;
$w++;
}
}
return $m;
}
function box_number_r($index) {
$r = floor($index/9);
$t = floor($r/3); // Geht natuerlich auch in einem Schritt
return $t;
}
function box_number_c($index) {
$c = fmod($index, 9);
$u = floor($c/3);
return $u;
}
// Aus Symmetriegruenden hier beibehalten:
// Fuer Farbsudokus
function frb($index) {
// Pattern: (r*9 + c) + (a*3 + b*27)
$b = floor($index/27);
$rest = fmod($index, 27); // $index - $b*27;
$r = floor($rest/9);
$rest = fmod($rest, 9); // $rest - $r*9;
$a = floor($rest/3);
$rest = fmod($rest, 3); // $rest - $a*3;
$c = floor($rest/1);
$v = $r*9 + $c;
$x = 0;
for ($b = 0; $b < 3; $b++) {
for ($a = 0; $a < 3; $a++) {
$n[$x] = $v + $a*3 + $b*27;
$x++;
}
}
return $n;
}
function show_row($r) {
echo "<TR>\n";
for ($k = 0; $k < 9; $k++) {
$value = $r[$k];
if (count($r) == 9) {
if ($r[$k] === 0) echo "<TD><INPUT TYPE=TEXT VALUE=\"\" SIZE=1 MAXLENGTH=1></TD>\n";
else echo "<TD><B>$r[$k]</B></TD>\n";
}
elseif (count($r) == 18) {
$rest = $r[$k+9];
if ($rest == "") $rest = " ";
if ($r[$k] === 0) echo "<TD><INPUT TYPE=TEXT VALUE=\"\" SIZE=1 MAXLENGTH=1><BR>$rest</TD>\n";
else echo "<TD><B>$r[$k]</B><BR>$rest</TD>\n";
}
if ($k == 2 || $k == 5) echo "<TD>|<BR>|</TD>\n";
}
echo "</TR>\n";
}
function erklaerung() {
global $farbe_gruen, $farbe_rot, $farbe_blau, $farbe_braun, $farbe_lila, $farbe_rotgelb;
echo "<H4>Prinzipen zur Lösung von Sudokus</H4>\n";
echo "Sudoku-Grundregel: Es sollen in jeder Zeile, in jeder Spalte und in jeder Box (3x3-Kästchen) alle Zahlen von 1 bis 9 genau einmal vorkommen. Die Zeilen und Spalten werden hier von oben links an mit 1 bis 9 durchnummeriert, die Boxen werden mit OL (oben links), OM (oben Mitte), OR (oben rechts), ML (Mitte links), MM (Mitte Mitte), ..., bis UR (unten rechts) bezeichnet.\n";
echo "<P>Dieses Programm benutzt 5 Lösungsverfahren mit verschiedener Punkte-Gewichtung, wobei für die Ausdünnung 5 verschiedene Analysemethoden (ebenfalls mit unterschiedlichen Punkten gewichtet) programmiert wurden.\n";
echo "<BR>Dabei wird nach einem Treffer immer wieder bei der einfachsten Methode begonnen, und zusätzlich in der Reihenfolge: Suche immer erst in Zeilen - dadurch sind diese Fälle immer am häufigsten -, dann in Spalten, zuletzt in Boxen.\n";
echo "<P>Bei der Bewertung wird davon ausgegangen, dass zuerst versucht wird, das Sudoku ohne Anschreiben der Reste (Kandidaten) zu lösen. Dabei kommen die Methoden A, B und C zum Einsatz. Kommt man damit nicht weiter, muss man für jede Zelle alle Zahlen aufschreiben, die dafür in Frage kommen: die Kandidaten, die hier als Ganzes oft Rest genannt und auch der Einfachheit halber als eine mehrstellige Zahl (ohne Komma oder andere Trennzeichen) geschrieben werden. Danach versucht man, diese Reste so lange auszudünnen, also zu verkürzen, bis man zu einer eindeutigen Lösung für eine Zelle kommt (Methoden D und E). Das Ausdünnen (Kandidaten-Reduzierung) wird hier mit den wichtigsten 5 Methoden versucht, die weiter unten erklärt werden.\n";
echo "<P>Trial- and Error-Verfahren werden nicht benutzt, sondern nur logisch nachvollziehbare Methoden - dieses Programm soll nicht ein Sudoku lösen, sondern alle Lösungsschritte aufzeigen. Ein \"richtiges\" Sudoku sollte immer ohne \"zufälligen\" Versuch und Irrtum und auf jeden Fall eindeutig gelöst werden können.\n";
echo "<H4>Programm-Neuigkeiten</H4>\n";
echo "<UL>\n";
echo "<LI>Die bei <A HREF=\"http://sourceforge.net/projects/php-sudoku/\">http://sourceforge.net/projects/php-sudoku/</A> gefundenen 1 Million Sudokus (Dank an Michael Jentsch) wurden durchgerechnet. Sie sind aber etwas einfacher als die hier bisher gesammelten mehr als 22000 Sudokus, denn 965351 Sudokus konnte ohne Ausdünnung gerechnet werden, 30420 Sudokus (3 %) konnten nur mit Ausdünnung gelöst werden, und nur 4229 (0.4 %) Sudokus konnten mit diesem Programm nicht gelöst werden, hatten aber eine eindeutige Lösung, die sich durch Trial&Error aber im Allgemeinen auch sehr einfach finden ließ. Interessant wieder: X-Wings waren 4483 dabei, aber Goldene Ketten 47581, fast 11 Mal so viel (August 2010).</LI><P>\n";
echo "<LI>Die jeweils neu gefundene Zahl wird mit spitzen Klammern, also z.B. >7< markiert (Juli 2010).</LI><P>\n";
echo "<LI>Die Beispiele wurden in ihrem Aufbau verändert und auf eine extra Webseite gebracht, damit die eigentliche Seite nicht zu lang ist (Juni 2010).</LI><P>\n";
echo "<LI>Jetzt gibt es die Möglichkeit, ein Sudoku, das mit den hier programmierten Methoden nicht gelöst werden kann, auf eindeutige Lösbarkeit testen zu lassen. Von 3400 untersuchten hier nicht lösbaren Sudokus waren etwa 630 eindeutig lösbar, über 2500 hatten mehr als eine Lösung - mit bis zu 52000 verschiedenen Lösungen - und etwa 230 waren prinzipiell nicht lösbar (Mai/Juni 2010).</LI><P>\n";
echo "<LI>Die Punkte-Bewertung wurde geändert, insbesondere wurden die A-Methoden getrennt, da man eine fehlende Zahl in Boxen einfacher (1 Punkt) sieht als in Zeilen oder Spalten (2 Punkte); und eine jeweils 9. fehlende Zahl wird gar nicht bewertet. Außerdem werden die Felder gezählt und mit je 1 Punkt bewertet, in denen zur Ausdünnung Reste eingetragen werden müssen (April/Mai 2010).</LI><P>\n";
echo "<LI>Jetzt wurden die Erklärungen und Beispiele zum Verständnis der Lösungsstrategien vollkommen überarbeitet und dabei auch Fehler behoben (Sorry!). Vielleicht kann man das Ganze nun besser verstehen... (März 2010).</LI><P>\n";
echo "<LI>Es wurden auch schon über 200 Stunden für die Analyse der über 20000 Beispiele aufgewendet, z.B. für die verschiedenen Beispiel-Listen (höchste Punktzahl, längste Goldene Kette, lösbar nur durch Quadrupel, usw.), - insbesondere ein paar Dutzend Prozeduren geschrieben, um das Ganze einigermaßen automatisch zu erzeugen, da es immer wieder aktualisiert wird. Auch die beiden Reduzierungsläufe kosteten einiges an Zeit... (Februar 2010).</LI><P>\n";
echo "<LI>Endlich wurde auch die Ausdünn-Methode X-Wing programmiert (in 5 Stunden von nun insgesamt etwa 300 Stunden Programmierarbeit). Leider erbrachte das aber auch nur knapp 1% mehr Lösungen (gegenüber 15% bei der Goldenen Kette!)... Aber immerhin hat die X-Wing-Methode den Vorteil, auch bei Zellen mit mehr als 2 Kandidaten zu funktionieren (gegenüber der Goldenen Ketten) - weswegen die Programmierung doch sinnvoll ist (Januar 2010).</LI><P>\n";
echo "<LI>Dem entsprechend wurde auch die Reihenfolge der Ausdünn-Methoden umgestellt: Zuerst kommen nun die einfachen Zeilen-/Spalten-/Box-Test-Methoden, danach erst die N-Tupel, dann X-Wing und am Ende die Goldenen Ketten (Januar 2010).</LI><P>\n";
echo "<LI>Es wurde die Goldene Kette in einer zweiten Version programmiert: Kürzere Kette werden zuerst gefunden (Maximallänge 14 - gegenüber vorher 23). Erstaunlichstes Ergebnis überhaupt aber war, dass durch die Programmierung der Goldenen Ketten 15% mehr Lösungen gefunden werden konnten als voher - und zwar auch noch fast genau so viele wie durch die Methode der 2-Tupel (Doppel) gefunden werden! Das Verfahren ist damit eine sehr wichtige Methode, aber auch aufwändiger: Es wurden schon Sudokus mit einer Rechenzeit von über 20 Sekunden (auf dem aktuellen Webserver) gelöst (bei der ersten Version aber wesentlich länger) - 30 Sekunden stehen bei Web-Anwendungen im Allgemeinen nur zur Verfügung (Dezember 2009; erste Version mit Rekursion: November 2009).</LI><P>\n";
echo "<LI>Die Programmierung der N-Tupel wurde verbessert, so dass nun auch N-Tupel gefunden werden, deren einzelne Mitglieder alle aus weniger als N Zahlen bestehen. Die gewählte Methode erkennt nun etwa 99.9% dieser Fälle - eine nochmals erweiterte Programmierung brachte nur ein Beispiel aus 10000 Sudokus, kostet aber 15 % mehr an Laufzeit und wird deswegen weggelassen (die Programmteile sind auskommentiert und könnten auf dem eigenen Rechner aktiviert werden)... Versteckte N-Tupel müssen nicht extra programmiert werden, da sie immer mit direkten N-Tupel korrespondieren (Oktober 2009).</LI><P>\n";
echo "<LI>Es fehlt die Programmierung von weiteren Ausdünn-Methoden wie z.B.: Swordfish (Erweiterung von X-Wing), und Colouring und Multicolouring, die aber nicht so viel zusätzliche Sudokus lösen werden können wie die bisherigen Methoden (auch X-Wing hatte ja nicht so viel gebracht...).</LI><P>\n";
echo "</UL>\n";
echo "<H4>Fünf Sudoku-Lösungsmethoden (A bis E)</H4>\n";
echo "<OL TYPE=\"A\">\n";
echo "<LI>Einfachste Methode (Wert: 1 Punkt innerhalb Boxen, 2 Punkte innerhalb Zeilen/Spalten, 0 Punkte bei der 9. fehlenden Zahl; Farbmarkierung: <FONT COLOR=$farbe_gruen>Grün</FONT>): Direkte Dreier-Methode oder eindeutige Stelle: Bestimme die fehlende dritte Zahl in drei zusammen liegenden (nebeneinander oder untereinander) Boxen. D.h.: Findet man in zwei von drei zusammen liegenden Boxen eine bestimmte Zahl, sucht man in der dritten Box nach einem eindeutigen Ort, an dem diese Zahl stehen kann. In vielen Fällen ist es auch einfach die einzige Stelle, an der eine bestimmte Zahl nur stehen kann, insbesondere beim Durchsuchen von Zeilen und Spalten.\n";
echo "<BR>Bemerkung: In knapp 95 % aller Lösungsschritte findet man eine Zahl (und den dazugehörenden Ort) mit dieser Methode, davon 90 % mit der Suche innerhalb von Boxen!</LI>\n";
echo "<P>Einfacher Fall:\n";
echo "<BR>In der dritten Box (OR) kann die Zahl 7 nur in der dritten Zeile sein; damit bleibt die letzte Spalte als einzig möglicher Ort übrig (mit kleinem x markiert).\n";
echo "<BR>PS: Der Übersichtlichkeit wegen wurden viele Felder nicht ausgefüllt, da deren Inhalt ohne Bedeutung ist; ebenso fehlen im Allgemeinen die letzten Zeilen der Beispiel-Sudokus.\n";
echo "<P><TABLE BORDER=1 CELLSPACING=4 CELLPADDING=4>\n";
echo "<TR><TD>\n";
echo "<TABLE CELLSPACING=0 CELLPADDING=4>\n";
show_row(array(0, 0, 0, 0, 7, 0, 0, 0, 0));
show_row(array(7, 0, 0, 0, 0, 0, 0, 0, 0));
show_row(array(0, 0, 0, 0, 0, 1, 4, 5, "<INPUT TYPE=TEXT VALUE=\"x\" SIZE=1 MAXLENGTH=1>"));
echo "<TR><TD COLSPAN=11><HR></TD></TR>\n";
show_row(array("...", "...", "...", "...", "...", "...", "...", "...", "..."));
echo "</TABLE>\n";
echo "</TD></TR>\n";
echo "</TABLE>\n";
echo "<P>Komplexerer Fall:\n";
echo "<BR>Oft muss auch in den Spalten (bzw. Zeilen, wenn die drei Boxen untereinander liegen) nachgesehen werden, ob eine Stelle für die bestimmte Zahl frei ist. In diesem Beispiel kann die Zahl 7 wieder nur in der dritten Zeile der rechten Box (OR) liegen. Da aber in der 8. Spalte in der darunter liegenden Box (MR) schon eine 7 steht, bleibt wieder nur die letzte Spalte (mit kleinem x markiert) als Zielort übrig.\n";
echo "<P><TABLE BORDER=1 CELLSPACING=4 CELLPADDING=4>\n";
echo "<TR><TD>\n";
echo "<TABLE CELLSPACING=0 CELLPADDING=4>\n";
show_row(array(0, 0, 0, 0, 7, 0, 0, 0, 0));
show_row(array(7, 0, 0, 0, 0, 0, 0, 0, 0));
show_row(array(0, 0, 0, 0, 0, 1, 4, 0, "<INPUT TYPE=TEXT VALUE=\"x\" SIZE=1 MAXLENGTH=1>"));
echo "<TR><TD COLSPAN=11><HR></TD></TR>\n";
show_row(array(0, 0, 0, 0, 0, 0, 0, 7, 0));
show_row(array("...", "...", "...", "...", "...", "...", "...", "...", "..."));
echo "</TABLE>\n";
echo "</TD></TR>\n";
echo "</TABLE>\n";
echo "<LI>Erweiterte oder indirekte Dreier-Methode (Wert: 4 Punkte, Farbmarkierung: <FONT COLOR=$farbe_rot>Rot</FONT>): Bestimme den Ort der dritten Zahl ohne genaue Kenntnis des Ortes der zweiten Zahl:\n";
echo "<BR>Hier nutzt man aus, dass die Position der zweiten Zahl zwar noch nicht genau bekannt ist, aber auf eine Zeile oder Spalte einer Box beschränkt werden kann. Dann folgt der Ort für die dritte Zahl analog der oben beschriebenen Methode A. Dieses Verfahren kann in bestimmten Fällen auch ohne Kenntnis der ersten Zahl funktionieren.</LI>\n";
echo "<P>Einfacher Fall:\n";
echo "<BR>Im einfachen Fall weiß man, dass in der rechten Box (OR) die Zahl 6 nur in der zweiten Zeile sein kann, da die erste Zeile nicht in Frage kommt (wegen der 6 in Spalte 9) - die genaue Position der Zahl 6 in der mittleren Zeile von Box OR ist aber noch unbekannt. Trotzdem kann man daraus schließen, dass in der ersten Box (OL) die 6 nur in der dritten Zeile sein kann; in dieser Zeile bleibt dann nur die zweite Spalte als einzig möglicher Ort übrig (mit kleinem x markiert).\n";
echo "<P><TABLE BORDER=1 CELLSPACING=4 CELLPADDING=4>\n";
echo "<TR><TD>\n";
echo "<TABLE CELLSPACING=0 CELLPADDING=4>\n";
show_row(array(5, 4, 7, 0, 0, 0, 2, 8, 0));
show_row(array(8, 0, 0, 0, 0, 2, 0, 0, 0));
show_row(array(2, "<INPUT TYPE=TEXT VALUE=\"x\" SIZE=1 MAXLENGTH=1>", 3, 0, 0, 0, 5, 4, 9));
echo "<TR><TD COLSPAN=11><HR></TD></TR>\n";
show_row(array(0, 0, 0, 0, 0, 0, 0, 0, 6));
show_row(array("...", "...", "...", "...", "...", "...", "...", "...", "..."));
echo "</TABLE>\n";
echo "</TD></TR>\n";
echo "</TABLE>\n";
echo "<P>Komplexerer Fall:\n";
echo "<BR>Wegen der Zahl 7 in der rechten mittleren Box (MR) kann in der davor liegenden Box (MM) die 7 nicht in Zeile 5 stehen. Damit bleiben als möglicher Ort für die 7 in dieser Box nur die beiden Positionen in der Spalte 5 übrig (mit kleinem a markiert).\n";
echo "<BR>Nun kann man ähnlich wie im einfachen Fall folgern, dass in der darüber liegenden Box (OM) die Zahl 7 nur in der oberen Zeile sein kann (Spalte 4 oder 6), wobei die genaue Position aber noch unbekannt ist. Also muss in der rechts davon liegenden Box (OR) die 7 wieder in der 3. Zeile sein. Da aber in der 8. Spalte in der darunter liegenden Box (MR) schon eine 7 steht, bleibt wieder nur die letzte Spalte (mit kleinem x markiert) als Zielort übrig.\n";
echo "<P>Alternativ kann man auch argumentieren, dass die Zahl 7 in der 3. Zeile nicht in Box OL stehen kann (in dieser Box ist schon eine 7), auch nicht in Box OM wegen der 7 irgendwo in Spalte 5 von Box MM (siehe oben, mit kleinem a markiert), aber auch nicht in Spalte 8 der Box OR (siehe oben), und somit bleibt dort nur die Spalte 9 (mit kleinem x markiert) als Zielort übrig.\n";
echo "<P><TABLE BORDER=1 CELLSPACING=4 CELLPADDING=4>\n";
echo "<TR><TD>\n";
echo "<TABLE CELLSPACING=0 CELLPADDING=4>\n";
show_row(array(0, 0, 0, 0, 0, 0, 0, 0, 0));
show_row(array(7, 0, 0, 0, 0, 0, 0, 0, 0));
show_row(array(0, 0, 0, 2, 0, 1, 4, 0, "<INPUT TYPE=TEXT VALUE=\"x\" SIZE=1 MAXLENGTH=1>"));
echo "<TR><TD COLSPAN=11><HR></TD></TR>\n";
show_row(array(0, 0, 0, 3, "<INPUT TYPE=TEXT VALUE=\"a\" SIZE=1 MAXLENGTH=1>", 2, 0, 0, 0));
show_row(array(0, 0, 0, 0, 0, 0, 0, 7, 0));
show_row(array("...", "...", "...", 5, "<INPUT TYPE=TEXT VALUE=\"a\" SIZE=1 MAXLENGTH=1>", 8, "...", "...", "..."));
echo "</TABLE>\n";
echo "</TD></TR>\n";
echo "</TABLE>\n";
echo "<LI>Einzig mögliche Zahl (Wert: 6 Punkte, Farbmarkierung: <FONT COLOR=$farbe_blau>Blau</FONT>): Einzige noch fehlende Zahl an einem bestimmtem Ort:\n";
echo "<BR>Man untersucht für einen Ort, welche der 9 Zahlen dort stehen könnten, wobei die Sudoku-Regeln berücksichtigt werden müssen. Bleibt nur eine Zahl übrig, hat man die Lösung für diese Stelle gefunden. Das klingt zwar einfach, ist aber nicht so leicht zu erkennen.</LI>\n";
echo "<P>Beispiel: Die einzige Zahl an der Position Zeile 3 und Spalte 4 (mit kleinem x markiert) kann nur die Zahl 7 sein, weil alle anderen Zahlen schon in gleicher Zeile (1, 4, 8, 9), in gleicher Spalte (2, 5), bzw. in gleicher Box (1, 2, 3, 6) vorhanden sind.\n";
echo "<P><TABLE BORDER=1 CELLSPACING=4 CELLPADDING=4>\n";
echo "<TR><TD>\n";
echo "<TABLE CELLSPACING=0 CELLPADDING=4>\n";
show_row(array(0, 0, 0, 2, 6, 0, 0, 0, 0));
show_row(array(0, 0, 0, 0, 0, 3, 0, 0, 0));
show_row(array(0, 8, 0, "<INPUT TYPE=TEXT VALUE=\"x\" SIZE=1 MAXLENGTH=1>", 0, 1, 4, 0, 9));
echo "<TR><TD COLSPAN=11><HR></TD></TR>\n";
show_row(array(0, 0, 0, 5, 0, 0, 0, 7, 0));
show_row(array("...", "...", "...", "...", "...", "...", "...", "...", "..."));
echo "</TABLE>\n";
echo "</TD></TR>\n";
echo "</TABLE>\n";
echo "<LI>Vollständige Ausdünnung mit einstelliger Restzahl bzw. einziger Kandidatenzahl (Wert: 1 Basis-Punkt, Farbmarkierung: <FONT COLOR=$farbe_braun>Braun</FONT>): Hat man nach einem oder mehreren Ausdünnschritten einen Rest so weit verkleinert, dass er nur noch aus einer Zahl besteht, ist diese Zahl die Lösung für die betrachtete Stelle.</LI>\n";
echo "<P>Ausdünnung:\n";
echo "<BR>Hier wird davon ausgegangen, dass zuerst versucht wird, das Sudoku ohne Anschreiben der Reste (das sind die Kandidaten, also die möglichen Zahlen für die jeweilige Stelle) zu lösen (Methoden A, B und C). Kommt man damit nicht weiter, muss man für jede freie Stelle alle Zahlen aufschreiben, die für diese Stelle in Frage kommen (also die dafür überhaupt noch möglichen Zahlen): Das sind die Kandidaten für die jeweilige Stelle, die hier als Ganzes \"Rest\" genannt und auch der Einfachheit halber als eine mehrstellige Zahl (ohne Komma oder andere Trennzeichen unterhalb der Eingabefelder) geschrieben werden.\n";
echo "<BR>Danach versucht man, diese Reste so lange \"auszudünnen\", also zu verkürzen, bis man zu einer eindeutigen Lösung für eine Stelle kommt (Methoden D und E). Die Ausdünn-Methoden I bis V werden im nächsten Abschnitt ausführlich beschrieben.\n";
echo "<P>Beispiel:\n";
echo "<BR>Nach der Ausdünn-Methode I (siehe weiter unten im nächsten Abschnitt) kommt die Zahl 9 innerhalb der zweiten Zeile nur in der ersten Box (OL) vor: Daher muss die 9 dort sein (auch wenn man die Position innerhalb der zweiten Zeile noch nicht weiß) - sie kann also nicht in der dritten Zeile dieser Box noch einmal vorkommen. Daher kann man aus den Resten dieser Zeile in der Box OL den Kandidaten 9 streichen (d.h.: 249 wird zu 24, 39 wird zu 3).\n";
echo "<BR>Damit bleibt an der Position Zeile 3 und Spalte 3 (mit kleinem x markiert) nur noch die 3 als Kandidat übrig. Also hat man einen eindeutigen Rest an dieser Stelle gefunden.\n";
echo "<P><TABLE BORDER=1 CELLSPACING=4 CELLPADDING=4>\n";
echo "<TR><TD>\n";
echo "<TABLE CELLSPACING=0 CELLPADDING=4>\n";
show_row(array(5, 0, 0, 9, 8, 7, 0, 0, 0,
"", "246", "36", "", "", "", "1234", "1234", "1234"));
show_row(array(1, 0, 0, 0, 0, 4, 8, 6, 5,
"", "279", "379", "23", "23", "", "", "", ""));
show_row(array(8, 0, "<INPUT TYPE=TEXT VALUE=\"x\" SIZE=1 MAXLENGTH=1>", 1, 6, 5, 7, 0, 0,
"", "249", "39", "", "", "", "", "2349", "2349"));
echo "<TR><TD COLSPAN=11><HR></TD></TR>\n";
show_row(array(0, 0, 4, 0, 0, 0, 0, 0, 0));
show_row(array(0, 3, 2, 0, 0, 0, 0, 0, 0));
show_row(array("...", "...", "...", "...", "...", "...", "...", "...", "..."));
echo "</TABLE>\n";
echo "</TD></TR>\n";
echo "</TABLE>\n";
echo "<LI>Vollständige Ausdünnung mit einzig auftretender Restzahl (alleine auftretender Kandidat) (Wert: 4 Basis-Punkte, Farbmarkierung: <FONT COLOR=$farbe_lila>Lila</FONT>): Hat man nach einem oder mehreren Ausdünnschritten mehrere Reste so weit verkleinert, dass eine bestimmte Zahl nur noch an einer einzigen Stelle innerhalb der Reste einer Zeile, einer Spalte oder einer Box vorkommt, ist diese Zahl Lösung für diese Stelle.</LI>\n";
echo "<P>Beispiel:\n";
echo "<BR>Nach der Ausdünn-Methode III (siehe weiter unten im nächsten Abschnitt) findet man in der Box OR das Reste-Paar 79 zwei Mal. Die Zahlen 7 und 9 müssen also an diesen beiden Stellen auftreten. Damit können in allen anderen Resten dieser Box die Zahlen 7 und 9 gestrichen werden. Daraus folgt, dass an der Position Zeile 1 und Spalte 4 (mit kleinem x markiert) die Zahl 7 stehen muss.\n";
echo "<P><TABLE BORDER=1 CELLSPACING=4 CELLPADDING=4>\n";
echo "<TR><TD>\n";
echo "<TABLE CELLSPACING=0 CELLPADDING=4>\n";
show_row(array(2, 6, 4, "<INPUT TYPE=TEXT VALUE=\"x\" SIZE=1 MAXLENGTH=1>", 9, 0, 0, 8, 3,
"", "", "", "157", "", "15", "157", "", ""));
show_row(array(0, 0, 0, 2, 0, 0, 6, 4, 0,
"1579", "1579", "1579", "", "3578", "1358", "", "", "79"));
show_row(array(3, 8, 0, 0, 6, 4, 0, 2, 0,
"", "", "1579", "1357", "", "", "1579", "", "79"));
echo "<TR><TD COLSPAN=11><HR></TD></TR>\n";
show_row(array(0, 0, 0, 6, 0, 2, 8, 0, 1));
show_row(array(0, 0, 0, 8, 1, 7, 0, 0, 5));
show_row(array("...", "...", "...", "...", "...", "...", "...", "...", "..."));
echo "</TABLE>\n";
echo "</TD></TR>\n";
echo "</TABLE>\n";
echo "</OL>\n";
echo "<H4>Fünf Methoden zur Ausdünnung der Reste (I bis V)</H4>\n";
echo "Der Begriff der Ausdünnung zur Verkürzung der Reste wurde im vorherigen Abschnitt unter Methode D schon erlätert. Im Allgemeinen sind, um eine Lösung zu finden, immer mehrere Ausdünnschritte notwendig (bis zu 23 direkt nacheinander wurden schon beobachtet!). Manche Schritte helfen dabei nicht zur Lösungsfindung, aber das weiß man vorher nicht.\n";
echo "<BR>Über die Hälfte (56 %) aller hier berechneten Sudokus sind nur durch Anschreiben der Reste und anschließender Ausdünnung lösbar!\n";
echo "<BR>In den folgenden Beispielen werden oft nur Teile eines Sudokus mit entsprechenden Resten dargestellt, um das Ganze übersichtlicher zu machen; es sind Ausschnitte aus aktuellen Sudokus.\n";
echo "<OL TYPE=\"I\">\n";
echo "<LI>Box-Test der Reste in einer Zeile oder Spalte: Man sieht in den Resten einer Box nach, ob innerhalb einer Zeile bzw. Spalte eine Zahl vorkommt, die nur genau in dieser Box auftaucht. Diese Zahl muss also innerhalb dieser Box in der gefundenen Zeile bzw. Spalte stehen (wobei die genaue Position noch unbekannt ist), sie kann dann aber aus den anderen Zeilen bzw. Spalten innerhalb dieser Box gestrichen werden. Dies ist die am häufigsten auftretende Methode, um die Reste auszudünnen: 48 %!</LI>\n";
echo "<BR>Bewertung: Für jedes Vorkommen gibt es 4 Punkte.\n";
echo "<P>Beispiel:\n";
echo "<P><TABLE BORDER=1 CELLSPACING=4 CELLPADDING=4>\n";
echo "<TR><TD>\n";
echo "<TABLE CELLSPACING=0 CELLPADDING=4>\n";
show_row(array(0, 5, 3, 4, 7, 9, 0, 6, 0,
"28", "", "", "", "", "", "12", "", "128"));
show_row(array(7, 0, 0, 0, 0, 5, 0, 0, 4,
"", "1289", "12689", "136", "136", "", "1239", "12389", ""));
show_row(array(4, 0, 0, 8, 0, 2, 0, 7, 0,
"", "19", "169", "", "136", "", "1359", "", "1359"));
echo "<TR><TD COLSPAN=11><HR></TD></TR>\n";
show_row(array(1, 6, 0, 0, 0, 0, 8, 0, 0));
show_row(array("...", "...", "...", "...", "...", "...", "...", "...", "..."));
echo "</TABLE>\n";
echo "</TD></TR>\n";
echo "</TABLE>\n";
echo "<BR>Hier findet man z.B. die Zahl 1: Sie ist innerhalb der ersten Zeile nur in den Resten der rechten Box OR vorhanden (rot gefärbte Reste). Also kann man in den anderen Zeilen dieser Box diese Zahl aus den Resten streichen - das wird hier durch die Darstellung in eckigen Klammern hervorgehoben. Damit bleibt übrig:\n";
echo "<P><TABLE BORDER=1 CELLSPACING=4 CELLPADDING=4>\n";
echo "<TR><TD>\n";
echo "<TABLE CELLSPACING=0 CELLPADDING=4>\n";
show_row(array(0, 5, 3, 4, 7, 9, 0, 6, 0,
"28", "", "", "", "", "", "<FONT COLOR=$farbe_rotgelb>12</FONT>", "", "<FONT COLOR=$farbe_rotgelb>128</FONT>"));
show_row(array(7, 0, 0, 0, 0, 5, 0, 0, 4,
"", "1289", "12689", "136", "136", "", "[1]239", "[1]2389", ""));
show_row(array(4, 0, 0, 8, 0, 2, 0, 7, 0,
"", "19", "169", "", "136", "", "[1]359", "", "[1]359"));
echo "<TR><TD COLSPAN=11><HR></TD></TR>\n";
show_row(array(1, 6, 0, 0, 0, 0, 8, 0, 0));
show_row(array("...", "...", "...", "...", "...", "...", "...", "...", "..."));
echo "</TABLE>\n";
echo "</TD></TR>\n";
echo "</TABLE>\n";
echo "<LI>Zeilen-/Spalten-Test der Reste innerhalb einer Box: Man sieht in den Resten nach, ob innerhalb einer Box eine Zahl vorkommt, die nur genau in einer Zeile bzw. Spalte dieser Box auftaucht - diese Zahl muss dann in dieser Zeile bzw. Spalte dieser Box stehen (wobei die genaue Position noch unbekannt ist). Dann kann man in den anderen Resten dieser Zeile bzw. Spalte außerhalb der Box diese Zahl streichen.</LI>\n";
echo "<BR>Bewertung: Für jedes Vorkommen gibt es 6 Punkte.\n";
echo "<P>Beispiel:\n";
echo "<P><TABLE BORDER=1 CELLSPACING=4 CELLPADDING=4>\n";
echo "<TR><TD>\n";
echo "<TABLE CELLSPACING=0 CELLPADDING=4>\n";
show_row(array(3, 0, 5, 0, 0, 0, 0, 0, 6,
"", "789", "", "12789", "12489", "124789", "1479", "1479", ""));
show_row(array(0, 4, 0, 5, 0, 6, 0, 2, 0,
"178", "", "1789", "", "1389", "", "1379", "", "1379"));
show_row(array(6, 0, 2, 0, 0, 0, 8, 0, 0,
"", "79", "", "1379", "1349", "13479", "", "134579", "134579"));
echo "<TR><TD COLSPAN=11><HR></TD></TR>\n";
show_row(array(9, 1, 0, 4, 7, 2, 0, 0, 0));
show_row(array("...", "...", "...", "...", "...", "...", "...", "...", "..."));
echo "</TABLE>\n";
echo "</TD></TR>\n";
echo "</TABLE>\n";
echo "<BR>Hier findet man z.B. die Zahl 1: Sie ist in den Resten der Box OL nur in der zweiten Zeile vorhanden (rot gefärbte Reste), nicht in den anderen Zeilen dieser Box. Also kann man in den anderen Resten dieser Zeile in den anderen beiden Boxen diese Zahl streichen (durch die Darstellung in eckigen Klammern hervorgehoben). Damit bleibt übrig:\n";
echo "<P><TABLE BORDER=1 CELLSPACING=4 CELLPADDING=4>\n";
echo "<TR><TD>\n";
echo "<TABLE CELLSPACING=0 CELLPADDING=4>\n";
show_row(array(3, 0, 5, 0, 0, 0, 0, 0, 6,
"", "789", "", "12789", "12489", "124789", "1479", "1479", ""));
show_row(array(0, 4, 0, 5, 0, 6, 0, 2, 0,
"<FONT COLOR=$farbe_rotgelb>178</FONT>", "", "<FONT COLOR=$farbe_rotgelb>1789</FONT>", "", "[1]389", "", "[1]379", "", "[1]379"));
show_row(array(6, 0, 2, 0, 0, 0, 8, 0, 0,
"", "79", "", "1379", "1349", "13479", "", "134579", "134579"));
echo "<TR><TD COLSPAN=11><HR></TD></TR>\n";
show_row(array(9, 1, 0, 4, 7, 2, 0, 0, 0));
show_row(array("...", "...", "...", "...", "...", "...", "...", "...", "..."));
echo "</TABLE>\n";
echo "</TD></TR>\n";
echo "</TABLE>\n";
echo "<LI>Man sucht in einer Zeile, Spalte oder Box nach N-Tupel, also danach, dass bestimmte Kandidaten an nur wenigen Stellen auftreten: Genauer heißt das, dass man N zusammen gehörende Stellen (innerhalb einer Zeile, Spalte oder Box) sucht, in denen genau N verschiedene Kandidaten auftreten. Wenn an N Stellen alle oder ein Teil der N betrachteten Kandidaten stehen, können diese Kandidaten nur an diesen N Stellen auftreten (wobei die Verteilung noch unbekannt ist), diese Kandidaten können dann aber aus den anderen Resten gestrichen werden.</LI>\n";
echo "<BR>Es gibt 2-Tupel (Doppel), 3-Tupel (Tripel), 4-Tupel (Quadrupel), 5-Tupel (Pentupel), 6-Tupel und 7-Tupel (8-Tupel machen keinen Sinn, da dann die neunte Zahl eindeutig ist und somit direkt gefunden werden kann).\n";
echo "<BR>Bewertung: Für jedes N-Tupel gibt es 2*N Punkte.\n";
echo "<P>Einfaches Beispiel mit 2-Tupel (Doppel):";
echo "<P><TABLE BORDER=1 CELLSPACING=4 CELLPADDING=4>\n";
echo "<TR><TD>\n";
echo "<TABLE CELLSPACING=0 CELLPADDING=4>\n";
show_row(array(6, 0, 2, 0, 1, 0, 8, 0, 0,
"", "79", "", "79", "", "3479", "", "34579", "34579"));
show_row(array(0, 4, 0, 5, 0, 6, 0, 2, 0,
"189", "", "179", "", "3789", "", "1379", "", "1379"));
show_row(array(3, 0, 5, 0, 0, 0, 0, 0, 6,
"", "1789", "", "2789", "24789", "2479", "1479", "1479", ""));
echo "<TR><TD COLSPAN=11><HR></TD></TR>\n";
show_row(array(7, 0, 8, 4, 0, 0, 0, 0, 0));
show_row(array(0, 0, 0, 3, 0, 8, 0, 0, 0));
show_row(array("...", "...", "...", "...", "...", "...", "...", "...", "..."));
echo "</TABLE>\n";
echo "</TD></TR>\n";
echo "</TABLE>\n";
echo "<BR>Hier findet man z.B. in der ersten Zeile das 2-Tupel 79 (Doppel: 79, 79), als rot gefärbte Reste markiert; die beiden Kandidaten 7 und 9 müssen also an diesen beiden Stellen sein. Also kann man in den anderen Resten dieser Zeile diese beiden Zahlen streichen (durch die Darstellung in eckigen Klammern hervorgehoben). Damit bleibt übrig:\n";
echo "<P><TABLE BORDER=1 CELLSPACING=4 CELLPADDING=4>\n";
echo "<TR><TD>\n";
echo "<TABLE CELLSPACING=0 CELLPADDING=4>\n";
show_row(array(6, 0, 2, 0, 1, 0, 8, 0, 0,
"", "<FONT COLOR=$farbe_rotgelb>79</FONT>", "", "<FONT COLOR=$farbe_rotgelb>79</FONT>", "", "34[7][9]", "", "345[7][9]", "345[7][9]"));
show_row(array(0, 4, 0, 5, 0, 6, 0, 2, 0,
"189", "", "179", "", "3789", "", "1379", "", "1379"));
show_row(array(3, 0, 5, 0, 0, 0, 0, 0, 6,
"", "1789", "", "2789", "24789", "2479", "1479", "1479", ""));
echo "<TR><TD COLSPAN=11><HR></TD></TR>\n";
show_row(array(7, 0, 8, 4, 0, 0, 0, 0, 0));
show_row(array(0, 0, 0, 3, 0, 8, 0, 0, 0));
show_row(array("...", "...", "...", "...", "...", "...", "...", "...", "..."));
echo "</TABLE>\n";
echo "</TD></TR>\n";
echo "</TABLE>\n";
echo "<P>Kurzes Beispiel mit 3-Tupel (Tripel):\n";
echo "<BR>Hier findet man in der Box OM (und in der 5. Spalte) das 3-Tupel 235 (Tripel: 235, 23, 25). Damit können in allen anderen Resten dieser Box (und in der 5. Spalte) die Zahlen 2, 3 und 5 gestrichen werden.\n";
echo "<P><TABLE BORDER=1 CELLSPACING=4 CELLPADDING=4>\n";
echo "<TR><TD>\n";
echo "<TABLE CELLSPACING=0 CELLPADDING=4>\n";
show_row(array(0, 4, 0, 0, 0, 9, 0, 1, 0,
"", "", "", "2357", "235", "", "", "", ""));
show_row(array(0, 1, 0, 6, 0, 8, 0, 0, 5,
"", "", "", "", "23", "", "", "", ""));
show_row(array(0, 0, 3, 0, 0, 0, 0, 0, 0,
"", "", "", "12457", "25", "12457", "", "", ""));
echo "<TR><TD COLSPAN=11><HR></TD></TR>\n";
show_row(array(0, 0, 0, 0, 7, 0, 0, 0, 0));
show_row(array(0, 0, 0, 0, 4, 0, 0, 0, 0));
show_row(array("...", "...", "...", "...", 1, "...", "...", "...", "..."));
echo "</TABLE>\n";
echo "</TD></TR>\n";
echo "</TABLE>\n";
echo "<P>Relativ häufig (in etwa 10% aller N-Tupel-Fälle) findet man noch 4-Tupel (z.B. das Quadrupel 1479 mit: 147, 17, 79, 49), aber 5-Tupel, 6-Tupel und 7-Tupel sind sowohl noch seltener (2 %) als auch schwieriger zu erkennen...\n";
echo "<LI>X-Wing-Methode: Man sieht in den Resten nach, ob es zwei Zeilen gibt, in denen in den Resten eine bestimmte Zahl in genau zwei Spalten vorkommt, wobei aber die Position der gefundenen Spalten in beiden Zeilen übereinstimmen muss. Dann weiß man, dass diese Zahl entweder als erste in der ersten Zeile und als zweite in der zweiten Zeile vorkommen muss oder umgekehrt als zweite in der ersten Zeile und dann als erste in der zweite Zeile. Diese 4 Möglichkeiten bilden das \"X\". Also kann man in den Spalten, die zu dem \"X\" gehören, diese Zahl in allen anderen Zeilen streichen.</LI>\n";
echo "<P>Das Ganze gilt entsprechend für Spalten: Man sieht in den Resten nach, ob es zwei Spalten gibt, in denen in den Resten eine bestimmte Zahl in genau zwei Zeilen vorkommt, wobei aber die Position der gefundenen Zeilen in beiden Spalten übereinstimmen muss. Dann kann man in den Zeilen, die zu dem \"X\" gehören, diese Zahl in allen anderen Spalten streichen.\n";
echo "<BR>Bewertung: Für jedes Vorkommen gibt es 10 Punkte.\n";
echo "<P>Beispiel:\n";
echo "<P><TABLE BORDER=1 CELLSPACING=4 CELLPADDING=4>\n";
echo "<TR><TD>\n";
echo "<TABLE CELLSPACING=0 CELLPADDING=4>\n";
show_row(array(8, 0, 3, 9, 0, 2, 1, 4, 7,
"", "56", "", "", "56", "", "", "", ""));
show_row(array(0, 0, 9, 0, 4, 1, 8, 3, 0,
"567", "2567", "", "56", "", "", "", "", "25"));
show_row(array(0, 0, 1, 7, 3, 8, 6, 9, 0,
"45", "245", "", "", "", "", "", "", "25"));
echo "<TR><TD COLSPAN=11><HR></TD></TR>\n";
show_row(array(0, 0, 8, 0, 2, 9, 3, 0, 0,
"1457", "1457", "", "56", "", "", "", "167", "146"));
show_row(array(3, 0, 6, 8, 0, 4, 2, 0, 9,
"", "157", "", "", "157", "", "", "17", ""));
show_row(array(2, "...", "...", "...", "...", "...", "...", 5, "..."));
echo "</TABLE>\n";
echo "</TD></TR>\n";
echo "</TABLE>\n";
echo "<BR>Hier findet man z.B. für die Zahl 5: Sie ist in den Resten der ersten Zeile nur in Spalte 2 und 5 vorhanden, aber auch in fünften Zeile nur in Spalte 2 und 5 (diese Positionen bilden das namensgebende \"X\"). An zwei gegenüberliegenden Stellen des \"X\" muss also die Zahl 5 liegen (rot gefärbte Reste), und deshalb kann in den anderen Zeilen die 5 in den Spalten 2 und 5 gestrichen werden (durch die Darstellung in eckigen Klammern hervorgehoben). Damit bleibt übrig:\n";
echo "<P><TABLE BORDER=1 CELLSPACING=4 CELLPADDING=4>\n";
echo "<TR><TD>\n";
echo "<TABLE CELLSPACING=0 CELLPADDING=4>\n";
show_row(array(8, 0, 3, 9, 0, 2, 1, 4, 7,
"", "<FONT COLOR=$farbe_rotgelb>56</FONT>", "", "", "<FONT COLOR=$farbe_rotgelb>56</FONT>", "", "", "", ""));
show_row(array(0, 0, 9, 0, 4, 1, 8, 3, 0,
"567", "2[5]67", "", "56", "", "", "", "", "25"));
show_row(array(0, 0, 1, 7, 3, 8, 6, 9, 0,
"45", "24[5]", "", "", "", "", "", "", "25"));
echo "<TR><TD COLSPAN=11><HR></TD></TR>\n";
show_row(array(0, 0, 8, 0, 2, 9, 3, 0, 0,
"1457", "14[5]7", "", "56", "", "", "", "167", "146"));
show_row(array(3, 0, 6, 8, 0, 4, 2, 0, 9,
"", "<FONT COLOR=$farbe_rotgelb>157</FONT>", "", "", "<FONT COLOR=$farbe_rotgelb>157</FONT>", "", "", "17", ""));
show_row(array(2, "...", "...", "...", "...", "...", "...", 5, "..."));
echo "</TABLE>\n";
echo "</TD></TR>\n";
echo "</TABLE>\n";
echo "<LI>Goldene Kette:</LI>\n";
echo "<P>Eine Goldene Kette (Golden Chain, manchmal auch Remote Pairs genannt) ist eine Reihe von Paaren vom Typ ab, bc, cd, de, ef, ..., xy, yz, za, von denen jeweils zwei aufeinanderfolgende Paare in der gleichen Zeile, Spalte oder Box sind und die eine gemeinsame Zahl besitzen. Wenn die Zahl des ersten Paars, die nicht im zweiten Paar vorkommt (hier bei ab also a) mit der Zahl des letzten Paars, die nicht im vorletzten Paar vorkommt (bei za also auch a), übereinstimmt, dann kann man alle Zahlen a streichen, die sowohl von dem ersten als auch dem letzten Paar aus \"gesehen\" werden, also in der jeweils gleichen Zeile, Spalte oder Box liegen, weil die Zahl a auf jeden Fall entweder an der Stelle des ersten oder des letzten Paars vorkommt (wenn a im ersten Paar vorkommt, ist das offensichtlich; kommt aber b vor, so muss im zweiten Paar c sein, daher im dritten Paar d usw., bis zu z im vorletzten Paar, also a im letzten Paar).\n";
echo "<BR>Bewertung: Hierbei gibt es 3*N Punkte entsprechend der Länge N der gefundenen Kette (3 bis 14 = längste bisher gefundene Kette, aber längere sind durchaus vorhanden - Längen über 20 wurden schon beobachtet).\n";
echo "<P>Literatur:\n";
echo "<BR>Download des Artikels von Eduyng Castan: <A HREF=http://www.coverpop.com/sfiles/Sudoku-GoldenChains.pdf>http://www.coverpop.com/sfiles/Sudoku-GoldenChains.pdf</A>\n";
echo "<BR>Ähnlicher Artikel von Mihail Iusut: <A HREF=http://www.scanraid.com/sudoku/Remote_Pairs_and_XY_Chains.pdf>http://www.scanraid.com/sudoku/Remote_Pairs_and_XY_Chains.pdf</A>\n";
echo "<P>Beispiel einer Goldenen Kette (nach wenigen anderen Ausdünnschritten):\n";
echo "<P><TABLE BORDER=1 CELLSPACING=4 CELLPADDING=4>\n";
echo "<TR><TD>\n";
echo "<TABLE CELLSPACING=0 CELLPADDING=4>\n";
show_row(array(8, 0, 6, 4, 9, 5, 0, 0, 1,
"", "<FONT COLOR=$farbe_rotgelb>27</FONT><SUB>1</SUB>", "", "", "", "", "<FONT COLOR=$farbe_rotgelb>37</FONT><SUB>2</SUB>", "23", "",));
show_row(array(0, 3, 0, 8, 7, 6, 5, 9, 0,
"1[2]", "", "124", "", "", "", "", "", "24"));
show_row(array(5, 9, 0, 0, 0, 0, 8, 6, 0,
"", "", "47", "23", "123", "12", "", "", "47"));
echo "<TR><TD COLSPAN=11><HR></TD></TR>\n";
show_row(array(0, 6, 9, 0, 4, 0, 0, 5, 8,
"<FONT COLOR=$farbe_rotgelb>12</FONT><SUB>4</SUB>", "", "", "237", "", "27", "<FONT COLOR=$farbe_rotgelb>13</FONT><SUB>3</SUB>", "", "",));
show_row(array(7, 0, 8, 5, 0, 9, 4, 0, 6,
"", "1[2]", "", "", "23", "", "", "13", ""));
show_row(array("...", "...", "...", "...", "...", "...", "...", "...", "..."));
echo "</TABLE>\n";
echo "</TD></TR>\n";
echo "</TABLE>\n";
// Nur 1 Doppel davor: 030200004107439280040000030904086372308042000020300048400003820000804003683027410
echo "<BR>Die gefundene Goldene Kette ist: (1:2)<FONT COLOR=$farbe_rotgelb>27</FONT> - (1:7)<FONT COLOR=$farbe_rotgelb>73</FONT> - (4:7)<FONT COLOR=$farbe_rotgelb>31</FONT> - (4:1)<FONT COLOR=$farbe_rotgelb>12</FONT>.\n";
echo "Beachte, dass hier die Reihenfolge der Zahlen innerhalb eines Doppels dem Verkettungs-Prinzip angepasst ist: Also 73 statt der sonst aufsteigenden Reihenfolge 37 und 31 statt sonst 13. Das jeweilige Ende der Goldenen Kette ist also die Zahl 2, die daher im Feld (2:1), also Zeile 2 und Spalte 1, und im Feld (5:2), also Zeile 5 und Spalte 2, gestrichen werden kann.\n";
echo "<BR>Identisch mit der gefundenen Goldenen Kette ist auch die in umgekehrter Reihenfolge: (4:1)<FONT COLOR=$farbe_rotgelb>21</FONT> - (4:7)<FONT COLOR=$farbe_rotgelb>13</FONT> - (1:7)<FONT COLOR=$farbe_rotgelb>37</FONT> - (1:2)<FONT COLOR=$farbe_rotgelb>72</FONT>.\n";
echo "<P>Es wurden 16 Sudokus gefunden, die in den im Web zur Verfügung stehenden 30 Sekunden nicht gelöst werden konnten. Hier drei Beispiele einer Batch-Rechnung - auffallend die immer länger werdenden Ketten mit immer mehr Alternativen (bei allen bisher gelösten Sudokus waren nicht mehr als 2770 Ketten einer Länge aufgetreten):\n";
echo "<UL>\n";
echo "<LI><A HREF=\"$php_self?000030080300000409054006700060178000400000510003000027007001000800300900092780000_0\" target=\"_blank\">000030080300000409054006700060178000400000510003000027007001000800300900092780000</A></LI>";
echo "<BR>Nach 7 gefundenen Goldenen Ketten waren noch 25 Paare übrig. Daraus ergaben sich dann 210 Ketten der Länge 3 (aber keine Goldenen), 424 der Länge 4, ..., 18662 der Länge 13. Dann wurde aber abgebrochen, da der Programm-Hauptspeicher (hier 8 MB) überschritten wurde. Dieses Sudoku ist trotzdem eindeutig lösbar (bei 2 Einsetzversuchen gefunden), wenn auch bisher nicht mit diesem Programm...\n";
echo "<LI><A HREF=\"$php_self?042000590809000002000209000206040000050000614004076000000608009408000003061000750_0\" target=\"_blank\">042000590809000002000209000206040000050000614004076000000608009408000003061000750</A></LI>";
echo "<BR>Nach 8 gefundenen Goldenen Ketten waren noch 30 Paare übrig. Daraus ergaben sich dann 134 Ketten der Länge 3 (aber keine Goldenen), ..., 90886 der Länge 18, 86514 der Länge 19. Dann wurde aber - nach über 1 Stunde - mit \"Bus error\" abgebrochen. Auf einem anderen Rechner wurde weiter gerechnet bis 6436 Ketten der Länge 25, 1160 der Länge 25, dann aber keine Kette der Länge 27. Das führte zu Einsetzversuchen, bei der es nach 6 Versuchen in 3 Rekursionen zu 4 Lösungen führte => also ist dieses kein wirkliches Sudoku.\n";
echo "<LI><A HREF=\"$php_self?568002070003070090000500200000007100204089007005300000001005302080060900050900040_0\" target=\"_blank\">568002070003070090000500200000007100204089007005300000001005302080060900050900040</A></LI>";
echo "<BR>Nach 5 gefundenen Goldenen Ketten waren noch 27 Paare übrig. Daraus ergaben sich dann 296 Ketten der Länge 3 (aber keine Goldenen), 628 der Länge 4, ..., 268106 der Länge 15, 355184 (!) der Länge 16. Dann wurde aber - nach 72 Minuten - abgebrochen, da der Programm-Hauptspeicher von 128 MB überschritten wurde. Einsetzversuche ergaben nach 2 Versuchen 2 Lösungen => also ist dieses kein wirkliches Sudoku.\n";
/*
Alle bisher nicht loesbaren (weil abgebrochene) Sudokus:
000030080300000409054006700060178000400000510003000027007001000800300900092780000 <= Aber eindeutig loesbar!
030040906000001000000068470000000081004006703823000009002000000000009067687015090
042000590809000002000209000206040000050000614004076000000608009408000003061000750
042000590809000002000209000206040000050000614004076000000608009408000063061000750
042000590809000002000209000206040000050000614004076000000608009408000063061000758
042000590809000002000209000206040000050000614004076005000608009408000063061000758
042000590809000002000209000206040000057000614004076000000608009408000060061000750
042000590809000002000209000206040000057000614004076000000608009408000060061000758
042000590809000002000209000206040000057000614004076005000608009408000060061000758
042000590809000002000209000206040007050000614004076005000608009408000063061000758
042000590809000002000209000206040007050000614104076005000608009408000063061000758
042000590809000002000209000206040007057000614004076005000608009408000060061000758
042000590809000002000209000206040007057000614104076005000608009408000060061000758
530070000600195000098000060800040003400803001700020006060000040000419005000000079
568002070003070090000500200000007100204089007005300000001005302080060900050900040
568192473123070095040530210030057100214689537075300000091045302480063951350900740
*/
echo "</UL>\n";
echo "</OL>\n";
echo "<H4>Allgemeines</H4>\n";
echo "<P>Die Punktzahlen sind so einigermaßen den Schwierigkeitsgraden angepasst. Sie hängen aber auch von der Reihenfolge im Programm ab - so ergibt eine andere Reihenfolge im Suchen von Mustern in den Resten etwas andere Werte. Gerade die Bewertung beim Ausdünnen ist schwierig: es werden alle Ausdünnschritte mitgezählt, egal, ob sie am Ende etwas bringen oder nicht. Aber das weiß man ja auch beim Lösen mit Hand vorher nicht...\n";
echo "<P>Ab 50 Punkten wird es interessant, über 75 Punkte ist es schon schwerer, über 100 Punkte wirklich schwer, und über 125 Punkte ist schon eine Herausforderung. Der Mittelwert aller Sudokus liegt bei 106 Punkten (der Hauptwert liegt <A HREF=\"verteilung.ohne.ausduennung.pdf\">um 60 Punkte ohne Ausdünnung (siehe Kurve)</A>, und <A HREF=\"verteilung.mit.ausduennung.pdf\">um 144 Punkte mit Ausdünnung (siehe Kurve)</A>). Aktuelles Maximum mit schwer zu überbietenden 516 Punkten (sehr viel mehr Punkte sind wohl kaum erreichbar?!), also das bisher am schwersten (hier) gelöste Sudoku:\n";
echo "<UL>\n";
?>
<LI>Bisher: 454 Punkte aus 23 Zahlen (erste einfache Schritte: 11, Verhältnis 7.8): - A: 50, B: 0, C: 2, D: 5, E: 1, Ausduennschritte: 28, N-Tupel: 3 (bis Tripel), X-Wings: 0, Goldene Ketten: 16 (maximal 10 lang) - in 17 sec: <BR><A HREF="<? echo $php_self; ?>?000000070003805906050403080047000320000000000020000100000204050506100000080000000_0" target="_blank">000000070003805906050403080047000320000000000020000100000204050506100000080000000</A></LI>
<LI>Neu (Dank an Michael Jentsch): 516 Punkte aus 25 Zahlen (erste einfache Schritte: 6, Verhältnis 9.2): - A: 48, B: 0, C: 1, D: 4, E: 3, Ausduennschritte: 28, N-Tupel: 1 (bis Tripel), X-Wings: 0, Goldene Ketten: 17 (maximal 11 lang) - in 18 sec: <BR><A HREF="<? echo $php_self; ?>?507000040003100009000000800000503100002010950070004600006000000380000000009280306_0" target="_blank">507000040003100009000000800000503100002010950070004600006000000380000000009280306</A></LI>
<LI>PS: Ohne Goldene Ketten liegt das Maximum bei 217 Punkten aus 17 Zahlen (erste einfache Schritte: 2, Verhältnis 3.4): - A: 51, B: 2, C: 0, D: 8, E: 3, Ausduennschritte: 20, N-Tupel: 4 (bis Quadrupel), X-Wings: 0, Goldene Ketten: 0 - in 1.5 sec: <BR><A HREF="<? echo $php_self; ?>?008000000000002540031060000000000070000400200063000000000000001500007000000080003_0" target="_blank">008000000000002540031060000000000070000400200063000000000000001500007000000080003</A></LI>
<?
echo "</UL>\n";
echo "Das 454-Punkte-Sudoku wurde durch Reduzierung aller bis dahin gelösten etwa 9200 Sudokus in einem Aufwand von über 2100 Stunden Rechenzeit (insgesamt wurden fast 3 Millionen Sudokus durchgerechnet) gefunden... Reduzierung heißt hier: Lässt man aus einem Sudoku mit N Zahlen jeweils eine Zahl aus, so entstehen N Sudokus mit jeweils N-1 Zahlen, die alle berechnet werden. Gibt es dabei Lösungen, macht man die gleiche Prozedur mit dem berechneten Sudoku, das die höchste Punktzahl hat, usw., bis es keine Lösung mehr gibt.\n";
echo "<H4>Etwas Statistik:</H4>\n";
echo "Bei bisher nun insgesamt etwa 22100 gelösten Sudokus wurden etwa 1197000 mal die Methoden A bis E eingesetzt; davon 94.5% für Methode A, 2.8% (0.8% + 2.0%) Methode B+C, und 2.7% (1.9% + 0.8%) Methode D+E (also Ausdünnung). Die Ausdünn-Methoden werden zwar selten gebraucht, sind aber trotzdem zur Lösung von knapp der Hälfte aller Sudokus notwendig!\n";
echo "<P>Genauer gesehen waren etwa 26% der Sudokus allein mit Methode A lösbar, insgesamt 54% nur mit den Methoden A+B+C. Das sind die einfacheren Sudokus, obwohl dabei immerhin auch etwa 100 Punkte erreicht werden können - bisheriges Maximum: 96, also die (hier) schwierigsten Sudokus ohne Ausdünnung:\n";
echo "<UL>\n";
?>
<LI>96 Punkte aus 23 Zahlen (erste einfache Schritte: 58, Verhältnis 1.7): - A: 48, B: 0, C: 10, D: 0, E: 0, Ausduennschritte: 0, N-Tupel: 0, X-Wings: 0, Goldene Ketten: 0 - in 0.5 sec: <BR><A HREF="<? echo $php_self; ?>?371600500000000300025000700054000000000102090200008004100000000000029001000830000_0" target="_blank">371600500000000300025000700054000000000102090200008004100000000000029001000830000</A></LI>
<LI>96 Punkte aus 24 Zahlen (erste einfache Schritte: 57, Verhältnis 1.7): - A: 47, B: 0, C: 10, D: 0, E: 0, Ausduennschritte: 0, N-Tupel: 0, X-Wings: 0, Goldene Ketten: 0 - in 0.8 sec: <BR><A HREF="<? echo $php_self; ?>?000050007940000020000000040001200098086045000000100000600037010002060000038000400_0" target="_blank">000050007940000020000000040001200098086045000000100000600037010002060000038000400</A></LI>
<?
echo "</UL>\n";
echo "Obwohl in einem weiteren Aufwand von etwa 550 Stunden Rechenzeit (insgesamt fast 2 Millionen Sudokus wurden durchgerechnet) alle Sudokus ohne Ausdünnung nach einem analogen Verfahren wie oben beschrieben reduziert wurden, konnte kein Sudoku gefunden werden, das mehr als 100 Punkte hat. Es dürfte also schwierig sein, ein Sudoku ohne Ausdünnung mit höherer Punktzahl zu finden.\n";
echo "<P>Für die etwa 10200 Sudokus (46% der Fälle), bei denen die Kandidaten/Reste analysiert werden mussten, waren insgesamt etwa 81000 Ausdünnschritte notwendig (davon 48 % Box-Tests, 7 % Zeilen-/Spalten-Tests, 20.5 % N-Tupel, 2.5 % X-Wings, 22 % Goldene Ketten). In einem Fall waren es 23 Ausdünnschritte hintereinander, bis eine Zahl gefunden werden konnte, und in einem anderen Fall insgesamt 33 Schritte!\n";
echo "<P>Dabei konnten etwa 1350 alleine durch die einfachen Box-Test- und Zeilen-/Spalten-Test-Methoden gelöst werden. Etwa 2950 Sudokus wurden durch die N-Tupel-Methode (darunter ein 7-Tupel!), nur 260 Sudokus durch die X-Wing-Methode (erstaunlich wenig!, aber immerhin wurden insgesamt etwa 1900 X-Wings gefunden), jedoch 5650 durch die Goldene Kette gelöst (bei insgesamt gut 17700 gefundenen Goldenen Ketten, und in einzelnen Sudokus bis zu 20 Goldenen Ketten bzw. maximal mit der Länge 14) - insofern verwundert es, dass dieses Verfahren so wenig bekannt ist!\n";
echo "<H4>Literatur:</H4>\n";
echo "Allgemeine Lösungsstrategien bei: <A HREF=http://www.sadmansoftware.com/sudoku/solvingtechniques.htm>http://www.sadmansoftware.com/sudoku/solvingtechniques.htm</A>\n";
echo "<BR>oder bei: <A HREF=http://hodoku.sourceforge.net/de/techniques.php</A>http://hodoku.sourceforge.net/de/techniques.php\n";
}
function microtime_float() {
list($usec, $sec) = explode(" ", microtime());
$time = (float)$usec + (float)$sec;
return $time;
}
function durchgestrichen($z, $string) {
// ereg_replace is deprecated in PHP 5.3.0, removed in PHP 6.0.0
return preg_replace("/($z)/", "[\$1]", $string);
}
function addiere_reste($r1, $r2) {
$r12 = $r1 . $r2;
$r = "";
for ($k = 1; $k <= 9; $k++) {
if (strpos($r12, "$k") !== FALSE) $r = $r . "$k";
}
return $r;
}
function sichtbar($index1, $index2) {
$row1 = row_number($index1);
$row2 = row_number($index2);
$col1 = col_number($index1);
$col2 = col_number($index2);
$box1r = box_number_r($index1);
$box2r = box_number_r($index2);
$box1c = box_number_c($index1);
$box2c = box_number_c($index2);
if ($row1 == $row2 || $col1 == $col2 || ($box1r == $box2r && $box1c == $box2c)) return 1;
else return 0;
}
function check_common($index1, $index2) {
// Alle Felder zu erstem Index
$row1 = row($index1);
$col1 = col($index1);
$box1 = box($index1);
// Alle Felder zu zweitem Index
$row2 = row($index2);
$col2 = col($index2);
$box2 = box($index2);
// Alle gemeinsamen Felder
/*
$both = array();
foreach($row2 as $value) {
if (in_array($value, $row1) || in_array($value, $col1) || in_array($value, $box1)) {
if (!in_array($value, $both)) $both[] = $value;
}
}
foreach($col2 as $value) {
if (in_array($value, $row1) || in_array($value, $col1) || in_array($value, $box1)) {
if (!in_array($value, $both)) $both[] = $value;
}
}
foreach($box2 as $value) {
if (in_array($value, $row1) || in_array($value, $col1) || in_array($value, $box1)) {
if (!in_array($value, $both)) $both[] = $value;
}
}
sort ($both);
*/
// Mit Prozeduren
$all1 = array_merge($row1, $col1, $box1);
$all1 = array_unique(array_values($all1));
$all2 = array_merge($row2, $col2, $box2);
$all2 = array_unique(array_values($all2));
// Alle gemeinsamen Felder
$both = array_intersect($all1, $all2);
$both = array_values($both);
sort($both);
return $both;
}
// Definition der Markierungswerte:
// d.h. "Spezielle" Zahlen nur aus optischen Gruenden, damit schneller erkennbar
// 32767: Nicht mehr besetzbar durch die aktuelle Zahl (da schon in gleicher Zeile, Spalte oder Box)
// 9999: Zwei oder drei Alternativen fuer die aktuelle Zahl in einer Zeile oder Spalte einer Box
// 20000: Wegen 9999 in der gleichen Zeile oder Spalte (andere Box) nicht besetzbar durch die aktuelle Zahl
function markiere_32767($sudoku_array, $zahl) {
// Markiere alle mit der laufenden Zahl erreichbaren Felder (mit 32767)
$sudoku_array_copy = $sudoku_array;
for ($index = 0; $index < 81; $index++) {
$field_value = $sudoku_array[$index];
if ($field_value == $zahl) {
foreach (row($index) as $value) {
if ($sudoku_array[$value] == 0) $sudoku_array_copy[$value] = 32767;
}
foreach (col($index) as $value) {
if ($sudoku_array[$value] == 0) $sudoku_array_copy[$value] = 32767;
}
foreach (box($index) as $value) {
if ($sudoku_array[$value] == 0) $sudoku_array_copy[$value] = 32767;
}
}
}
return $sudoku_array_copy;
}
function markiere_alle($sudoku_array, $zahl, &$info_text) {
// $info_text wird hier veraendert!
// Drei Schritte:
// 1. Markiere (mit 32767) nicht mehr besetzbare Felder
// 2. Zaehle in allen Boxen echte freie Felder (mit 0)
// 3. Setze Markierung (9999 und 20000) an bestimmte Stellen
// 1. Markiere alle mit der laufenden Zahl erreichbaren Felder (mit 32767)
$sudoku_array_copy = markiere_32767($sudoku_array, $zahl);
// Loop ueber Schritte 2 und 3
$nochmal = 1; // Erzwinge Loop
while ($nochmal == 1) {
$nochmal = 0;
// 2. Bestimme zuerst alle echten freien Felder (mit 0) in Boxen
$null_array = array();
for ($a = 0; $a < 3; $a++) {
for ($b = 0; $b < 3; $b++) {
$index_box = 27*$a + 3*$b;
// Speichere alle Positionen der 0-Werte in Array von Arrays
$null = array();
foreach (box($index_box) as $value) {
// Echte Null, also auch ungleich 32767 bzw. 20000
if ($sudoku_array_copy[$value] == 0) $null[] = $value;
}
$null_array[] = $null;
}
}
// 3. Setze 9999 fuer moegliche Stellen der Zahl innerhalb einer Box (in genau einer Zeile/Spalte)
$box = 0;
for ($a = 0; $a < 3; $a++) { // Stufe 1
for ($b = 0; $b < 3; $b++) { // Stufe 2
$index_box = 27*$a + 3*$b;
$a_1 = $a + 1;
$b_1 = $b + 1;
$null = $null_array[$box];
if (count($null) == 2 || count($null) == 3) {
// Zwei oder drei Alternativen in einer Zeile
$row = row_number($null[0]);
if ((count($null) == 2 && $row == row_number($null[1])) ||
(count($null) == 3 && $row == row_number($null[1]) && $row == row_number($null[2]))) {
// Markiere mit 9999 eine moegliche Stelle fuer Zahl (nur in Trefferbox), sonst 20000
$box_c = box_number_c($null[0]);
foreach (row($null[0]) as $value) {
if ($sudoku_array[$value] == 0 && $sudoku_array_copy[$value] != 32767) {
if (box_number_c($value) == $box_c) $sudoku_array_copy[$value] = 9999;
else {
$sudoku_array_copy[$value] = 20000;
$row_1 = $row + 1;
$text = "In Box $a_1#$b_1 ist Zahl $zahl nur in Zeile $row_1 dieser Box möglich";
if (!in_array($text, $info_text)) $info_text[] = $text;
}
}
}
$nochmal = 1;
}
// Zwei oder drei Alternativen in einer Spalte
$col = col_number($null[0]);
if ((count($null) == 2 && $col == col_number($null[1])) ||
(count($null) == 3 && $col == col_number($null[1]) && $col == col_number($null[2]))) {
// Markiere mit 9999 eine moegliche Stelle fuer Zahl (nur in Trefferbox), sonst 20000
$box_r = box_number_r($null[0]);
foreach (col($null[0]) as $value) {
if ($sudoku_array[$value] == 0 && $sudoku_array_copy[$value] != 32767) {
if (box_number_r($value) == $box_r) $sudoku_array_copy[$value] = 9999;
else {
$sudoku_array_copy[$value] = 20000;
$col_1 = $col + 1;
$text = "In Box $a_1#$b_1 ist Zahl $zahl nur in Spalte $col_1 dieser Box möglich";
if (!in_array($text, $info_text)) $info_text[] = $text;
}
}
}
$nochmal = 1;
}
}
$box++;
} // Ende Stufe 2
} // Ende Stufe 1
} // Loop
return $sudoku_array_copy;
}
function teste_reste(&$sudoku_array, &$sudoku_array_color, $sudoku_array_rest, &$last_index) {
global $neuereste, $anzahl, $d_anzahl, $e_anzahl, $punkte, $punkte_art, $farbe_gruen, $farbe_rot, $farbe_blau, $farbe_braun, $farbe_lila, $farbe_rotgelb;
$test = 0;
$while = 0;
// Suche einstellige, damit eindeutige Loesungen
// Beispiel: Rest "5" => Eindeutiger Wert
while ($while == 0) { // Stufe 1
$while = 1; // Nur einmal durchlaufen um mit break zu einem return zu kommen
for ($index = 0; $index < 81; $index++) { // Stufe 2
$rest = $sudoku_array_rest[$index];
if (strlen($rest) == 1) {
$sudoku_array[$index] = $rest;
$r_1 = row_number($index) + 1;
$c_1 = col_number($index) + 1;
$last_index = $index;
$sudoku_array_color[$index] = "><FONT COLOR=$farbe_braun>$rest</FONT><";
echo "<BR>D1 - Einzige Möglichkeit in Zeile $r_1 und Spalte $c_1: Zahl $rest\n";
$neuereste = 1;
$punkte = $punkte + $punkte_art[4];
$d_anzahl++;
$anzahl++;
$test = 1;
break 2;
}
} // Stufe 2
// Suche eindeutige Moeglichkeiten (nur 1 Alternative):
// Zaehle in jeder Zeile, Spalte, Box, ob von allen Alternativen in dieser Zeile, Spalte, Box
// eine Zahl genau ein Mal vorkommt
// (z.B.: Reste "169","48","16","58","149" => "5" kommt nur ein Mal vor)
// Einzig aufgetretene Alternativen in Zeilen
for ($r = 0; $r < 9; $r++) { // Stufe 2
$index = 9 * $r;
$r_1 = $r + 1;
// Jede Zahl
for ($z = 1; $z <= 9; $z++) { // Stufe 3
$last = 0;
$anz = 0;
foreach (row($index) as $value) {
if (strlen($sudoku_array_rest[$value]) >= 1) {
if (strpos($sudoku_array_rest[$value], "$z") !== FALSE) {
$last = $value;
$anz++;
}
}
}
if ($anz == 1) {
$sudoku_array[$last] = $z;
$c_1 = col_number($last) + 1;
$last_index = $last;
$sudoku_array_color[$last] = "><FONT COLOR=$farbe_lila>$z</FONT><";
echo "<BR>E1 - Einzige Möglichkeit für Zahl $z in Zeile $r_1: Spalte $c_1\n";
$neuereste = 1;
$punkte = $punkte + $punkte_art[5];
$e_anzahl++;
$anzahl++;
$test = 1;
break 3;
}
} // Stufe 3
} // Stufe 2
// Einzig aufgetretene Alternativen in Spalten
for ($c = 0; $c < 9; $c++) { // Stufe 2
$index = $c;
$c_1 = $c + 1;
// Jede Zahl
for ($z = 1; $z <= 9; $z++) { // Stufe 3
$last = 0;
$anz = 0;
foreach (col($index) as $value) {
if (strlen($sudoku_array_rest[$value]) >= 1) {
if (strpos($sudoku_array_rest[$value], "$z") !== FALSE) {
$last = $value;
$anz++;
}
}
}
if ($anz == 1) {
$sudoku_array[$last] = $z;
$r_1 = row_number($last) + 1;
$last_index = $last;
$sudoku_array_color[$last] = "><FONT COLOR=$farbe_lila>$z</FONT><";
echo "<BR>E2 - Einzige Möglichkeit für Zahl $z in Spalte $c_1: Zeile $r_1\n";
$neuereste = 1;
$punkte = $punkte + $punkte_art[5];
$e_anzahl++;
$anzahl++;
$test = 1;
break 3;
}
} // Stufe 3
} // Stufe 2
// Einzig aufgetretene Alternativen in Boxen
// Alle Boxen starten bei der ersten Farbe: Einfacher formulierbar mit: foreach (frb(0) as $index) {
for ($a = 0; $a < 3; $a++) { // Stufe 2
for ($b = 0; $b < 3; $b++) { // Stufe 3
$index = 27*$a + 3*$b;
$a_1 = $a + 1;
$b_1 = $b + 1;
// Jede Zahl
for ($z = 1; $z <= 9; $z++) { // Stufe 4
$last = 0;
$anz = 0;
foreach (box($index) as $value) {
if (strlen($sudoku_array_rest[$value]) >= 1) {
if (strpos($sudoku_array_rest[$value], "$z") !== FALSE) {
$last = $value;
$anz++;
}
}
}
if ($anz == 1) {
$sudoku_array[$last] = $z;
$r_1 = row_number($last) + 1;
$c_1 = col_number($last) + 1;
$last_index = $last;
$sudoku_array_color[$last] = "><FONT COLOR=$farbe_lila>$z</FONT><";
echo "<BR>E3 - Einzige Möglichkeit für Zahl $z in Box $a_1#$b_1: Zeile $r_1 und Spalte $c_1\n";
$neuereste = 1;
$punkte = $punkte + $punkte_art[5];
$e_anzahl++;
$anzahl++;
$test = 1;
break 4;
}
} // Stufe 4
} // Stufe 3
} // Stufe 2
} // Stufe 1
return $test;
}
function check_correctness($sudoku_array) {
global $box_row, $box_col;
// Test in Zeilen
$error = 0;
// In Zeilen
for ($r = 0; $r < 9; $r++) { // Stufe 1
$r_1 = $r + 1;
$index = 9 * $r;
$gefunden = array();
foreach (row($index) as $value) { // Stufe 2
$z = $sudoku_array[$value];
if ($z != 0) {
if (!in_array($z, $gefunden)) $gefunden[] = $z;
else {
echo "<H2>Keine Lösung! Zahl $z mehr als einmal in Zeile $r_1!</H2>\n";
$error = 1;
break 2;
}
}
} // Stufe 2
} // Stufe 1
// Test in Spalten
for ($c = 0; $c < 9; $c++) { // Stufe 1
$c_1 = $c + 1;
$index = $c;
$gefunden = array();
foreach (col($index) as $value) { // Stufe 2
$z = $sudoku_array[$value];
if ($z != 0) {
if (!in_array($z, $gefunden)) $gefunden[] = $z;
else {
echo "<H2>Keine Lösung! Zahl $z mehr als einmal in Spalte $c_1!</H2>\n";
$error = 1;
break 2;
}
}
} // Stufe 2
} // Stufe 1
// Test in Boxen
// Alle Boxen starten bei der ersten Farbe: Einfacher formulierbar mit: foreach (frb(0) as $index) {
for ($a = 0; $a < 3; $a++) { // Stufe 1
for ($b = 0; $b < 3; $b++) { // Stufe 2
$a_1 = $a + 1;
$b_1 = $b + 1;
$index = 27*$a + 3*$b;
$gefunden = array();
foreach (box($index) as $value) { // Stufe 3
$z = $sudoku_array[$value];
if ($z != 0) {
if (!in_array($z, $gefunden)) $gefunden[] = $z;
else {
$box_name = "$box_row[$a]$box_col[$b]";
echo "<H2>Keine Lösung! Zahl $z mehr als einmal in Box $a_1#$b_1 ($box_name)!</H2>\n";
$error = 1;
break 3;
}
}
} // Stufe 3
} // Stufe 2
} // Stufe 1
if ($error == 1) {
zwischen_ausgabe($sudoku_array, array());
}
return $error;
}
// Zwischen-Ausgabe
function zwischen_ausgabe($sudoku_array_xxxx, $sudoku_array_rest) {
global $anzahl, $punkte;
// Eventuell keine Reste anzeigen
if ($sudoku_array_rest == array()) $rest_leer = 1;
else $rest_leer = 0;
echo "<P>";
echo "<TABLE BORDER=1 CELLSPACING=4 CELLPADDING=4>\n";
echo "<TR><TD>\n";
echo "<TABLE CELLSPACING=0 CELLPADDING=4>\n";
$index = 0;
for ($r = 0; $r < 9; $r++) {
echo "<TR>\n";
for ($c = 0; $c < 9; $c++) {
$field_name = "a$index";
$field_value = $sudoku_array_xxxx[$index];
if ($field_value === 0) {
$rest = $sudoku_array_rest[$index];
}
else {
$rest = " ";
}
// Wichtig: === wegen Strings im Feld
if ($field_value === 0) {
if ($rest == "") $rest = " ";
if ($rest == "123456789") $rest = ""; // statt: $rest = "1..9"
if ($rest_leer == 1) echo "<TD><INPUT TYPE=TEXT NAME=$field_name VALUE=\"\" SIZE=1 MAXLENGTH=1></TD>\n";
else echo "<TD><INPUT TYPE=TEXT NAME=$field_name VALUE=\"\" SIZE=1 MAXLENGTH=1><BR>$rest</TD>\n";
}
else {
if ($rest_leer == 1) {
if (substr($field_value, 0, 4) == ">") {
// Markierung nicht Bold
$innen = substr($field_value, 4, -4);
echo "<TD>><B>$innen</B><</TD>\n";
}
else {
echo "<TD><B>$field_value</B></TD>\n";
}
}
else {
echo "<TD><B>$field_value</B><BR>$rest</TD>\n";
}
}
if ($c == 2 || $c == 5) echo "<TD>|<BR>|</TD>\n";
$index++;
}
echo "</TR>\n";
if ($r == 2 || $r == 5) echo "<TR><TD COLSPAN=11><HR></TD></TR>\n";
}
echo "</TABLE>\n";
echo "</TD></TR>\n";
echo "</TABLE>\n";
if ($anzahl != "") echo "<P>Anzahl Zahlen: $anzahl, Punkte: $punkte\n";
echo "<BR>\n";
}
$php_self = $_SERVER['PHP_SELF'];
// Initialisierungen
// Timezone (notwendig seit Version 5.1)
// date_default_timezone_set('Europe/Berlin');
// Maximale Goldene Ketten-Anzahl (Bisherige Maxima aller 21000 geloesten Sudokus: 1824=>2266=>2770, 1458=>2470=>4130)
$max_kette = 10000;
// X-Wing ausschaltbar (bei xwing = 0)
$xwing = 1;
// Fuer Loop ueber alle 9 Zahlen
$zahlen = array(1, 2, 3, 4, 5, 6, 7, 8, 9);
// Werte-Punkte - spaeter vom User setzbar
// Feld 0: Schwarz: Vorhandene Ausgangszahlen
// Feld 1: Gruen: Einzige Position in Box und Zeile/Spalte (neu: Zeile/Spalte doppelt so viel wert)
// Feld 2: Rot: Einzige Position in Zeile/Spalte/Box wegen nicht moeglichen anderen Positionen
// Feld 3: Blau: Einstellige, damit eindeutige Loesungen
// Feld 4: Braun: Loesung durch weitergehendes Ausduennen mit einstelligem Rest
// Feld 5: Lila: Loesung durch weitergehendes Ausduennen mit einzig auftretendem Rest
// $punkte_art = array(0, 1, 6, 8, 2, 4);
$punkte_art = array(0, 1, 4, 6, 1, 4);
// Extra-Punkte - spaeter vom User setzbar
// Bemerkung: Die Reihenfolge im Array entspricht nicht der Reihenfolge im Programm (Umstellung)
// Feld 0: Dummy
// Feld 1: Box-Test der Reste in einer Zeile oder Spalte
// Feld 2: Zeilen-/Spalten-Test der Reste innerhalb einer Box
// Feld 3: Faktor * N (von N-Tupel)
// Feld 4: X-Wing
// Feld 5: Faktor * Laenge der Kette
$ausduenn_punkte = array(0, 4, 6, 2, 10, 3);
// Box-Bezeichnung
$box_row = array("O", "M", "U");
$box_col = array("L", "M", "R");
// Fuer N-Tupel-Texte
$tupel = array("0", "0", "2-Tupel (Doppel)", "3-Tupel (Tripel)", "4-Tupel (Quadrupel)", "5-Tupel (Pentupel)", "6-Tupel", "7-Tupel");
// Farben fuer Methoden 1 - 5
$farbe_gruen = "\"#00CC00\"";
$farbe_rot = "\"#FF0000\"";
$farbe_blau = "\"#0000FF\"";
$farbe_braun = "\"#FFAA00\"";
$farbe_lila = "\"#CC00FF\"";
// Bei Ausduenneng: Reste-Markierung
$farbe_rotgelb = "\"#FF2200\"";
// (HIDDEN-)Parameter lesen
if (array_key_exists('sudoku', $_POST)) $sudoku = $_POST['sudoku']; else $sudoku = "";
if (array_key_exists('status', $_POST)) $status = $_POST['status']; else $status = "";
if (array_key_exists('punkte', $_POST)) $punkte = $_POST['punkte']; else $punkte = 0;
// if (array_key_exists('STANDARD', $_POST)) $STANDARD = $_POST['STANDARD']; else $STANDARD = "";
// Query-String lesen
$query = $_SERVER['QUERY_STRING'];
// Drei Anfangsfaelle: Leeres Sudoku mit Eintragungen; Vorgegebenes Sudoku (Query-String); Verzweigung
// Normalfall: Leeres Sudoku mit Eintragungen: nach Werten fragen
if (($status === "" && $query === "") || $query == "000000000000000000000000000000000000000000000000000000000000000000000000000000000_0") {
$status = 0;
echo "<H3>Geben Sie die Ausgangszahlen ein (1..9)</H3>\n";
// Eingabe
echo "<FORM METHOD=POST NAME=sudoku ACTION=\"$php_self\">\n";
echo "<INPUT TYPE=HIDDEN NAME=status VALUE=$status>\n";
// Fuer TAB-Text
echo "<TABLE BORDER=0>\n";
echo "<TR><TD>\n";
echo "<TABLE BORDER=1 CELLSPACING=4 CELLPADDING=4>\n";
echo "<TR><TD>\n";
echo "<TABLE CELLSPACING=0 CELLPADDING=4>\n";
$index = 0;
for ($r = 0; $r < 9; $r++) {
echo "<TR>\n";
for ($c = 0; $c < 9; $c++) {
$field_name = "a$index";
echo "<TD><INPUT TYPE=TEXT NAME=$field_name VALUE=\"\" SIZE=1 MAXLENGTH=1></TD>\n";
if ($c == 2 || $c == 5) echo "<TD>|<BR>|</TD>\n";
$index++;
}
echo "</TR>\n";
if ($r == 2 || $r == 5) echo "<TR><TD COLSPAN=11><HR></TD></TR>\n";
}
echo "</TABLE>\n";
echo "</TD></TR>\n";
echo "</TABLE>\n";
echo "</TD><TD VALIGN=\"TOP\"> PS: Sie können mit der TAB-Taste von Feld zu Feld springen<BR> ohne die Maus zu benutzen :-)\n";
echo "</TD></TR>\n";
echo "</TABLE>\n";
echo "<SCRIPT TYPE=\"text/javascript\">\n";
echo "document.sudoku.a0.focus();\n";
echo "</SCRIPT>\n";
echo "<P>";
// echo "<INPUT TYPE=SUBMIT NAME=SUBMIT VALUE=\"Go!\">\n";
// Wenn man im Safari zweimal die Enter/Return-Taste drueckt, wird das Formular abgeschickt
// Bei Firefox und Internet Explorer reicht einmal ...
echo "<INPUT TYPE=SUBMIT VALUE=\"Go!\">\n";
echo "</FORM>\n";
echo "<P><HR><P>";
erklaerung();
}
// Vorgegebenes Sudoku - mit Frage nach Test-Typ
elseif (substr($query, 82) === "0") {
// (int) wichtig wegen spaeterem ===
for ($k = 0; $k < 81; $k++) $sudoku_array[$k] = (int) substr($query, $k, 1);
$status = 0;
echo "<H3>Vorgegebenes Beispiel</H3>";
echo "<FORM METHOD=POST ACTION=\"$php_self\">\n";
echo "<INPUT TYPE=HIDDEN NAME=status VALUE=$status>\n";
// zwischen_ausgabe($sudoku_array, array());
echo "<TABLE BORDER=1 CELLSPACING=4 CELLPADDING=4>\n";
echo "<TR><TD>\n";
echo "<TABLE CELLSPACING=0 CELLPADDING=4>\n";
$index = 0;
for ($r = 0; $r < 9; $r++) {
echo "<TR>\n";
for ($c = 0; $c < 9; $c++) {
$field_name = "a$index";
$field_value = $sudoku_array[$index];
// Wichtig: === wegen Strings im Feld
if ($field_value === 0) {
echo "<TD><INPUT TYPE=TEXT NAME=$field_name VALUE=\"\" SIZE=1 MAXLENGTH=1></TD>\n";
}
else {
echo "<TD><B><INPUT TYPE=TEXT NAME=$field_name VALUE=\"$field_value\" SIZE=1 MAXLENGTH=1></B></TD>\n";
}
if ($c == 2 || $c == 5) echo "<TD>|<BR>|</TD>\n";
$index++;
}
echo "</TR>\n";
if ($r == 2 || $r == 5) echo "<TR><TD COLSPAN=11><HR></TD></TR>\n";
}
echo "</TABLE>\n";
echo "</TD></TR>\n";
echo "</TABLE>\n";
echo "<P>";
echo "<INPUT TYPE=SUBMIT VALUE=\"Go!\">\n";
echo "</FORM>\n";
echo "<P><HR><P>";
// erklaerung();
}
else {
// Hauptteil (eigentliche Abarbeitung)
// Statt: $sudoku_array = array(0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0, ... 0,0,0,0,0,0,0,0,0);
$sudoku_array = array_fill(0, 81, 0);
// Beginn Uebertragung und Berechnungen
// Vorgegebenes Sudoku (Query-String)
if ($query != "") {
if (substr($query, 82) == "X") {
$xwing = 0;
$status = 0;
}
else {
$xwing = 1;
$status = (int) substr($query, 82);
}
// (int) wichtig wegen spaeterem ===
for ($k = 0; $k < 81; $k++) $sudoku_array[$k] = (int) substr($query, $k, 1);
}
// Leeres Sudoku mit Eintragungen; bzw. Verzweigung
else {
// Werte aus Hidden-Parameter (bei Verzweigung)
if ($sudoku != "") {
// (int) wichtig wegen spaeterem ===
for ($k = 0; $k < 81; $k++) $sudoku_array[$k] = (int) substr($sudoku, $k, 1);
}
else {
$status = 0;
}
// Aus Formblatt Parameter uebertragen (in beiden Faellen)
for ($index = 0; $index < 81; $index++) {
$string_name = "a$index";
if (array_key_exists("$string_name", $_POST)) {
$orig = $_POST["$string_name"];
// Abfangen von Eingabefehlern
if ($orig != "") {
$name = (int) $orig;
if ($name < 1 || $name > 9) {
$index_1 = $index + 1;
$r_1 = row_number($index) + 1;
$c_1 = col_number($index) + 1;
echo "<H3><FONT COLOR=$farbe_rot>Fehler in Zeile $r_1 und Spalte $c_1: Keine Zahl zwischen 1 und 9 ($orig)</FONT></H3>\n";
$sudoku_array[$index] = 0;
}
else {
$sudoku_array[$index] = $name;
}
}
}
} // for
}
// TEST
/*
$sudoku_array = array(0,1,2,7,6,0,8,5,3, 7,0,0,0,2,5,1,9,6, 0,6,5,3,0,0,2,7,4,
0,2,7,1,0,6,9,8,5, 6,5,9,0,7,0,0,2,1, 1,0,8,9,5,2,0,6,7,
5,9,0,2,0,7,6,4,8, 0,0,6,5,0,0,7,1,2, 2,7,0,6,8,0,5,3,9);
*/
$time_anf = microtime_float();
// Ausgangszahlen zaehlen
$anzahl = 0;
for ($index = 0; $index < 81; $index++) {
if ($sudoku_array[$index] != 0) $anzahl++;
}
$anzahl_anfangs = $anzahl;
// Statt: $sudoku_array_rest = array("123456789","123456789", ... "123456789","123456789");
$sudoku_array_rest = array_fill(0, 81, "123456789");
$ausduennen = false;
// Wegen farbiger Ausgabe
$sudoku_array_color = $sudoku_array;
if ($status == 0) $punkte = 0; // sonst Uebernahme vom vorherigen Aufruf
$simple = 0;
$a_anzahl = 0;
$b_anzahl = 0;
$c_anzahl = 0;
$d_anzahl = 0;
$e_anzahl = 0;
$ausduenn_schritte = 0;
$ausduenn_maximum = 0;
$ausduenn_felder = 0;
$ntupel_anzahl = 0;
$ntupel_max = 0;
$xwing_anzahl = 0;
$golden_anzahl = 0;
$golden_maxlen = 0;
// Darstellung ohne Reste
echo "<H1><FONT COLOR=$farbe_rot>Gewähltes Beispiel</FONT></H1>\n";
zwischen_ausgabe($sudoku_array, array());
$error = check_correctness($sudoku_array);
// Gesamtloop
while ($anzahl < 81 && $error == 0) { // Stufe 1
// zwischen_ausgabe($sudoku_array_color, array());
$anzahl_vorher_grosse_loop = $anzahl - 1; // Erzwinge Loop
while ($anzahl_vorher_grosse_loop < $anzahl) { // Stufe 2
$anzahl_vorher_grosse_loop = $anzahl;
// Fuer nur einmalige Ausgabe der Info-Texte
$info_text = array();
// Einfach und ohne Punkte: Suche letzte noch fehlende Zahl in Zeile
for ($r = 0; $r < 9; $r++) { // Stufe 3
$index_row = 9 * $r;
$r_1 = $r + 1;
// Speichere alle Positionen der 0-Werte in Array
$not_pos = array();
$val = array();
foreach (row($index_row) as $value) {
if ($sudoku_array[$value] == 0) $not_pos[] = $value;
else $val[] = $sudoku_array[$value];
}
// Nur eine fehlende Zahl
if (count($not_pos) == 1) {
$zahl = 0;
foreach ($zahlen as $wert) {
if (!in_array($wert, $val)) $zahl = $wert;
}
$current = $not_pos[0];
$c_1 = col_number($current) + 1;
$last_index = $current;
$sudoku_array[$current] = $zahl;
$sudoku_array_copy[$current] = $zahl;
$sudoku_array_color[$current] = "><FONT COLOR=$farbe_gruen>$zahl</FONT><";
echo "<BR>A1 - Letzte Position für Zahl $zahl in Zeile $r_1: Spalte $c_1\n";
// Wegen zwangsweiser Setzung einer Zahl kann ein Widerspruch entstanden sein
$error = check_correctness($sudoku_array);
if ($error == 1) break 3;
// 0 Punkte, da letzte Zahl
$punkte = $punkte + 0;
$a_anzahl++;
$anzahl++;
if ($anzahl == 81) break 3;
$sudoku_array_copy = markiere_32767($sudoku_array, $zahl);
zwischen_ausgabe($sudoku_array_color, array());
// Markierung weg werfen
$sudoku_array_color[$last_index] = substr($sudoku_array_color[$last_index], 4, -4);
continue 3;
}
} // Stufe 3
// Einfach und ohne Punkte: Suche letzte noch fehlende Zahl in Spalte
for ($c = 0; $c < 9; $c++) { // Stufe 3
$index_col = $c;
$c_1 = $c + 1;
// Speichere alle Positionen der 0-Werte in Array
$not_pos = array();
$val = array();
foreach (col($index_col) as $value) {
if ($sudoku_array[$value] == 0) $not_pos[] = $value;
else $val[] = $sudoku_array[$value];
}
// Nur eine fehlende Zahl
if (count($not_pos) == 1) {
$zahl = 0;
foreach ($zahlen as $wert) {
if (!in_array($wert, $val)) $zahl = $wert;
}
$current = $not_pos[0];
$r_1 = row_number($current) + 1;
$last_index = $current;
$sudoku_array[$current] = $zahl;
$sudoku_array_copy[$current] = $zahl;
$sudoku_array_color[$current] = "><FONT COLOR=$farbe_gruen>$zahl</FONT><";
echo "<BR>A2 - Letzte Position für Zahl $zahl in Spalte $c_1: Zeile $r_1\n";
// Wegen zwangsweiser Setzung einer Zahl kann ein Widerspruch entstanden sein
$error = check_correctness($sudoku_array);
if ($error == 1) break 3;
// 0 Punkte, da letzte Zahl
$punkte = $punkte + 0;
$a_anzahl++;
$anzahl++;
if ($anzahl == 81) break 3;
$sudoku_array_copy = markiere_32767($sudoku_array, $zahl);
zwischen_ausgabe($sudoku_array_color, array());
// Markierung weg werfen
$sudoku_array_color[$last_index] = substr($sudoku_array_color[$last_index], 4, -4);
continue 3;
}
} // Stufe 3
// Einfach und ohne Punkte: Suche letzte noch fehlende Zahl in Box
for ($a = 0; $a < 3; $a++) { // Stufe 3
for ($b = 0; $b < 3; $b++) { // Stufe 4
$index_box = 27*$a + 3*$b;
$a_1 = $a + 1;
$b_1 = $b + 1;
// Speichere alle Positionen der 0-Werte in Array
$not_pos = array();
$val = array();
foreach (box($index_box) as $value) {
if ($sudoku_array[$value] == 0) $not_pos[] = $value;
else $val[] = $sudoku_array[$value];
}
// Nur eine fehlende Zahl
if (count($not_pos) == 1) {
$zahl = 0;
foreach ($zahlen as $wert) {
if (!in_array($wert, $val)) $zahl = $wert;
}
$current = $not_pos[0];
$r_1 = row_number($current) + 1;
$c_1 = col_number($current) + 1;
$box_name = "$box_row[$a]$box_col[$b]";
$last_index = $current;
$sudoku_array[$current] = $zahl;
$sudoku_array_copy[$current] = $zahl;
$sudoku_array_color[$current] = "><FONT COLOR=$farbe_gruen>$zahl</FONT><";
echo "<BR>A3 - Letzte Position für Zahl $zahl in Box $a_1#$b_1 ($box_name): Zeile $r_1 und Spalte $c_1\n";
// Wegen zwangsweiser Setzung einer Zahl kann ein Widerspruch entstanden sein
$error = check_correctness($sudoku_array);
if ($error == 1) break 4;
// 0 Punkte, da letzte Zahl
$punkte = $punkte + 0;
$a_anzahl++;
$anzahl++;
if ($anzahl == 81) break 4;
$sudoku_array_copy = markiere_32767($sudoku_array, $zahl);
zwischen_ausgabe($sudoku_array_color, array());
// Markierung weg werfen
$sudoku_array_color[$last_index] = substr($sudoku_array_color[$last_index], 4, -4);
continue 4;
}
} // Stufe 4
} // Stufe 3
// Grosse Loop ueber alle Zahlen
foreach ($zahlen as $zahl) { // Stufe 3
$eventuell_ausgabe = 0;
// Markiere mit 32767
$sudoku_array_copy = markiere_32767($sudoku_array, $zahl);
// Einfache Abfrage, getrennt fuer Zeilen, Spalten, Boxen => Jetzt nur Boxen
$anzahl_vorher = $anzahl - 1; // Erzwinge Loop
while ($anzahl_vorher < $anzahl) { // Stufe 4
$anzahl_vorher = $anzahl;
// Suche einzelnes freies Feld in Boxen (echte 0)
for ($a = 0; $a < 3; $a++) { // Stufe 5
for ($b = 0; $b < 3; $b++) { // Stufe 6
$index_box = 27*$a + 3*$b;
$a_1 = $a + 1;
$b_1 = $b + 1;
// Speichere alle Positionen der 0-Werte in Array
$null = array();
foreach (box($index_box) as $value) {
if ($sudoku_array_copy[$value] == 0) $null[] = $value;
}
if (count($null) == 1) {
$current = $null[0];
$r_1 = row_number($current) + 1;
$c_1 = col_number($current) + 1;
$box_name = "$box_row[$a]$box_col[$b]";
$last_index = $current;
$sudoku_array[$current] = $zahl;
$sudoku_array_copy[$current] = $zahl;
$sudoku_array_color[$current] = "><FONT COLOR=$farbe_gruen>$zahl</FONT><";
// Ist nie letzte Zahl
echo "<BR>A3 - Einzige Position für Zahl $zahl in Box $a_1#$b_1 ($box_name): Zeile $r_1 und Spalte $c_1\n";
$punkte = $punkte + $punkte_art[1];
$a_anzahl++;
$anzahl++;
if ($anzahl == 81) break 6;
// Suche mehrere auf einmal
$eventuell_ausgabe++;
$sudoku_array_copy = markiere_32767($sudoku_array, $zahl);
}
} // Stufe 6
} // Stufe 5
} // Stufe 4
// Ende einfache Abfrage
if ($eventuell_ausgabe != 0) {
zwischen_ausgabe($sudoku_array_color, array());
// Markierungen weg werfen
for ($m = 0; $m < 81; $m++) {
if (strpos($sudoku_array_color[$m], "<") > 0) $sudoku_array_color[$m] = substr($sudoku_array_color[$m], 4, -4);
}
continue 3;
}
} // Stufe 3
// Grosse Loop ueber alle Zahlen
foreach ($zahlen as $zahl) { // Stufe 3
// Markiere mit 32767
$sudoku_array_copy = markiere_32767($sudoku_array, $zahl);
// Einfache Abfrage, getrennt fuer Zeilen, Spalten, Boxen => Jetzt nur Zeilen und Spalten
$anzahl_vorher = $anzahl - 1; // Erzwinge Loop
while ($anzahl_vorher < $anzahl) { // Stufe 4
$anzahl_vorher = $anzahl;
// Suche einzelnes freies Feld in Zeilen (echte 0)
for ($r = 0; $r < 9; $r++) { // Stufe 5
$index_row = 9 * $r;
$r_1 = $r + 1;
// Speichere alle Positionen der 0-Werte in Array
$null = array();
foreach (row($index_row) as $value) {
if ($sudoku_array_copy[$value] == 0) $null[] = $value;
}
if (count($null) == 1) {
$current = $null[0];
$c_1 = col_number($current) + 1;
$last_index = $current;
$sudoku_array[$current] = $zahl;
$sudoku_array_copy[$current] = $zahl;
$sudoku_array_color[$current] = "><FONT COLOR=$farbe_gruen>$zahl</FONT><";
// Ist nie letzte Zahl
echo "<BR>A1 - Einzige Position für Zahl $zahl in Zeile $r_1: Spalte $c_1\n";
$punkte = $punkte + 2*$punkte_art[1];
$a_anzahl++;
$anzahl++;
if ($anzahl == 81) break 5;
$sudoku_array_copy = markiere_32767($sudoku_array, $zahl);
zwischen_ausgabe($sudoku_array_color, array());
// Markierung weg werfen
$sudoku_array_color[$last_index] = substr($sudoku_array_color[$last_index], 4, -4);
continue 5;
}
} // Stufe 5
} // Stufe 4
$anzahl_vorher = $anzahl - 1; // Erzwinge Loop
while ($anzahl_vorher < $anzahl) { // Stufe 4
$anzahl_vorher = $anzahl;
// Suche einzelnes freies Feld in Spalten (echte 0)
for ($c = 0; $c < 9; $c++) { // Stufe 5
$index_col = $c;
$c_1 = $c + 1;
// Speichere alle Positionen der 0-Werte in Array
$null = array();
foreach (col($index_col) as $value) {
if ($sudoku_array_copy[$value] == 0) $null[] = $value;
}
if (count($null) == 1) {
$current = $null[0];
$r_1 = row_number($current) + 1;
$last_index = $current;
$sudoku_array[$current] = $zahl;
$sudoku_array_copy[$current] = $zahl;
$sudoku_array_color[$current] = "><FONT COLOR=$farbe_gruen>$zahl</FONT><";
// Ist nie letzte Zahl
echo "<BR>A2 - Einzige Position für Zahl $zahl in Spalte $c_1: Zeile $r_1\n";
$punkte = $punkte + 2*$punkte_art[1];
$a_anzahl++;
$anzahl++;
if ($anzahl == 81) break 5;
$sudoku_array_copy = markiere_32767($sudoku_array, $zahl);
zwischen_ausgabe($sudoku_array_color, array());
// Markierung weg werfen
$sudoku_array_color[$last_index] = substr($sudoku_array_color[$last_index], 4, -4);
continue 5;
}
} // Stufe 5
} // Stufe 4
// Ende einfache Abfrage
} // Stufe 3
// Ende Grosse Loop ueber alle Zahlen
// Grosse Loop ueber alle Zahlen
foreach ($zahlen as $zahl) { // Stufe 3
// Markiere mit 32767, 9999 und 20000 wegen Paaren und Tripeln in einer Zeile/Spalte einer Box
$sudoku_array_copy = markiere_alle($sudoku_array, $zahl, $info_text);
// Analyse der Markierungen fuer Zeilen
$anzahl_vorher = $anzahl - 1; // Erzwinge Loop
while ($anzahl_vorher < $anzahl) { // Stufe 4
$anzahl_vorher = $anzahl;
// Suche einzelnes freies Feld in Zeilen
for ($r = 0; $r < 9; $r++) { // Stufe 5
$index_row = 9 * $r;
$r_1 = $r + 1;
// Speichere alle Positionen der 0-Werte (0 oder 9999) und 20000-Werte in Array
$null = array();
$anz_20000 = array();
foreach (row($index_row) as $value) {
if ($sudoku_array_copy[$value] == 0 || $sudoku_array_copy[$value] == 9999) $null[] = $value;
if ($sudoku_array_copy[$value] == 20000) $anz_20000[] = $value;
}
if (count($null) == 1 && count($anz_20000) > 0) {
$current = $null[0];
// Suche Info-Text
$text = "";
foreach ($info_text as $value) {
if (strpos($value, "Zahl $zahl") > 0) $text .= ", und: " . $value;
}
$teil_text = substr($text, 7);
$c_1 = col_number($current) + 1;
$sudoku_array[$current] = $zahl;
$sudoku_array_copy[$current] = $zahl;
$last_index = $current;
$sudoku_array_color[$current] = "><FONT COLOR=$farbe_rot>$zahl</FONT><";
echo "<BR>B1 - Wegen: $teil_text: Einzige Position für Zahl $zahl der Zeile $r_1 in Spalte $c_1 gefunden\n";
$punkte = $punkte + $punkte_art[2];
$b_anzahl++;
$anzahl++;
if ($anzahl == 81) break 5;
$sudoku_array_copy = markiere_alle($sudoku_array, $zahl, $info_text);
zwischen_ausgabe($sudoku_array_color, array());
// Markierung weg werfen
$sudoku_array_color[$last_index] = substr($sudoku_array_color[$last_index], 4, -4);
continue 5;
}
} // Stufe 5
} // Stufe 4
// Analyse fuer Spalten
$anzahl_vorher = $anzahl - 1; // Erzwinge Loop
while ($anzahl_vorher < $anzahl) { // Stufe 4
$anzahl_vorher = $anzahl;
// Suche einzelnes freies Feld in Spalten
for ($c = 0; $c < 9; $c++) { // Stufe 5
$index_col = $c;
$c_1 = $c + 1;
// Speichere alle Positionen der 0-Werte (0 oder 9999) und 20000-Werte in Array
$null = array();
$anz_20000 = array();
foreach (col($index_col) as $value) {
if ($sudoku_array_copy[$value] == 0 || $sudoku_array_copy[$value] == 9999) $null[] = $value;
if ($sudoku_array_copy[$value] == 20000) $anz_20000[] = $value;
}
if (count($null) == 1 && count($anz_20000) > 0) {
$current = $null[0];
// Suche Info-Text
$text = "";
foreach ($info_text as $value) {
if (strpos($value, "Zahl $zahl") > 0) $text .= ", und: " . $value;
}
$teil_text = substr($text, 7);
$r_1 = row_number($current) + 1;
$sudoku_array[$current] = $zahl;
$sudoku_array_copy[$current] = $zahl;
$last_index = $current;
$sudoku_array_color[$current] = "><FONT COLOR=$farbe_rot>$zahl</FONT><";
echo "<BR>B2 - Wegen: $teil_text: Einzige Position für Zahl $zahl der Spalte $c_1 in Zeile $r_1 gefunden\n";
$punkte = $punkte + $punkte_art[2];
$b_anzahl++;
$anzahl++;
if ($anzahl == 81) break 5;
$sudoku_array_copy = markiere_alle($sudoku_array, $zahl, $info_text);
zwischen_ausgabe($sudoku_array_color, array());
// Markierung weg werfen
$sudoku_array_color[$last_index] = substr($sudoku_array_color[$last_index], 4, -4);
continue 5;
}
} // Stufe 5
} // Stufe 4
// Analyse fuer Boxen
$anzahl_vorher = $anzahl - 1; // Erzwinge Loop
while ($anzahl_vorher < $anzahl) { // Stufe 4
$anzahl_vorher = $anzahl;
// Suche einzelnes freies Feld in Boxen
for ($a = 0; $a < 3; $a++) { // Stufe 5
for ($b = 0; $b < 3; $b++) { // Stufe 6
$a_1 = $a + 1;
$b_1 = $b + 1;
$index_box = 27*$a + 3*$b;
// Speichere alle Positionen der 0-Werte (0 oder 9999) und 20000-Werte in Array
$null = array();
$anz_20000 = array();
foreach (box($index_box) as $value) {
if ($sudoku_array_copy[$value] == 0 || $sudoku_array_copy[$value] == 9999) $null[] = $value;
if ($sudoku_array_copy[$value] == 20000) $anz_20000[] = $value;
}
if (count($null) == 1 && count($anz_20000) > 0) {
$current = $null[0];
// Suche Info-Text
$text = "";
foreach ($info_text as $value) {
if (strpos($value, "Zahl $zahl") > 0) $text .= ", und: " . $value;
}
$teil_text = substr($text, 7);
$r_1 = row_number($current) + 1;
$c_1 = col_number($current) + 1;
$box_name = "$box_row[$a]$box_col[$b]";
$sudoku_array[$current] = $zahl;
$sudoku_array_copy[$current] = $zahl;
$last_index = $current;
$sudoku_array_color[$current] = "><FONT COLOR=$farbe_rot>$zahl</FONT><";
echo "<BR>B3 - Wegen: $teil_text: Einzige Position für Zahl $zahl der Box $a_1#$b_1 ($box_name) in Zeile $r_1 und Spalte $c_1 gefunden\n";
$punkte = $punkte + $punkte_art[2];
$b_anzahl++;
$anzahl++;
if ($anzahl == 81) break 6;
$sudoku_array_copy = markiere_alle($sudoku_array, $zahl, $info_text);
zwischen_ausgabe($sudoku_array_color, array());
// Markierung weg werfen
$sudoku_array_color[$last_index] = substr($sudoku_array_color[$last_index], 4, -4);
continue 6;
}
} // Stufe 6
} // Stufe 5
} // Stufe 4
// Ende mit Markierungen und moeglichen Feldern
} // Stufe 3
// Ende Grosse Loop ueber alle Zahlen
// Berechne die Reste: Gehe anfangs von 123456789 aus, danach von den aktuellen Resten
// Streiche alle Zahlen aus, die in der gleichen Zeile, Spalte oder Box vorkommen
for ($index = 0; $index < 81; $index++) { // Stufe 3
$field_value = $sudoku_array[$index];
if ($field_value == 0) {
// Streichen
$rest = $sudoku_array_rest[$index];
foreach (row($index) as $value) {
$pos = $sudoku_array[$value];
$rest = str_replace($pos, "", $rest);
}
foreach (col($index) as $value) {
$pos = $sudoku_array[$value];
$rest = str_replace($pos, "", $rest);
}
foreach (box($index) as $value) {
$pos = $sudoku_array[$value];
$rest = str_replace($pos, "", $rest);
}
}
else {
$rest = "";
}
$sudoku_array_rest[$index] = $rest;
} // Stufe 3
// Fuer naechste Ausgabe
$sudoku_array_rest_markiert = $sudoku_array_rest;
// Einstellige, damit eindeutige Loesungen: Beispiel: Rest "5" => Eindeutiger Wert 5
for ($index = 0; $index < 81; $index++) { // Stufe 3
$zahl = $sudoku_array_rest[$index];
if (strlen($zahl) == 1) {
$r_1 = row_number($index) + 1;
$c_1 = col_number($index) + 1;
$sudoku_array[$index] = $zahl;
$sudoku_array_rest[$index] = "";
$last_index = $index;
if ($ausduennen == false) {
$sudoku_array_color[$index] = "><FONT COLOR=$farbe_blau>$zahl</FONT><";
echo "<BR>C1 - Einzige Möglichkeit in Zeile $r_1 und Spalte $c_1: Zahl $zahl\n";
$punkte = $punkte + $punkte_art[3];
$c_anzahl++;
}
else {
// Hier wird von den durch Ausduennen verkleinerten Resten ausgegangen, daher Methode D statt C
// Bemerkung: Ist manchmal auch direkt als C-Methode erkennbar
// Der Aufwand lohnt aber nicht, und es waeren unnoetig viele Punkte mehr (6 statt 1)!
// Markiere durchgestrichene Zahl (nur an der Trefferstelle)
$rest_zahl = str_replace($zahl, "", $sudoku_array_rest_markiert[$index]);
if ($rest_zahl != "") {
$sudoku_array_rest_markiert[$index] = durchgestrichen("$rest_zahl", $sudoku_array_rest_markiert[$index]);
}
echo "<H4>Neue Reste ($neuereste)</H4>\n";
zwischen_ausgabe($sudoku_array_color, $sudoku_array_rest_markiert);
// if ($neuereste > $ausduenn_maximum) $ausduenn_maximum = $neuereste;
// $neuereste++;
// $ausduenn_schritte++;
$sudoku_array_color[$index] = "><FONT COLOR=$farbe_braun>$zahl</FONT><";
echo "<BR>D2 - Einzige Möglichkeit in Zeile $r_1 und Spalte $c_1: Zahl $zahl\n";
$neuereste = 1;
$punkte = $punkte + $punkte_art[4];
$d_anzahl++;
}
$anzahl++;
if ($anzahl == 81) break 3;
zwischen_ausgabe($sudoku_array_color, array());
// Markierung weg werfen
$sudoku_array_color[$last_index] = substr($sudoku_array_color[$last_index], 4, -4);
continue 3; // Nur ein Mal
}
} // Stufe 3
// Falls schon mal ausgeduennt wurde, sofort nach weiteren Moeglichkeiten schauen
if ($ausduennen == true) {
$test = teste_reste($sudoku_array, $sudoku_array_color, $sudoku_array_rest, $last_index);
if ($test == 1) {
zwischen_ausgabe($sudoku_array_color, array());
// Markierung weg werfen
$sudoku_array_color[$last_index] = substr($sudoku_array_color[$last_index], 4, -4);
if ($anzahl == 81) break 2;
continue 2;
}
else continue 1;
}
// Einstellige, damit eindeutige Loesungen, auch mit indirekten Positionen wie Typ B
// Waere Loesung C2 - Aufwand lohnt aber nicht
} // Stufe 2
//################################################################################
echo "<P>Keine (weiteren) Standard-Regeln (A, B, C) anwendbar\n";
// Erstes mal Ausduennen
if ($ausduennen == false) {
$ausduennen = true;
$simple = $a_anzahl + $b_anzahl + $c_anzahl;
// Berechnung der Ausduenn-Felder ueber bisher gefundene Felder
$ausduenn_felder = 81 - $anzahl;
echo "<BR>Anzahl Ausdünnfelder: $ausduenn_felder\n";
$punkte = $punkte + $ausduenn_felder;
}
echo "<H4>Reste vor dem Ausdünnen</H4>\n";
zwischen_ausgabe($sudoku_array_color, $sudoku_array_rest);
// Test, ob evtl. Reste leer sind, d.h. keine Zahlen moeglich sind
for ($index = 0; $index < 81; $index++) { // Stufe 2
if ($sudoku_array_rest[$index] == "" && $sudoku_array[$index] == 0) {
$r_1 = row_number($index) + 1;
$c_1 = col_number($index) + 1;
echo "<H2>Keine Lösung! Keine Zahl möglich in Zeile $r_1/Spalte $c_1!</H2>\n";
$error = 1;
break 2;
}
} // Stufe 2
// Ausduennen nach den 5 Methoden: Box-Test, Zeilen-/Spalten-Test, N-Tupel, X-Wing, Goldene Kette