<HTML>
<HEAD>
<TITLE>Sudoku Solver (Loop)</TITLE>
</HEAD>
<BODY TEXT="#000000" BGCOLOR="#F8F8FC">
<H1>Sudoku Solver (Loop)</H1>
<H3>Auflistung aller Schritte - damit als Hilfe/Unterstützung beim Lösen mit Hand benutzbar</H3>
<H3>Die Anzahl der notwendigen Schritte kann als Maß für die Schwierigkeit benutzt werden</H3>
<?
// Einfachste Loesung mit einem einzeiligen (alle Zeilen nebeneinander) Feld (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 Feld zurueckgegeben werden.
// Haupttrick: Berechne aus dem Index (0 - 80) die Index-Felder der zugehoerigen Zeile, Spalte, Box
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
$s = fmod($index,9);
for ($i = 0; $i < 9; $i++) $l[$i] = $s + $i*9;
return $l;
}
function col_number($index) {
$s = fmod($index,9);
return $s;
}
function box($index) {
// Pattern: (u*3 + t*27) + (i*9 + j)
$r = floor($index/9);
$s = fmod($index, 9); // $index - $r*9;
$t = floor($r/3);
$u = floor($s/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_s($index) {
$s = fmod($index, 9);
$u = floor($s/3);
return $u;
}
// 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;
}
$php_self = $_SERVER['PHP_SELF'];
// (HIDDEN-)Parameter lesen
if (array_key_exists('status', $_POST)) $status = $_POST['status']; else $status = "";
if (array_key_exists('sudoku', $_POST)) $sudoku = $_POST['sudoku']; else $sudoku = "";
if (array_key_exists('sdrest', $_POST)) $sdrest = $_POST['sdrest']; else $sdrest = "";
if (array_key_exists('STANDARD', $_POST)) $STANDARD = $_POST['STANDARD']; else $STANDARD = "";
if (array_key_exists('AUSDUENNEN', $_POST)) $AUSDUENNEN = $_POST['AUSDUENNEN']; else $AUSDUENNEN = "";
// 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") {
echo "<H3>Geben Sie die Ausgangszahlen ein (1..9)</H3>\n";
$status = 0;
// Eingabe
echo "<FORM METHOD=POST NAME=sudoku ACTION=\"$php_self\">\n";
echo "<INPUT TYPE=HIDDEN NAME=status VALUE=$status>\n";
echo "<TABLE BORDER=1 CELLSPACING=5 CELLPADDING=5>\n";
echo "<TR><TD>\n";
echo "<TABLE CELLSPACING=0 CELLPADDING=5>\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 "<SCRIPT TYPE=\"text/javascript\">\n";
echo "document.sudoku.a0.focus();\n";
echo "</SCRIPT>\n";
echo "<P>";
echo "<INPUT TYPE=SUBMIT NAME=AUSDUENNEN VALUE=\"Mit Ausdünnen\">\n";
echo " <INPUT TYPE=SUBMIT NAME=STANDARD VALUE=\"Nur Standard-Tests\">\n";
echo "</FORM>\n";
}
// Vorgegebenes Sudoku - mit Frage nach Test-Typ
elseif (substr($query, 82) === "0") {
// (int) wichtig wegen späterem ===
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";
echo "<TABLE BORDER=1 CELLSPACING=5 CELLPADDING=5>\n";
echo "<TR><TD>\n";
echo "<TABLE CELLSPACING=0 CELLPADDING=5>\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) {
$rest = "...";
echo "<TD><INPUT TYPE=TEXT NAME=$field_name VALUE=\"\" SIZE=1 MAXLENGTH=1><BR>$rest</TD>\n";
}
else {
$rest = " ";
echo "<TD><B><INPUT TYPE=TEXT NAME=$field_name VALUE=\"$field_value\" SIZE=1 MAXLENGTH=1></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";
echo "<P>";
echo "<INPUT TYPE=SUBMIT NAME=AUSDUENNEN VALUE=\"Mit Ausdünnen\">\n";
echo " <INPUT TYPE=SUBMIT NAME=STANDARD VALUE=\"Nur Standard-Tests\">\n";
echo "</FORM>\n";
}
else {
// Hauptteil
// Default-Werte
$anf_status = 0;
$end_status = 40;
// 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 != "") {
$status = (int) substr($query, 82);
$anf_status = $status;
// (int) wichtig wegen späterem ===
for ($k = 0; $k < 81; $k++) $sudoku_array[$k] = (int) substr($query, $k, 1);
}
// Leeres Sudoku mit Eintragungen; bzw. Verzweigung
else {
$anf_status = 0;
// Reste uebernehmen
if ($sdrest != "") $sudoku_rest = explode(",", $sdrest);
// Werte aus Hidden-Parameter (bei Verzweigung)
if ($sudoku != "") {
// (int) wichtig wegen späterem ===
for ($k = 0; $k < 81; $k++) $sudoku_array[$k] = (int) substr($sudoku, $k, 1);
$anf_status = $status + 1;
}
// Aus Formblatt Parameter übertragen
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;
echo "<H3><FONT COLOR=\"FF0000\">Fehler im Feld $index_1: Keine Zahl zwischen 1 und 9 ($orig)</FONT></H3>";
$sudoku_array[$index] = 0;
}
else {
$sudoku_array[$index] = $name;
}
}
}
}
}
// Loop bis Loesung gefunden oder Ende wegen Alternativen
for ($status = $anf_status; $status <= $end_status; $status++) {
$sudoku_array_color = $sudoku_array;
// Statt: if ($status == 0) $sudoku_rest = array("123456789","123456789","123456789", ... "123456789","123456789");
if ($status == 0) $sudoku_rest = array_fill(0, 81, "123456789");
// Darstellung
if ($status == $anf_status) {
echo "<H1><FONT COLOR=\"FF0000\">Gewähltes Beispiel</FONT></H1>\n";
echo "<TABLE BORDER=1 CELLSPACING=5 CELLPADDING=5>\n";
echo "<TR><TD>\n";
echo "<TABLE CELLSPACING=0 CELLPADDING=5>\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];
if ($field_value === 0) {
$rest = $sudoku_rest[$index];
}
else {
$rest = " ";
}
// Wichtig: === wegen Strings im Feld
if ($field_value === 0) {
if ($rest == "") $rest = " ";
if ($rest == "123456789") $rest = "...";
echo "<TD><INPUT TYPE=TEXT NAME=$field_name VALUE=\"\" SIZE=1 MAXLENGTH=1><BR>$rest</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";
$schritt = $status;
echo "<H3>Schritt $schritt</H3>";
}
// Berechnungen
// Wegen farbiger Ausgabe
$sudoku_array_color = $sudoku_array;
$color_num = 0;
// Erster Schritt:
// Ermittle moegliche Werte durch Austreichen:
// Streiche alle Zahlen aus, die in der gleichen Zeile, Spalte oder Box vorkommen
// (z.B.: "123456789" => "169", da z.B. "2","3","4","5","7","8" anderswo vorkommen)
for ($index = 0; $index < 81; $index++) {
$field_name = "a$index";
$field_value = $sudoku_array[$index];
if ($field_value == 0) {
// Streichen
$rest = $sudoku_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);
}
// Streichen in Farbbereichen
// foreach (frb($index) as $value) {
// $pos = $sudoku_array[$value];
// $rest = str_replace($pos, "", $rest);
// }
}
else {
$rest = "";
}
$sudoku_rest[$index] = $rest;
}
if ($status == $anf_status) {
echo "<P><HR><P>";
echo "<H3>Vorher</H3>";
echo "<TABLE BORDER=1 CELLSPACING=5 CELLPADDING=5>\n";
echo "<TR><TD>\n";
echo "<TABLE CELLSPACING=0 CELLPADDING=5>\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_color[$index];
if ($field_value === 0) {
$rest = $sudoku_rest[$index];
}
else {
$rest = " ";
}
// Wichtig: === wegen Strings im Feld
if ($field_value === 0) {
if ($rest == "") $rest = " ";
if ($rest == "123456789") $rest = ""; /* $rest = "1..9"; */
echo "<TD><INPUT TYPE=TEXT NAME=$field_name VALUE=\"\" SIZE=1 MAXLENGTH=1><BR>$rest</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 ($AUSDUENNEN != "") {
// Ausduennen mit Paaren (ab, ab)
// Beispiel: Reste einer Zeile "349", "148", "24", "12", "24" => 2 und 4 muessen an den beiden Stellen "24", "24" sein
// Also kann man in den anderen Resten diese Zahlen streichen => "39", "18", "24", "1", "24" => Sogar einen eindeutigen Rest ("1") gefunden
// Ausduennen mit Tripeln (abc, ab, ac, bc als Teile des Tripels)
// Beispiel: Reste einer Zeile "459", "348", "249", "29", "1349", "24" => 2 und 4 und 9 muessen an den drei Stellen "249", "29", "24" sein
// Also kann man in den anderen Resten diese Zahlen streichen => "5", "38", "249", "29", "13", "24" => Sogar einen eindeutigen Rest ("5") gefunden
// Ausduennen mit Quadrupeln (abcd, abc, abd, acd, bcd, ab, ac, ad, bc, bd, cd als Teile des Quadrupels)
// Beispiel: Reste einer Zeile "2489", "248", "29", "1389", "14", "28", "1349" => 2 und 4 und 8 und 9 muessen an den vier Stellen "2489", "248", "29", "28" sein
// Also kann man in den anderen Resten diese Zahlen streichen => "13", "1", "13" => Sogar einen eindeutigen Rest ("1") gefunden
// Ausduennen mit n-Tupeln (2- bis 8-Tupel)
$tupel = array("", "", "Paar", "Tripel", "Quadrupel", "5-Tupel", "6-Tupel", "7-Tupel", "8-Tupel");
for ($n = 2; $n < 9; $n++) {
// In Zeilen
for ($r = 0; $r < 9; $r++) {
$index = 9 * $r;
$r_1 = $r + 1;
$row_array = row($index);
foreach (row($index) as $value) {
if (strlen($sudoku_rest[$value]) == $n) {
$found = array();
$ntuple_rest = $sudoku_rest[$value];
$ntuple = array();
for ($j = 0; $j < $n; $j++) {
$ntuple[$j] = substr($ntuple_rest, $j, 1);
}
// Suche alle n-Tupel bzw. dessen Teile in dieser Zeile
for ($k = 0; $k < 9; $k++) {
$teilstring = $sudoku_rest[$row_array[$k]];
// Mindestens zweistellige Reste
if (strlen($teilstring) < 2) continue;
// Streiche alle Teile des n-Tupels aus => Wenn Leerstring uebrig bleibt, war es ein Treffer
for ($j = 0; $j < $n; $j++) {
$teilstring = str_replace($ntuple[$j], "", $teilstring);
}
// Keine anderen Zahlen vorhanden
if ($teilstring == "") $found[] = $row_array[$k];
}
if (count($found) == $n) {
$old_rest = $sudoku_rest;
foreach ($row_array as $rowvalue) {
if ($sudoku_rest[$rowvalue] == "") continue;
for ($j = 0; $j < $n; $j++) {
if ($rowvalue == $found[$j]) continue 2; // Achtung: 2 = 2 for-Schleifen-Ebenen
}
// Streiche eventuell vorhandene Zahlen in den anderen Resten
for ($j = 0; $j < $n; $j++) {
$sudoku_rest[$rowvalue] = str_replace($ntuple[$j], "", $sudoku_rest[$rowvalue]);
}
}
$found_text = "";
for ($j = 0; $j < $n; $j++) {
$m = $found[$j];
$found_text .= ",$sudoku_rest[$m]";
}
$found_text = substr($found_text, 1);
if ($old_rest != $sudoku_rest) echo "<BR>$tupel[$n] \"$ntuple_rest\" ($found_text) gefunden in Zeile $r_1\n";
}
}
}
}
// In Spalten
for ($s = 0; $s < 9; $s++) {
$index = $s;
$s_1 = $s + 1;
$col_array = col($index);
foreach (col($index) as $value) {
if (strlen($sudoku_rest[$value]) == $n) {
$found = array();
$ntuple_rest = $sudoku_rest[$value];
$ntuple = array();
for ($j = 0; $j < $n; $j++) {
$ntuple[$j] = substr($ntuple_rest, $j, 1);
}
// Suche alle n-Tupel bzw. dessen Teile in dieser Spalte
for ($k = 0; $k < 9; $k++) {
$teilstring = $sudoku_rest[$col_array[$k]];
// Mindestens zweistellige Reste
if (strlen($teilstring) < 2) continue;
for ($j = 0; $j < $n; $j++) {
$teilstring = str_replace($ntuple[$j], "", $teilstring);
}
// Keine anderen Zahlen vorhanden
if ($teilstring == "") $found[] = $col_array[$k];
}
if (count($found) == $n) {
$old_rest = $sudoku_rest;
foreach ($col_array as $colvalue) {
if ($sudoku_rest[$colvalue] == "") continue;
for ($j = 0; $j < $n; $j++) {
if ($colvalue == $found[$j]) continue 2; // Achtung: 2 = 2 for-Schleifen-Ebenen
}
// Streiche eventuell vorhandene Zahlen in den anderen Resten
for ($j = 0; $j < $n; $j++) {
$sudoku_rest[$colvalue] = str_replace($ntuple[$j], "", $sudoku_rest[$colvalue]);
}
}
$found_text = "";
for ($j = 0; $j < $n; $j++) {
$m = $found[$j];
$found_text .= ",$sudoku_rest[$m]";
}
$found_text = substr($found_text, 1);
if ($old_rest != $sudoku_rest) echo "<BR>$tupel[$n] \"$ntuple_rest\" ($found_text) gefunden in Spalte $s_1\n";
}
}
}
}
// In Boxen
for ($a = 0; $a < 3; $a++) {
for ($b = 0; $b < 3; $b++) {
$index = 27*$a + 3*$b;
$a_1 = $a + 1;
$b_1 = $b + 1;
$box_array = box($index);
foreach (box($index) as $value) {
if (strlen($sudoku_rest[$value]) == $n) {
$found = array();
$ntuple_rest = $sudoku_rest[$value];
$ntuple = array();
for ($j = 0; $j < $n; $j++) {
$ntuple[$j] = substr($ntuple_rest, $j, 1);
}
// Suche alle n-Tupel bzw. dessen Teile in dieser Box
for ($k = 0; $k < 9; $k++) {
$teilstring = $sudoku_rest[$box_array[$k]];
// Mindestens zweistellige Reste
if (strlen($teilstring) < 2) continue;
for ($j = 0; $j < $n; $j++) {
$teilstring = str_replace($ntuple[$j], "", $teilstring);
}
// Keine anderen Zahlen vorhanden
if ($teilstring == "") $found[] = $box_array[$k];
}
if (count($found) == $n) {
$old_rest = $sudoku_rest;
foreach ($box_array as $boxvalue) {
if ($sudoku_rest[$boxvalue] == "") continue;
for ($j = 0; $j < $n; $j++) {
if ($boxvalue == $found[$j]) continue 2; // Achtung: 2 = 2 for-Schleifen-Ebenen
}
// Streiche eventuell vorhandene Zahlen in den anderen Resten
for ($j = 0; $j < $n; $j++) {
$sudoku_rest[$boxvalue] = str_replace($ntuple[$j], "", $sudoku_rest[$boxvalue]);
}
}
$found_text = "";
for ($j = 0; $j < $n; $j++) {
$m = $found[$j];
$found_text .= ",$sudoku_rest[$m]";
}
$found_text = substr($found_text, 1);
if ($old_rest != $sudoku_rest) echo "<BR>$tupel[$n] \"$ntuple_rest\" ($found_text) gefunden in Box $a_1/$b_1\n";
}
}
}
}
}
}
// Box-Test der Reste in einer Zeile
// Beispiel: Reste in einer Zeile
// "48", "678", "38", "5", "47", "67", "9", "46", "146"
// Die "8" kommt in dieser Zeile nur in der ersten Box vor => Also kann man in den anderen Resten dieser Box diese Zahl streichen
for ($r = 0; $r < 9; $r++) {
$index = 9 * $r;
$r_1 = $r + 1;
for ($z = 1; $z <= 9; $z++) {
$box_array = array();
foreach (row($index) as $value) {
if (strpos($sudoku_rest[$value], "$z") !== false) {
// Dadurch in gleicher Box
$box_pos = floor($value/3);
if (!in_array($box_pos, $box_array)) $box_array[] = $box_pos;
}
}
// Falls Treffer: teste auf alle in gleicher Box
$treffer = count($box_array);
// Treffer 1 heisst: nur in einer Box
if ($treffer == 1) {
$old_rest = $sudoku_rest;
// Zahl in der gleichen Box aus den anderen Resten entfernen
foreach (box(3*$box_array[0]) as $value) {
// Nicht aber in der untersuchten Zeile
if (row_number($value) == $r) continue;
if (strpos($sudoku_rest[$value], "$z") !== false) {
$a_1 = box_number_r($value) + 1;
$b_1 = box_number_s($value) + 1;
$sudoku_rest[$value] = str_replace($z, "", $sudoku_rest[$value]);
}
}
if ($old_rest != $sudoku_rest) echo "<BR>Zahl \"$z\" kommt in Zeile $r_1 nur in der Box $a_1/$b_1 vor\n";
}
}
}
// Box-Test der Reste in einer Spalte
// Beispiel: Reste in einer Spalte
// "48", "678", "38", "5", "47", "67", "9", "46", "146"
// Die "8" kommt in dieser Spalte nur in der ersten Box vor => Also kann man in den anderen Resten dieser Box diese Zahl streichen
for ($s = 0; $s < 9; $s++) {
$index = $s;
$s_1 = $s + 1;
for ($z = 1; $z <= 9; $z++) {
$box_array = array();
foreach (col($index) as $value) {
if (strpos($sudoku_rest[$value], "$z") !== false) {
// Dadurch in gleicher Box
$box_pos = floor($value/27);
if (!in_array($box_pos, $box_array)) $box_array[] = $box_pos;
}
}
// Falls Treffer: teste auf alle in gleicher Box
$treffer = count($box_array);
// Treffer 1 heisst: nur in einer Box
if ($treffer == 1) {
$old_rest = $sudoku_rest;
// Zahl in der gleichen Box aus den anderen Resten entfernen
foreach (box($s + 27*$box_array[0]) as $value) {
// Nicht aber in der untersuchten Spalte
if (col_number($value) == $s) continue;
if (strpos($sudoku_rest[$value], "$z") !== false) {
$a_1 = box_number_r($value) + 1;
$b_1 = box_number_s($value) + 1;
$sudoku_rest[$value] = str_replace($z, "", $sudoku_rest[$value]);
}
}
if ($old_rest != $sudoku_rest) echo "<BR>Zahl \"$z\" kommt in Spalte $s_1 nur in der Box $a_1/$b_1 vor\n";
}
}
}
// Zeilen-Spalten-Test der Reste in einer Box
// Beispiel: Reste in einer Box
// "367", "678", "38"
// "179", "", "89"
// "139", "54", ""
// Die "1" kommt in dieser Box nur der ersten Spalte vor => Also kann man in den anderen Resten dieser Spalte der anderen Boxen diese Zahl streichen
for ($a = 0; $a < 3; $a++) {
for ($b = 0; $b < 3; $b++) {
$a_1 = $a + 1;
$b_1 = $b + 1;
$index = 27*$a + 3*$b;
for ($z = 1; $z <= 9; $z++) {
$zeile_array = array();
$spalte_array = array();
foreach (box($index) as $value) {
if (strpos($sudoku_rest[$value], "$z") !== false) {
$zeile_array[] = floor($value/9);
$spalte_array[] = fmod($value,9);
}
}
sort($zeile_array);
sort($spalte_array);
// Falls Treffer: teste auf alle in gleicher Zeile bzw. Spalte
$treffer = count($zeile_array); // identisch mit count($spalte_array)
// Nur ein Treffer ist uninteressant (Treffer = 1 wird auch schon oben abgehandelt)
if ($treffer > 1) {
// Pruefe, ob erster und letzter Wert uebereinstimmen (dann stimmen alle ueberein)
if ($zeile_array[0] == $zeile_array[$treffer-1]) {
$old_rest = $sudoku_rest;
// Zahl in der gleichen Zeile in den anderen Boxen aus den Resten entfernen
$box_nr = -1;
foreach (row(9*$zeile_array[0]) as $value) {
$box_nr++;
if (floor($box_nr/3) == $b) continue;
if (strpos($sudoku_rest[$value], "$z") !== false) {
$z_1 = $zeile_array[0] + 1;
$sudoku_rest[$value] = str_replace($z, "", $sudoku_rest[$value]);
}
}
if ($old_rest != $sudoku_rest) echo "<BR>Zahl \"$z\" kommt in Box $a_1/$b_1 nur in Zeile $z_1 vor\n";
}
// Pruefe, ob erster und letzter Wert uebereinstimmen (dann stimmen alle ueberein)
if ($spalte_array[0] == $spalte_array[$treffer-1]) {
$old_rest = $sudoku_rest;
// Zahl in der gleichen Spalte in den anderen Boxen aus den Resten entfernen
$box_nr = -1;
foreach (col($spalte_array[0]) as $value) {
$box_nr++;
if (floor($box_nr/3) == $a) continue;
if (strpos($sudoku_rest[$value], "$z") !== false) {
$s_1 = $spalte_array[0] + 1;
$sudoku_rest[$value] = str_replace($z, "", $sudoku_rest[$value]);
}
}
if ($old_rest != $sudoku_rest) echo "<BR>Zahl \"$z\" kommt in Box $a_1/$b_1 nur in Spalte $s_1 vor\n";
}
}
}
}
}
} // Ende Ausduennen
// 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)
$streichen = array();
// Einzig aufgetretene Alternativen in Zeilen
for ($r = 0; $r < 9; $r++) {
$index = 9 * $r;
// Jede Zahl
for ($z = 1; $z <= 9; $z++) {
$last = 0;
$anz = 0;
foreach (row($index) as $value) {
if (strlen($sudoku_rest[$value]) >= 1) {
if (strpos($sudoku_rest[$value], "$z") !== FALSE) {
$last = $value;
$anz++;
}
}
}
if ($anz == 1) {
$sudoku_array[$last] = $z;
$sudoku_array_color[$last] = "<FONT COLOR=\"00FF00\"><B>$z</B></FONT>";
$color_num++;
// Merken der Position der nur ein Mal gefundenen Zahl
$streichen[] = $last;
}
}
}
// Einzig aufgetretene Alternativen in Spalten
for ($s = 0; $s < 9; $s++) {
$index = $s;
// Jede Zahl
for ($z = 1; $z <= 9; $z++) {
$last = 0;
$anz = 0;
foreach (col($index) as $value) {
if (strlen($sudoku_rest[$value]) >= 1) {
if (strpos($sudoku_rest[$value], "$z") !== FALSE) {
$last = $value;
$anz++;
}
}
}
if ($anz == 1) {
$sudoku_array[$last] = $z;
$sudoku_array_color[$last] = "<FONT COLOR=\"00FF00\"><B>$z</B></FONT>";
$color_num++;
$streichen[] = $last;
}
}
}
// 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++) {
for ($b = 0; $b < 3; $b++) {
$index = 27*$a + 3*$b;
// Jede Zahl
for ($z = 1; $z <= 9; $z++) {
$last = 0;
$anz = 0;
foreach (box($index) as $value) {
if (strlen($sudoku_rest[$value]) >= 1) {
if (strpos($sudoku_rest[$value], "$z") !== FALSE) {
$last = $value;
$anz++;
}
}
}
if ($anz == 1) {
$sudoku_array[$last] = $z;
$sudoku_array_color[$last] = "<FONT COLOR=\"00FF00\"><B>$z</B></FONT>";
$color_num++;
$streichen[] = $last;
}
}
}
}
foreach ($streichen as $value) $sudoku_rest[$value] = "";
// Einstellige, damit eindeutige Loesungen
// Beispiel: Rest "5" => Eindeutiger Wert
$rest_num = 81;
for ($index = 0; $index < 81; $index++) {
$rest = $sudoku_rest[$index];
if ($rest == "" || strlen($rest) == 1) $rest_num--;
if (strlen($rest) == 1) {
$sudoku_array[$index] = $rest;
$sudoku_array_color[$index] = "<FONT COLOR=\"FF0000\"><B><I>$rest</I></B></FONT>";
$color_num++;
$sudoku_rest[$index] = "";
}
}
// Test, ob evtl. nur noch ein einziger Rest
// Nur zum Schluss sinnvoll
if ($rest_num == 1) {
for ($index = 0; $index < 81; $index++) {
if ($sudoku_rest[$index] != "") {
// Streiche o.B.d.A. in dieser Zeile
$rest = "123456789";
foreach (row($index) as $value) {
$zahl = $sudoku_array[$value];
$rest = str_replace($zahl, "", $rest);
}
$sudoku_array[$index] = $rest;
$sudoku_array_color[$index] = "<FONT COLOR=\"00FF00\"><B>$rest</B></FONT>";
$color_num++;
$sudoku_rest[$index] = "";
break; // Nur ein Mal
}
}
}
// Tests, ob Loesung moeglich ist
// Test in Zeilen
$error = 0;
// In Zeilen
for ($r = 0; $r < 9; $r++) {
$r_1 = $r + 1;
$index = 9 * $r;
$gefunden = array();
foreach (row($index) as $value) {
$z = $sudoku_array[$value];
if ($z != 0) {
if (!in_array($z, $gefunden)) $gefunden[] = $z;
else {
echo "<H2>Keine Lösung! $z mehr als einmal in Zeile $r_1!</H2>";
$error = 1;
}
}
}
}
// Test in Spalten
for ($s = 0; $s < 9; $s++) {
$s_1 = $s + 1;
$index = $s;
$gefunden = array();
foreach (col($index) as $value) {
$z = $sudoku_array[$value];
if ($z != 0) {
if (!in_array($z, $gefunden)) $gefunden[] = $z;
else {
echo "<H2>Keine Lösung! $z mehr als einmal in Spalte $s_1!</H2>";
$error = 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++) {
for ($b = 0; $b < 3; $b++) {
$a_1 = $a + 1;
$b_1 = $b + 1;
$index = 27*$a + 3*$b;
$gefunden = array();
foreach (box($index) as $value) {
$z = $sudoku_array[$value];
if ($z != 0) {
if (!in_array($z, $gefunden)) $gefunden[] = $z;
else {
echo "<H2>Keine Lösung! $z mehr als einmal in Box $a_1/$b_1!</H2>";
$error = 1;
}
}
}
}
}
// Test ob evtl. gar keine Alternativen moeglich sind und gleichzeitig Test auf Ende
// Auch formulierbar mit: for ($index = 0; $index < 81; $index++) {
$besetzt = 0;
$index = 0;
for ($r = 0; $r < 9; $r++) {
$r_1 = $r + 1;
for ($c = 0; $c < 9; $c++) {
$c_1 = $c + 1;
$field_name = "a$index";
$field_value = $sudoku_array[$index];
if ($field_value === 0) {
$rest = $sudoku_rest[$index];
if ($rest == "") {
echo "<H2>Keine Lösung! Mögliche Werte fehlen in Zeile $r_1 / Spalte $c_1!</H2>";
$error = 1;
}
}
else $besetzt++;
$index++;
}
}
// Fuer Uebergabe an naechsten Aufruf als eine Variable (Hidden-Parameter oder Query-String)
$sudoku = "";
foreach ($sudoku_array as $value) {
$sudoku .= $value;
}
// Fuer Uebergabe an naechsten Aufruf als eine Variable (Hidden-Parameter)
$sdrest = "";
foreach ($sudoku_rest as $value) {
$sdrest .= ",$value";
}
$sdrest = substr($sdrest, 1);
// Ausgabe + im Verzweigungsfall naechste Eingabe
if ($status == $anf_status) echo "<H3>Nachher</H3>";
else echo "<P>";
// $color_num == 0 heisst: Keine neuen Werte gefunden (Wert selbst ohne Bedeutung)
if ($color_num == 0 && $rest_num > 0 && $besetzt > 0) {
echo "<FORM METHOD=POST ACTION=\"$php_self\">\n";
echo "<INPUT TYPE=HIDDEN NAME=status VALUE=$status>\n";
echo "<INPUT TYPE=HIDDEN NAME=sudoku VALUE=$sudoku>\n";
echo "<INPUT TYPE=HIDDEN NAME=sdrest VALUE=\"$sdrest\">\n";
}
echo "<TABLE BORDER=1 CELLSPACING=5 CELLPADDING=5>\n";
echo "<TR><TD>\n";
echo "<TABLE CELLSPACING=0 CELLPADDING=5>\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_color[$index];
if ($field_value === 0) {
$rest = $sudoku_rest[$index];
}
else {
$rest = " ";
}
// Wichtig: === wegen Strings im Feld
if ($field_value === 0) {
if ($rest == "") $rest = " ";
if ($rest == "123456789") $rest = ""; /* $rest = "1..9"; */
echo "<TD><INPUT TYPE=TEXT NAME=$field_name VALUE=\"\" SIZE=1 MAXLENGTH=1><BR>$rest</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";
$schritt = $status + 1;
echo "<H3>Schritt $schritt </H3>";
if ($color_num == 0 && $rest_num > 0 && $besetzt > 0) {
echo "<H3><FONT COLOR=\"FF0000\">Keine automatische Lösung gefunden. Versuche Alternativen in einem der $rest_num Eingabe-Felder...</FONT></H3>\n";
echo "<INPUT TYPE=SUBMIT NAME=AUSDUENNEN VALUE=\"Mit Ausdünnen\">\n";
echo " <INPUT TYPE=SUBMIT NAME=STANDARD VALUE=\"Nur Standard-Tests\">\n";
echo "</FORM>\n";
echo "<H3><A HREF=$php_self?${sudoku}_${status} target=\"_blank\">Erzeuge eine neue Webseite mit einer aktuellen Kopie</A></H3>\n";
// $end_status = 0;
break; // Loop
}
if ($error == 1) break;
if ($besetzt == 81) {
echo "<H3><FONT COLOR=\"00FF00\">Glückwunsch: Gelöst :-)</FONT></H3>\n";
// $end_status = 0;
break; // Loop
}
} // Ende Loop
} // Ende Hauptteil
?>
<P><HR><P>
<H3><A HREF="<? echo $php_self; ?>?000000000000000000000000000000000000000000000000000000000000000000000000000000000_0">Neustart</A></H3>
<H3>Standard-Methode</H3>
<UL>
<LI>Ermittle mögliche Werte durch Austreichen:
<BR>Streiche alle Zahlen aus, die in der gleichen Zeile, Spalte oder Box vorkommen
<BR>Beispiel: "123456789" => "169", da z.B. "2","3","4","5","7","8" anderswo (gleiche Zeile, Spalte oder Box) vorkommen
<LI>Suche eindeutige Möglichkeiten, also einzig auftretende Alternativen:
<BR>Zähle in den Resten jeder Zeile, Spalte, Box, ob von allen Alternativen in dieser Zeile, Spalte, Box eine Zahl genau ein Mal vorkommt
<BR>Beispiel: Reste "169","48","16","58","149" => "5" kommt nur ein Mal vor: Also muss in dem "58"-Feld die "5" stehen (Grün markiert)
<LI>Suche alle einstelligen (eindeutigen) Reste innerhalb einer Reihe, Spalte oder Box:
<BR>Beispiel: Reste "348", "6", "3789", "79" => "6" ist einstelliger Rest (<I>Rot (Italic)</I> markiert)
</UL>
<H3>Ausdünnen</H3>
Als Besipiel siehe auch alle vom Typ "Sehr schwieriges Sudoku"
<BR>(Es werden nur erfolgreiche Ausdünn-Treffer angezeigt)
<UL>
<LI>Ausdünnen mit Paaren (ab, ab)
<BR>Beispiel: Reste einer Zeile (oder Spalte oder Box)
<BR>"349", "148", "24", "12", "24"
<BR> => Zahlen 2 und 4 müssen an den beiden Stellen "24", "24" sein
<BR> => Also kann man in den anderen Resten diese Zahlen streichen => Bleibt übrig: "39", "18", "24", "1", "24"
<BR> => Sogar einen eindeutigen Rest ("1") gefunden
<LI>Ausdünnen mit Tripeln (abc, und ab, ac, oder bc als Teile des Tripels)
<BR>Beispiel: Reste einer Zeile (oder Spalte oder Box)
<BR>"459", "348", "249", "29", "1349", "24"
<BR> => Zahlen 2 und 4 und 9 müssen an den drei Stellen "249", "29", "24" sein
<BR> => Also kann man in den anderen Resten diese Zahlen streichen => Bleibt übrig: "5", "38", "249", "29", "13", "24"
<BR> => Sogar einen eindeutigen Rest ("5") gefunden
<LI>Ausdünnen mit Quadrupeln (abcd, und abc, abd, acd, bcd, ab, ac, ad, bc, bd, cd als Teile des Quadrupels) analog
<LI>Ausdünnen mit 5-, 6-, 7-, 8-Tupeln analog
<LI>Box-Test der Reste in einer Zeile (bzw. Spalte)
<BR>Beispiel: Reste in einer Zeile
<BR>"48", "678", "38", "5", "47", "67", "9", "46", "146"
<BR> => Die Zahl 8 kommt in dieser Zeile nur in der ersten Box vor, d.h. sie muss dort sein
<BR> => Also kann man in den anderen Resten dieser Box diese Zahl streichen
<LI>Zeilen-Spalten-Test der Reste in einer Box
<BR>Beispiel: Reste in einer Box
<BR>"367", "678", "38"
<BR>"179", "", "89"
<BR>"139", "54", ""
<BR> => Die Zahl 1 kommt in dieser Box nur der ersten Spalte vor, d.h. sie muss dort sein
<BR> => Also kann man in den anderen Resten dieser Spalte der anderen Boxen diese Zahl streichen
</UL>
Noch nicht implementiert:
<UL>
<LI>Indirekte Tripel (ab, ac, oder bc als Teile eines Tripels)
<LI>Indirekte Quadrupel (abc, abd, acd, bcd, ab, ac, ad, bc, bd oder cd als Teile des Quadrupels) usw.
<LI>Versteckte Paare (abx, aby, ...)
<LI>Versteckte Tripel (abcx, aby, acz, ...)
<LI>Versteckte Quadrupel (abcdx, abcy, abdz, ...) usw.
<LI>Goldene Kette (ab, bc, cd, de, ef, ..., xy, yz, za) => Ausschluss von a in den Zellen, die sowohl von der Anfangszelle als auch von der Endzelle aus sichtbar sind - siehe <A HREF="http://www.coverpop.com/sfiles/Sudoku-GoldenChains.pdf">The Golden Chain Technique</A> oder <A HREF="http://sadmansoftware.com/sudoku/techniques.htm">Sadman Sudoku Solving Techniques</A>
</UL>
<P><HR><P>
<H3><A HREF="<? echo $php_self; ?>?012760800000000903000000000465070382000852000928040517000000000509000000001034260_0" target="_blank">Schwieriges Sudoku</A></H3>
<H3><A HREF="<? echo $php_self; ?>?000000000000060197000073005000000050083005900005031472050019008070604039098007620_0" target="_blank">Anderes schwieriges Sudoku, aber mit Ausdünnen ohne Verzweigung lösbar</A></H3>
<H3><A HREF="<? echo $php_self; ?>?000200000040000080000041397025004600003070200081005900000062834030000010000100000_0" target="_blank">Sehr schwieriges Sudoku, aber mit Ausdünnen in 9 Schritten ohne Verzweigung lösbar</A></H3>
<H3><A HREF="<? echo $php_self; ?>?040007800026000037000090100203000070000162000060000204008020000690000310004500020_0" target="_blank">Sehr schwieriges Sudoku, in 17 Schritten lösbar, in 8 Schritten mit Ausdünnen</A></H3>
<H3><A HREF="<? echo $php_self; ?>?010060720006200300020000000300600200040908060009004005000000050008009400035070080_0" target="_blank">Sehr schwieriges Sudoku, in 18 Schritten lösbar, in 9 Schritten mit Ausdünnen</A></H3>
<H3><A HREF="<? echo $php_self; ?>?070006800009004075500100030010420000004000200000068090020005003850300900003600010_0" target="_blank">Sehr schwieriges Sudoku, in 18 Schritten lösbar, in 9 Schritten mit Ausdünnen</A></H3>
<H3><A HREF="<? echo $php_self; ?>?030000070600000003001205600003407800000000000005601200007803400100000006050000010_0" target="_blank">Sehr schwieriges Sudoku, in 19 Schritten lösbar, in 6 Schritten mit Ausdünnen</A></H3>
<H3><A HREF="<? echo $php_self; ?>?054009008000080009680200007010007050000060000020500090100002084400010000800300120_0" target="_blank">Sehr schwieriges Sudoku, in 19 Schritten lösbar, in 9 Schritten mit Ausdünnen</A></H3>
<H3><A HREF="<? echo $php_self; ?>?200400000001008003000920050906040030030705020020090708010084000800100400000009001_0" target="_blank">Sehr schwieriges Sudoku, in 20 Schritten lösbar, in 7 Schritten mit Ausdünnen</A></H3>
<H3><A HREF="<? echo $php_self; ?>?705000401003000900920000067000103000000050000000709000850000012004000600102000308_0" target="_blank">Sehr schwieriges Sudoku, in 17 Schritten lösbar, in 11 Schritten mit Ausdünnen</A></H3>
<H3><A HREF="<? echo $php_self; ?>?005060003000001009000000000090000002000040070010806000002900000000002000004000800_0" target="_blank">Sehr schwieriges Sudoku, in 20 Schritten lösbar, in 12 Schritten mit Ausdünnen</A></H3>
<H3><A HREF="<? echo $php_self; ?>?000000001000002030004005000000000050000004600017080000000010007020900000500000400_0" target="_blank">Minimal-Sudoku (17 vorgegebene Zahlen), mit Ausdünnen in 7 Schritten lösbar</A></H3>
<H3><A HREF="<? echo $php_self; ?>?530001028000000000010050000004900000809060070007030004000573069000010800000800003_0" target="_blank">Sehr schwieriges Sudoku, mit Ausdünnen in 10 Schritten lösbar</A></H3>
<H3><A HREF="<? echo $php_self; ?>?000000000073402890000301000002000300097000680080109020008000500700806003400507008_0" target="_blank">Sehr schwieriges Sudoku, aber lösbar mit Ausdünnung mit versteckten Paaren</A></H3>
<H3><A HREF="<? echo $php_self; ?>?000008004876000300400790006060051400000000000004620050700045003003000982600900000_0" target="_blank">Sehr schwieriges Sudoku, aber lösbar mit Ausdünnung mit Quadrupeln oder über Goldene Kette</A></H3>
<H3><A HREF="<? echo $php_self; ?>?000803090080205003400100000678000100050010060001000784000009008800501020020407000_0" target="_blank">Sehr schwieriges Sudoku, auch mit Ausdünnen, aber lösbar in 7 Schritten über Goldene Kette</A></H3>
<H3><A HREF="<? echo $php_self; ?>?090700860031005020806000000007050006000307000500010700000000109020600350054008070_0" target="_blank">Sehr schwieriges Sudoku, auch mit Ausdünnen, aber lösbar in 9 Schritten über Goldene Kette</A></H3>
<H3><A HREF="<? echo $php_self; ?>?002100070070005090004087500040500000000761000000002010008670300030200050090003700_0" target="_blank">Sehr schwieriges Sudoku, auch mit Ausdünnen, aber lösbar in 12 Schritten über Goldene Kette</A></H3>
<H3><A HREF="<? echo $php_self; ?>?070000009000700500032050080007630054000080000360095200020010730004300000100000090_0" target="_blank">Angeblich schwierigstes Sudoku, auch mit Ausdünnen ("Diabolisch")</A></H3>
<P><HR><P>
<H3><A HREF="sudoku_solver.php">Variante: Sudoku Solver (Einzelschritt)</A></H3>
<H3><A HREF="sudoku_solver_diag.php">Variante mit Einbeziehung der Diagonalen</A></H3>
<H3><A HREF="sudoku_solver_color.php">Variante: Farb-Sudoku</A></H3>
<P><HR><P>
<H3><A HREF="http://apollo.zeit.de/sudoku/" target="_blank">DIE ZEIT: Sudoku</A></H3>
<H3><A HREF="http://www.sudoku.org.uk/daily.asp" target="_blank">The Daily Telegraph: Sudoku</A></H3>
<H3><A HREF="sudoku_solver_loop.phps" target="_blank">(Für Neugierige: Dieses PHP-Programm)</A></H3>
<H5>Kommentare bitte an <A HREF=mailto:I.Giese@gsi.de>Ingolf Giese</A></H5>
</BODY>
</HTML>