Solving Sudoku puzzles - a "spike solution"
This is a "test of concept" page - the code is not clean and
doesn't follow easy maintainance guidelines. It would
need some work to turn it into production code! You can try
it out (if you dare!) at
sudoku.php4
Provided by Graham Ellis who should
know better than publish horrid research code
like this!
<?php
$horiz = array(0,1,2,3,4,5,6,7,8);
$vert = array(0,9,18,27,36,45,54,63,72);
$clump = array(0,1,2,9,10,11,18,19,20);
$h_start = $vert;
$v_start = $horiz;
$c_start = array (0,3,6,27,30,33,54,57,60);
session_name("gg");
session_start();
if (! $_SESSION[current]) {
$current = 0;
} else {
$current = $_SESSION[current];
}
######################### Finish current form
switch ($current) {
case 0: // Finish up from initialisation
$_SESSION[fixed] = array_pad(array (), 81, 0);
$_SESSION[reason] = array_pad(array (), 81, "white");
$_SESSION[calculated] = array_pad(array (), 81, 0);
$_SESSION[starter] = $_SESSION[fixed];
$current = 1;
break;
case 1:
for ($k=0; $k<81; $k++) {
if ($_REQUEST["$k"]) {
$_SESSION[fixed][$k] = $_REQUEST["$k"];
$_SESSION[reason][$k] = "red";
$_SESSION[calculated][$k] = $_REQUEST["$k"];
} else {
$_SESSION[calculated][$k] = array(1,2,3,4,5,6,7,8,9);
}
}
$_SESSION[starter] = $_SESSION[fixed];
$current = 2;
break;
case 2:
$current = 0;
break;
default:
$current = 0;
break;
}
$_SESSION[current] = $current;
######################### Prepare for next form
switch ($current) {
case 1: // Initial display
$which = "Initial";
break;
case 2: // Suggestions display
$which = "Suggestions";
$_SESSION[starter] = $_SESSION[fixed];
# Iterate possibilities
$iteract = 1;
while ($iteract) {
$iteract = 0;
$_SESSION[calculated] = $_SESSION[fixed];
for ($k=0; $k<81; $k++) {
if ($_SESSION[calculated][$k] == 0 ) {
$_SESSION[calculated][$k] = array(1,2,3,4,5,6,7,8,9);
}
}
foreach ($h_start as $offset) {
foreach ($horiz as $current) {
if ($_SESSION[fixed][$offset + $current]) {
foreach ($horiz as $used) {
if (is_array($_SESSION[calculated][$offset+$used]))
{
$_SESSION[calculated][$offset+$used] =
array_merge($_SESSION[calculated][$offset+$used], -$_SESSION[fixed][$offset+$current]);
}
}
}
}
}
foreach ($v_start as $offset) {
foreach ($vert as $current) {
if ($_SESSION[fixed][$offset + $current]) {
foreach ($vert as $used) {
if (is_array($_SESSION[calculated][$offset+$used]))
{
$_SESSION[calculated][$offset+$used] =
array_merge($_SESSION[calculated][$offset+$used], -$_SESSION[fixed][$offset+$current]);
}
}
}
}
}
foreach ($c_start as $offset) {
foreach ($clump as $current) {
if ($_SESSION[fixed][$offset + $current]) {
foreach ($clump as $used) {
if (is_array($_SESSION[calculated][$offset+$used]))
{
$_SESSION[calculated][$offset+$used] =
array_merge($_SESSION[calculated][$offset+$used], -$_SESSION[fixed][$offset+$current]);
}
}
}
}
}
# Can we make any other definite decisions?
for ($cell = 0; $cell < 81; $cell++) {
if (! $_SESSION[fixed][$cell]){
$have = array (1,1,1,1,1,1,1,1,1);
for ($k=0; $k<count($_SESSION[calculated][$cell]); $k++) {
$n = - $_SESSION[calculated][$cell][$k];
if ($n > 0) $have[$n-1] = 0;
}
$nmatch = 0;
for ($k=0; $k<9; $k++) {
if ($have[$k]) {
$nmatch++;
$matchval = $k+1;
}
}
if ($nmatch == 1) {
$_SESSION[fixed][$cell] = $matchval;
$_SESSION[reason][$cell] = "yellow";
$iteract++;
}
}
}
# If we have place something, skip next section since "calculated" may have changed!
if ($iteract) continue;
# If we haven't fully resolved the puzzle ... any "only possible"s?
###################################################################
$chain_starts = array($c_start,$v_start,$h_start);
$chain_steps = array($clump,$vert,$horiz);
for ($way=0; $way<3; $way++) {
if ($iteract) continue;
$cst = $chain_starts[$way];
$clu = $chain_steps[$way];
foreach ($cst as $offset) {
if ($iteract) continue;
foreach ($clu as $current) {
if ($iteract) continue;
$cell = $offset + $current;
# Skip cells already assigned
if ($_SESSION[fixed][$cell] != 0) continue;
# What may go in THIS cell?
$have = array (1,1,1,1,1,1,1,1,1);
for ($k=0; $k<count($_SESSION[calculated][$cell]); $k++) {
$n = - $_SESSION[calculated][$cell][$k];
if ($n > 0) $have[$n-1] = 0;
}
# remove what may go in OTHER cells in this cluster
$have2 = array (1,1,1,1,1,1,1,1,1);
foreach ($clu as $alsoposs) {
if ($alsoposs == $current) continue;
$cellxx = $offset + $alsoposs;
for ($k=0; $k<count($_SESSION[calculated][$cellxx]); $k++) {
$n = - $_SESSION[calculated][$cellxx][$k];
if ($n > 0) $have2[$n-1] = 0;
}
}
$nmatch = 0;
for ($k=0; $k<9; $k++) {
if ($have[$k] and $have2[$k] == 0) {
$nmatch++;
$matchval = $k+1;
}
}
if ($nmatch == 1) {
$_SESSION[fixed][$cell] = $matchval;
$_SESSION[reason][$cell] = "#FFCCFF";
$iteract++;
}
}
}
}
}
break;
}
# if ($current == 0) session_destroy();
######################### Display Status
$rs = "<form method=POST><table border=1>";
for ($yo=0; $yo<3; $yo++) {
$rs .= "<tr>";
for ($xo=0; $xo<3; $xo++) {
$rs .= "<td><table border=1>";
for ($yi=0; $yi<3; $yi++) {
$rs .= "<tr>";
for ($xi=0; $xi<3; $xi++) {
$val = $xi + 3 * $xo + 9 * $yi + 27 * $yo;
if ($current == 1)
$rs .= "<td>$val<input name=$val size=1></td>";
if ($current != 1) {
if ($_SESSION[fixed][$val]){
# $colour = "yellow";
# if ($_SESSION[starter][$val]) $colour = "red";
$colour = $_SESSION[reason][$val];
$rs .= "<td bgcolor=$colour><b>".$_SESSION[fixed][$val]."</b></td>";
} else {
$have = array (1,1,1,1,1,1,1,1,1);
for ($k=0; $k<count($_SESSION[calculated][$val]); $k++) {
$n = - $_SESSION[calculated][$val][$k];
if ($n > 0) $have[$n-1] = 0;
}
$say = "! ";
for ($k=0; $k<9; $k++) {
if ($have[$k]) $say .= " ".($k+1);
}
# $rs .= "<td>".join(" ",$_SESSION[calculated][$val])."</td>";
$rs .= "<td>".$say."!". $_SESSION[fixed][$val]."</td>";
}
}
}
$rs .= "</tr>";
}
$rs .= "</table></td>";
}
$rs .= "<tr>";
}
$rs .= "</table><br><input type=submit></form>";
?>
<html>
<head><title>Sudoku demonstration</title></head>
<body>
<?= $which ?> table<br>
<?= $rs ?>
</body>
</html>