Sudoku 2006: Quellcode
<HTML>
<HEAD>
<TITLE>Sudoku Solver</TITLE>
</HEAD>
<BODY TEXT="#000000" BGCOLOR="#F8F8FC">
<H1>Sudoku Solver - From Web Archive September 24, 2005</H1>
<?php
// Nach: http://web.archive.org/web/20050924021428/http://www-aix.gsi.de/sudoku/sudoku_solver.php
// Wiki: In Deutschland und Österreich führte der regelmäßige Abdruck in Tageszeitungen und Fernsehzeitschriften seit Ende 2005 zu einer raschen Verbreitung.
// Haupttrick: Berechne aus dem Index (0 - 80) die Index-Felder der zugeh. Zeile, Spalte, Box
function row($index) {
$r = floor($index/9);
for ($i = 0; $i < 9; $i++) $k[$i] = 9*$r + $i;
return $k;
}
function col($index) {
$s = fmod($index,9);
for ($i = 0; $i < 9; $i++) $l[$i] = $s + 9*$i;
return $l;
}
function box($index) {
$r = floor($index/9);
$s = fmod($index,9);
$t = floor($r/3);
$u = floor($s/3);
$v = 27*$t + 3*$u;
$w = 0;
for ($i = 0; $i < 3; $i++) {
for ($j = 0; $j < 3; $j++) {
$m[$w] = $v + 9*$i + $j;
$w++;
}
}
return $m;
}
// Falls von "Erzeuge eine neue Webseite..."
$query = getenv("QUERY_STRING");
if ($query != "") $status = (int) substr($query, 82);
// NEU, DA NICHT MEHR DIREKT BEI ALTEM PHP
if (array_key_exists('status', $_POST)) $status = $_POST['status']; else $status = "";
if (array_key_exists('sudoku', $_POST)) $sudoku = $_POST['sudoku']; else $sudoku = "";
if ($status == "") {
// Anfang bzw. Default
$status = 0;
// Einfachste Lösung mit einem einzeiligen (alle Zeilen nebeneinander) Feld (mit Index 0 - 80),
// wobei über die Funktion row/col/box zu einem gegebenen Index alle (jeweils 9) zu einer
// Zeile, Spalte oder Box gehörenden Indizes berechnet und als Feld zurückgegeben werden.
$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,
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,
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);
echo "<H3>Geben Sie die Ausgangszahlen ein</H3>";
// Festes Beispiel (Moderate bis Tough), zum Testen auskommentieren
// $sudoku_array = array(7,0,8,0,2,0,1,0,6, 2,0,0,0,0,0,0,0,5, 0,4,0,1,0,3,0,7,0,
// 0,0,1,0,0,0,3,0,0, 0,0,0,8,7,6,0,0,0, 0,0,4,0,0,0,5,0,0,
// 0,8,0,9,0,7,0,5,0, 1,0,0,0,0,0,0,0,3, 3,0,6,0,4,0,7,0,8);
// Festes Beispiel (Diabolical !), zum Testen auskommentieren
// $sudoku_array = array(0,9,0,7,0,0,8,6,0, 0,3,1,0,0,5,0,2,0, 8,0,6,0,0,0,0,0,0,
// 0,0,7,0,5,0,0,0,6, 0,0,0,3,0,7,0,0,0, 5,0,0,0,1,0,7,0,0,
// 0,0,0,0,0,0,1,0,9, 0,2,0,6,0,0,3,5,0, 0,5,4,0,0,8,0,7,0);
}
else {
echo "<H3>Grün markierte Ziffern sind einzig aufgetretene Alternativen
innerhalb einer Reihe, Spalte oder Box</H3>";
echo "<H3>Rot markierte Ziffern sind einstellige, damit eindeutige Lösungen
innerhalb einer Reihe, Spalte oder Box</H3>";
// (int) wichtig wegen späterem ===
for ($k = 0; $k < 81; $k++) $sudoku_array[$k] = (int) substr($sudoku, $k, 1);
}
// Falls von "Erzeuge eine neue Webseite..."
if ($query != "") {
// (int) wichtig wegen späterem ===
for ($k = 0; $k < 81; $k++) $sudoku_array[$k] = (int) substr($query, $k, 1);
}
// Aus Formblatt Parameter übertragen
if ($status > 0) {
for ($k = 0; $k < 81; $k++) {
$string_name = "a$k";
$orig = $_POST["$string_name"];
// $orig = ${$string_name}; NUR BEI ALTEM PHP
// Abfangen von Eingabefehlern
if ($orig != "") {
$name = (int) $orig;
if ($name < 1 || $name > 9) {
$k_1 = $k + 1;
echo "<H3><FONT COLOR=\"FF0000\">Fehler im Feld $k_1: Keine Ziffer zwischen 1 und 9 ($orig)</FONT></H3>";
$sudoku_array[$k] = 0;
}
else {
$sudoku_array[$k] = $name;
}
}
}
}
$status++;
// Wegen farbiger Ausgabe
$sudoku_array_color = $sudoku_array;
$color_num = 0;
// Ermittle mögliche Werte durch Austreichen
for ($index = 0; $index < 81; $index++) {
$field_name = "a$index";
$field_value = $sudoku_array[$index];
if ($field_value == 0) {
// Streichen
$rest = "123456789";
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_rest[$index] = $rest;
}
// Suche eindeutige Möglichkeiten (nur 1 Alternative)
$streichen = array();
// In Zeilen
for ($r = 0; $r < 9; $r++) {
$index = 9 * $r;
// Jede Ziffer
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++;
$streichen[] = $last;
}
}
}
// In Spalten
for ($s = 0; $s < 9; $s++) {
$index = $s;
// Jede Ziffer
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;
}
}
}
// In Boxen
for ($a = 0; $a < 3; $a++) {
for ($b = 0; $b < 3; $b++) {
$index = 27*$a + 3*$b;
// Jede Ziffer
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] = "";
// Eindeutige Möglichkeiten
$rest_num = 81;
$index = 0;
for ($r = 0; $r < 9; $r++) {
for ($c = 0; $c < 9; $c++) {
$rest = $sudoku_rest[$index];
if ($rest == "") $rest_num--;
if (strlen($rest) == 1) {
$sudoku_array[$index] = $rest;
$sudoku_array_color[$index] = "<FONT COLOR=\"FF0000\"><B>$rest</B></FONT>";
$color_num++;
$sudoku_rest[$index] = "";
}
$index++;
}
}
// Tests, ob Lösung möglich ist
// 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>";
}
}
}
// 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>";
}
}
}
// In Boxen
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>";
}
}
}
}
// Test ob evtl. gar keine Alternativen möglich sind und gleichzeitig Test auf Ende
$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>";
}
else $besetzt++;
$index++;
}
}
// For Hidden Parameter or Query String
$sudoku = "";
foreach ($sudoku_array as $value) {
$sudoku .= $value;
}
// Ausgabe + nächste Eingabe
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 "<TABLE BORDER=1 CELLSPACING=5 CELLPADDING=5>\n";
echo "<TR><TD>\n";
echo "<TABLE CELLSPACING=10 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 = "1..9";
echo "<TD><INPUT TYPE=TEXT NAME=$field_name VALUE=\"\" SIZE=1 MAXSIZE=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";
echo "<H3>Schritt $status <INPUT TYPE=SUBMIT VALUE=\"Berechne und Ersetze\"></H3>\n";
if ($color_num == 0 && $rest_num > 0 && $besetzt > 0) {
echo "<H3>Keine automatische Lösung gefunden. Versuche Alternativen in einem der $rest_num Eingabe-Feldern...</H3>\n";
echo "<H3><A HREF=$PHP_SELF?${sudoku}_${status} target=\"_blank\">Erzeuge eine neue Webseite mit einer aktuellen Kopie</A></H3>\n";
}
if ($besetzt == 81) echo "<H3><FONT COLOR=\"00FF00\">Glückwunsch: Gelöst :-)</FONT></H3>\n";
echo "<H3><A HREF=$PHP_SELF?000000000000000000000000000000000000000000000000000000000000000000000000000000000_0>Neustart</A></H3>\n";
echo "</FORM>\n";
?>
<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_source.php" target="_blank">(Für Neugierige: Dieses PHP-Programm)</A></H3>
<H4><A HREF=hinweis+impressum.html>DSGVO-Hinweis und Impressum</A></H4>
</BODY>
</HTML>