<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<title>Sudoku</title>
<style type="text/css">
.input
{
border: dotted 1px #CCCCCC;
margin: 0;
padding: 1px;
width: 20px;
height: 20px;
text-align: right;
display: block;
float: left;
}
.top { border-top: solid 1px #000000; }
.left { border-left: solid 1px #000000; }
.right { border-right: solid 1px #000000; }
.bottom{ border-bottom: solid 1px #000000; }
</style>
</head>
<body>
<?php
$is_input = 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
);
$data = 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
);
function check_valid_source(&$data)
{
for ($i = 0; $i < 81; ++$i)
{
if ($data[$i] != 0)
{
$values = get_valid_values($i, $data);
if (!in_array($data[$i], $values)) return false;
}
}
return true;
}
function get_block_indices($index)
{
if ($index >= 81) throw new Exception("Invalid Index. Cannot get block info");
$indices = array();
$index_to_block_map = array(
0,0,0,1,1,1,2,2,2,
0,0,0,1,1,1,2,2,2,
0,0,0,1,1,1,2,2,2,
3,3,3,4,4,4,5,5,5,
3,3,3,4,4,4,5,5,5,
3,3,3,4,4,4,5,5,5,
6,6,6,7,7,7,8,8,8,
6,6,6,7,7,7,8,8,8,
6,6,6,7,7,7,8,8,8
);
$block_index = $index_to_block_map[$index];
for ($i = 0; $i < 81; ++$i)
{
if ($index_to_block_map[$i] == $block_index)
{
array_push($indices, $i);
}
}
return $indices;
}
function get_valid_values($index, &$data)
{
if ($index >= 81) return array();
$valid_values = array(1,2,3,4,5,6,7,8,9);
$row = ((int)($index / 9)) * 9;
$col = (int)($index % 9);
$block_indices = get_block_indices($index);
for ($i = 0; $i < 9; ++$i)
{
if (($row + $i != $index) && ($data[$row + $i] != 0)) $valid_values[$data[$row + $i] - 1] = 0;
if (($col + ($i * 9) != $index) && ($data[$col + ($i * 9)] != 0)) $valid_values[$data[$col + ($i * 9)] - 1] = 0;
if (($block_indices[$i] != $index) && ($data[$block_indices[$i]] != 0)) $valid_values[$data[$block_indices[$i]] - 1] = 0;
}
return array_filter($valid_values);
}
for ($i = 0; $i < 81; ++$i)
{
$data[$i] = (isset($_POST["input"][$i])) ? (int)($_POST["input"][$i]) : 0;
if ($data[$i] != 0) $is_input[$i] = 1;
}
$watchdog = 0;
$index = 0;
$solved = 0;
if (count(array_filter($is_input)) > 0)
{
try
{
if (!check_valid_source($data)) throw new Exception("Unsolvable. Conflict in source!");
while (!$solved)
{
if ($index == 81) { $solved = 1; break; }
if (++$watchdog > 100000000) throw new Exception("Watchdog!");
for ($i = $index + 1; $i < 81; ++$i)
{
$data[$i] = $data[$i] * $is_input[$i];
}
if (!$is_input[$index])
{
$value = 0;
$valid_values = get_valid_values($index, $data);
do
{
$value = (int)array_shift($valid_values);
} while (($value != 0) && ($value <= $data[$index]));
if ($value == 0)
{
while (($is_input[--$index]) && ($index >= 0));
if ($index < 0) throw new Exception("Unsolvable");
}
else
{
$data[$index] = $value;
++$index;
}
}
else
{
++$index;
}
}
}
catch (Exception $ex)
{
echo $ex->getMessage();
}
}
?>
<form action="index.php" method="post" style="margin: 0; padding: 0">
<div>
<?php for ($y = 0; $y < 81; $y += 9): ?>
<?php for ($x = 0; $x < 9; ++$x): ?>
<?php $classes = array("input"); ?>
<?php if (($x % 3) == 0) array_push($classes, "left"); ?>
<?php if (($y % 27) == 0) array_push($classes, "top"); ?>
<?php if ($y == 72) array_push($classes, "bottom"); ?>
<?php if ($x == 8) array_push($classes, "right"); ?>
<input type="text" name="input[]" value="<?= $data[$x + $y] ?>" class="<?= implode(" ", $classes) ?>" />
<?php endfor; ?>
<div style="clear: both;"></div>
<?php endfor; ?>
<div style="clear: both;"></div>
<input type="submit" value="Solve!" />
</div>
</form>
</body>
</html>
EPT
