Finally the all awaited su doku solver in PHP. This is a release after quite a few attempts to convert my c++ logic algorithms to PHP. I ended up with a basic, not so complete script. It is right now a bit messy with all the HTML and Javascript, but never the less, it's there. If you make any updates on it please inform me about it.
Thank you,
leapinglangoor
for ($r = 1; $r < 10; $r++)
for ($c = 1; $c < 10; $c++) {
$thevalue = $matrix[$r][$c];
if (!is_array($thevalue)) {
// only eliminate once for each square
if (in_array("($r, $c)", $didelim)) continue; array_push($didelim, "($r, $c)");
$block_startrow = $r - (($r - 1) % 3); $block_startcol = $c - (($c - 1) % 3);
print "($r, $c) is a $thevalue, so no other square in row $r, column $c, or block " . (1+(($block_startrow - 1) / 3)*3 + (($block_startcol - 1) / 3)) . " is a $thevalue<br />"; $thiselim = true;
// eliminate the value from other squares in this row
for ($x = 1; $x < 10; $x++)
if (is_array($matrix[$x][$c])) {
$location = array_search($thevalue, $matrix[$x][$c]);
if ($location !== false) array_splice($matrix[$x][$c], $location, 1);
if (count($matrix[$x][$c]) == 1) {
$changed = true;
$thenewvalue = $matrix[$x][$c][0];
$matrix[$x][$c] = $thenewvalue;
print "($x, $c) only has one remaining possibility, $thenewvalue <span class=\"gr\">(" . --$howmany . " squares to go)</span><br />";
if ($howmany == 0) return false;
}
}
// eliminate the value from other squares in this column
for ($x = 1; $x < 10; $x++)
if (is_array($matrix[$r][$x])) {
$location = array_search($thevalue, $matrix[$r][$x]);
if ($location !== false) array_splice($matrix[$r][$x], $location, 1);
if (count($matrix[$r][$x]) == 1) {
$changed = true;
$thenewvalue = $matrix[$r][$x][0];
$matrix[$r][$x] = $thenewvalue;
print "($r, $x) only has one remaining possibility, $thenewvalue<span class=\"gr\">(" . --$howmany . " squares to go)</span><br />";
if ($howmany == 0) return false;
}
}
// eliminate the value from other squares in this 3x3 block
for ($x = $block_startrow; $x < $block_startrow + 3; $x++)
for ($y = $block_startcol; $y < $block_startcol + 3; $y++)
if (is_array($matrix[$x][$y])) {
$location = array_search($thevalue, $matrix[$x][$y]);
if ($location !== false) array_splice($matrix[$x][$y], $location, 1);
if (count($matrix[$x][$y]) == 1) {
$changed = true;
$thenewvalue = $matrix[$x][$y][0];
$matrix[$x][$y] = $thenewvalue;
print "($x, $y) only has one remaining possibility, $thenewvalue<span class=\"gr\">(" . --$howmany . " squares to go)</span><br />";
if ($howmany == 0) return false;
}
}
}
}
return $changed;
}
function apply_placement() {
global $matrix, $howmany; $changed = false;
print "<br /><b>Number Placement</b><br />";
// * * * * *
// NUMBER PLACEMENT
// In this phase, we go through each row/column/block and try to add the numbers that are missing when we count from 1 to 9.
// If any number from 1 to 9 is missing from the row/column/block, and there is only one possibility of where to place it,
// add the number.
// check rows
for ($r = 1; $r < 10; $r++)
// check each number from 1 to 9
for ($value = 1; $value < 10; $value++) {
$where = array();
// stop if this number is already somewhere in this row
$abort = false;
for ($c = 1; $c < 10; $c++)
if (!is_array($matrix[$r][$c]) && $matrix[$r][$c] == $value)
$abort = true;
if (!$abort) {
// the number is not in this row, but it does need to be
// list all of the possible places where the number could appear in this row
for ($c = 1; $c < 10; $c++)
if (is_array($matrix[$r][$c]) && in_array($value, $matrix[$r][$c])) array_push($where, array($r, $c));
// add the number if there is only one possibility
if (count($where) == 1) {
$changed = true;
list($where_r, $where_c) = array_pop($where);
$matrix[$where_r][$where_c] = $value;
print "($where_r, $where_c) is the only possible place for the $value in row $r<span class=\"gr\">(" . --$howmany . " squares to go)</span><br />";
if ($howmany == 0) return false;
print '<div class="jumpindent">'; apply_elimination(); print '</div>';
}
}
}
// check columns
for ($c = 1; $c < 10; $c++)
// check each number from 1 to 9
for ($value = 1; $value < 10; $value++) {
$where = array();
// stop if this number is already somewhere in this row
$abort = false;
for ($r = 1; $r < 10; $r++)
if (!is_array($matrix[$r][$c]) && $matrix[$r][$c] == $value)
$abort = true;
if (!$abort) {
// the number is not in this column, but it does need to be
// list all of the possible places where the number could appear in this column
for ($r = 1; $r < 10; $r++)
if (is_array($matrix[$r][$c]) && in_array($value, $matrix[$r][$c])) array_push($where, array($r, $c));
// add the number if there is only one possibility
if (count($where) == 1) {
$changed = true;
list($where_r, $where_c) = array_pop($where);
$matrix[$where_r][$where_c] = $value;
print "($where_r, $where_c) is the only possible place for the $value in column $c<span class=\"gr\">(" . --$howmany . " squares to go)</span><br />";
if ($howmany == 0) return false;
print '<div class="jumpindent">'; apply_elimination(); print '</div>';
}
}
}
// check 3x3 blocks
for ($r = 0; $r < 3; $r++)
for ($c = 0; $c < 3; $c++)
// check each number from 1 to 9
for ($value = 1; $value < 10; $value++) {
$where = array();
// stop if this number is already somewhere in this block
$abort = false;
for ($rr = 1+$r*3; $rr < 4+$r*3; $rr++)
for ($cc = 1+$c*3; $cc < 4+$c*3; $cc++)
if (!is_array($matrix[$rr][$cc]) && $matrix[$rr][$cc] == $value)
$abort = true;
if (!$abort) {
// the number is not in this 3x3 block, but it does need to be
// list all of the possible places where the number could appear in this block
for ($rr = 1+$r*3; $rr < 4+$r*3; $rr++)
for ($cc = 1+$c*3; $cc < 4+$c*3; $cc++)
if (is_array($matrix[$rr][$cc]) && in_array($value, $matrix[$rr][$cc])) array_push($where, array($rr, $cc));
// add the number if there is only one possibility
if (count($where) == 1) {
$changed = true;
list($where_r, $where_c) = array_pop($where);
$matrix[$where_r][$where_c] = $value;
print "($where_r, $where_c) is the only possible place for the $value in block " . (1+$r*3 + $c) . "<span class=\"gr\">(" . --$howmany . " squares to go)</span><br />";
if ($howmany == 0) return false;
print '<div class="jumpindent">'; apply_elimination(); print '</div>';
// are all the possibilities for this value in this block in the same row?
if (count($urows) == 1) {
$therow = array_pop($urows);
$othercols = array_diff(range(1, 9), $ucols);
foreach ($othercols as $thecol) {
if (is_array($matrix[$therow][$thecol])) {
$location = array_search($value, $matrix[$therow][$thecol]);
if ($location !== false) {
$changed = true;
array_splice($matrix[$therow][$thecol], $location, 1);
print "($therow, $thecol) is not a $value because the $value in that row must be in block " . (1+$r*3 + $c) . "<br />";
}
if (count($matrix[$therow][$thecol]) == 1) {
$changed = true;
$thenewvalue = $matrix[$therow][$thecol][0];
$matrix[$therow][$thecol] = $thenewvalue;
print "($therow, $thecol) only has one remaining possibility, $thenewvalue <span class=\"gr\">(" . --$howmany . " squares to go)</span><br />";
if ($howmany == 0) return false;
print '<div class="jumpindent">'; apply_elimination(); print '</div>';
}
}
}
}
// are all the possibilities for this value in this block in the same column?
if (count($ucols) == 1) {
$thecol = array_pop($ucols);
$otherrows = array_diff(range(1, 9), $urows);
foreach ($otherrows as $therow) {
if (is_array($matrix[$therow][$thecol])) {
$location = array_search($value, $matrix[$therow][$thecol]);
if ($location !== false) {
$changed = true;
array_splice($matrix[$therow][$thecol], $location, 1);
print "($therow, $thecol) is not a $value because the $value in that column must be in block " . (1+$r*3 + $c) . "<br />";
}
if (count($matrix[$therow][$thecol]) == 1) {
$changed = true;
$thenewvalue = $matrix[$therow][$thecol][0];
$matrix[$therow][$thecol] = $thenewvalue;
print "($therow, $thecol) only has one remaining possibility, $thenewvalue <span class=\"gr\">(" . --$howmany . " squares to go)</span><br />";
if ($howmany == 0) return false;
print '<div class="jumpindent">'; apply_elimination(); print '</div>';
}
}
}
}
}
}
}
return $changed;
}
function apply_locked_pairing() {
global $matrix, $howmany; $changed = false;
print "<br /><b>Locked Pairing</b><br />";
// * * * * *
// LOCKED PAIRING
// If X squares in a row/column/block all share an identical set of X possibilities, exclude these possibilities
// from the other squares in the same row/column/block.
// check rows
for ($r = 1; $r < 10; $r++) {
// compile an array of the possibilities for each square in this row
$rowpossibilities = array();
for ($c = 1; $c < 10; $c++)
if (is_array($matrix[$r][$c])) $rowpossibilities[ serialize($matrix[$r][$c]) ]++;
foreach ($rowpossibilities as $tp_serialize => $tp_count) {
$tp_array = unserialize($tp_serialize);
if ($tp_count > 1 && $tp_count == count($tp_array)) {
for ($c = 1; $c < 10; $c++)
if (is_array($matrix[$r][$c]) && $matrix[$r][$c] !== $tp_array) {
foreach ($tp_array as $tp) {
$location = array_search($tp, $matrix[$r][$c]);
if ($location !== false) {
$changed = true;
array_splice($matrix[$r][$c], $location, 1);
print "($r, $c) is not $tp because the $tp in row $r is locked in a $tp_count-square pairing<br />";
}
}
if (count($matrix[$r][$c]) == 1) {
$changed = true;
$thenewvalue = $matrix[$r][$c][0];
$matrix[$r][$c] = $thenewvalue;
print "($r, $c) only has one remainig possibility, $thenewvalue <span class=\"gr\">(" . --$howmany . " squares to go)</span><br />";
if ($howmany == 0) return false;
print '<div class="jumpindent">'; apply_elimination(); print '</div>';
}
}
}
}
}
// check columns
for ($c = 1; $c < 10; $c++) {
// compile an array of the possibilities for each square in this column
$columnpossibilities = array();
for ($r = 1; $r < 10; $r++)
if (is_array($matrix[$r][$c])) $columnpossibilities[ serialize($matrix[$r][$c]) ]++;
foreach ($columnpossibilities as $tp_serialize => $tp_count) {
$tp_array = unserialize($tp_serialize);
if ($tp_count > 1 && $tp_count == count($tp_array)) {
for ($r = 1; $r < 10; $r++)
if (is_array($matrix[$r][$c]) && $matrix[$r][$c] !== $tp_array) {
foreach ($tp_array as $tp) {
$location = array_search($tp, $matrix[$r][$c]);
if ($location !== false) {
$changed = true;
array_splice($matrix[$r][$c], $location, 1);
print "($r, $c) is not $tp because the $tp in column $c is locked in a $tp_count-square pairing<br />";
}
}
if (count($matrix[$r][$c]) == 1) {
$changed = true;
$thenewvalue = $matrix[$r][$c][0];
$matrix[$r][$c] = $thenewvalue;
print "($r, $c) only has one remaining possibility, $thenewvalue <span class=\"gr\">(" . --$howmany . " squares to go)</span><br />";
if ($howmany == 0) return false;
print '<div class="jumpindent">'; apply_elimination(); print '</div>';
}
}
}
}
}
// check 3x3 blocks
for ($r = 0; $r < 3; $r++)
for ($c = 0; $c < 3; $c++) {
// compile an array of the possibilities for each square in this 3x3 block
$blockpossibilities = array();
for ($rr = 1+$r*3; $rr < 4+$r*3; $rr++)
for ($cc = 1+$c*3; $cc < 4+$c*3; $cc++)
if (is_array($matrix[$rr][$cc])) $blockpossibilities[ serialize($matrix[$rr][$cc]) ]++;
foreach ($blockpossibilities as $tp_serialize => $tp_count) {
$tp_array = unserialize($tp_serialize);
if ($tp_count > 1 && $tp_count == count($tp_array)) {
for ($rr = 1+$r*3; $rr < 4+$r*3; $rr++)
for ($cc = 1+$c*3; $cc < 4+$c*3; $cc++)
if (is_array($matrix[$rr][$cc]) && $matrix[$rr][$cc] !== $tp_array) {
foreach ($tp_array as $tp) {
$location = array_search($tp, $matrix[$rr][$cc]);
if ($location !== false) {
$changed = true;
array_splice($matrix[$rr][$cc], $location, 1);
print "($rr, $cc) is not $tp because the $tp in block " . (1+$r*3 + $c) . " is locked in a $tp_count-square pairing<br />";
}
}
if (count($matrix[$rr][$cc]) == 1) {
$changed = true;
$thenewvalue = $matrix[$rr][$cc][0];
$matrix[$rr][$cc] = $thenewvalue;
print "($rr, $cc) only has one remaining possibility, $thenewvalue <span class=\"gr\">(" . --$howmany . " squares to go)</span><br />";
if ($howmany == 0) return false;
print '<div class="jumpindent">'; apply_elimination(); print '</div>';
}
}
}
}
}
return $changed;
}
function apply_hidden_pairing() {
global $matrix, $howmany; $changed = false;
print "<br /><b>Hidden Pairing</b><br />";
// * * * * *
// HIDDEN PAIRING
// If X possibilities exist in only X squares in a row/column/block, exclude any other possibilities from these X squares.
// check rows
for ($r = 1; $r < 10; $r++) {
// compile an array of each number and its locations in this row
$location = array();
for ($c = 1; $c < 10; $c++)
if (is_array($matrix[$r][$c]))
foreach ($matrix[$r][$c] as $value) {
if (!$location[$value]) $location[$value] = array();
array_push($location[$value], "($r, $c)");
}
foreach ($location as $tp_number => $tp_locations)
foreach ($location as $tp_number2 => $tp_locations2) {
if ($tp_number >= $tp_number2) continue;
$combined = array_count_values(array_merge($tp_locations, $tp_locations2));
if (count(array_unique($combined)) == 1 && array_shift($combined) == 2) {
$int = array_intersect($location[$tp_number], $location[$tp_number2]);
if (count($int) == 2) {
print "hidden pair in row $r: $tp_number and $tp_number2<br>";
foreach ($location[$tp_number] as $square) {
$square_r = substr($square, 1, 1); $square_c = substr($square, 4, 1);
if ($matrix[$square_r][$square_c] !== array($tp_number, $tp_number2)) {
print "($square_r, $square_c) is either $tp_number or $tp_number2 because these numbers are locked in a 2-square pairing<br />";
$matrix[$square_r][$square_c] = array($tp_number, $tp_number2); }
}
}
}
}
}
// check columns
for ($c = 1; $c < 10; $c++) {
// compile an array of each number and its locations in this column
$location = array();
for ($r = 1; $r < 10; $r++)
if (is_array($matrix[$r][$c]))
foreach ($matrix[$r][$c] as $value) {
if (!$location[$value]) $location[$value] = array();
array_push($location[$value], "($r, $c)");
}
foreach ($location as $tp_number => $tp_locations)
foreach ($location as $tp_number2 => $tp_locations2) {
if ($tp_number >= $tp_number2) continue;
$combined = array_count_values(array_merge($tp_locations, $tp_locations2));
if (count(array_unique($combined)) == 1 && array_shift($combined) == 2) {
$int = array_intersect($location[$tp_number], $location[$tp_number2]);
if (count($int) == 2) {
print "hidden pair in column $c: $tp_number and $tp_number2<br>";
foreach ($location[$tp_number] as $square) {
$square_r = substr($square, 1, 1); $square_c = substr($square, 4, 1);
if ($matrix[$square_r][$square_c] !== array($tp_number, $tp_number2)) {
print "($square_r, $square_c) is either $tp_number or $tp_number2 because these numbers are locked in a 2-square pairing<br />";
$matrix[$square_r][$square_c] = array($tp_number, $tp_number2); }
}
}
}
}
}
return $changed;
}
function apply_fish_cycles() {
global $matrix, $howmany; $changed = false;
print "<br /><b>"X-Wings"</b><br />";
// * * * * *
// FISH CYCLES
// If X possibilities exist in only X squares in a row/column/block, exclude any other possibilities from these X squares.
// check rows
$location = array();
for ($r = 1; $r < 10; $r++)
for ($c = 1; $c < 10; $c++)
if (is_array($matrix[$r][$c]))
foreach ($matrix[$r][$c] as $value) {
if (!$location[$r][$value]) $location[$r][$value] = array();
array_push($location[$r][$value], $c);
}
for ($r = 1; $r < 10; $r++) {
for ($value = 1; $value < 10; $value++) {
if ($location[$r][$value] && count($location[$r][$value]) == 2) {
for ($rr = 1; $rr < 10; $rr++) {
if ($r >= $rr) continue;
if (!$location[$rr][$value]) continue;
$i = array_intersect($location[$r][$value], $location[$rr][$value]);
if (count($i) == 2 && count($location[$rr][$value]) == 2) {
print "$value appears in the same columns in rows $r and $rr<br />";
for ($x = 1; $x < 10; $x++) {
if ($x == $r || $x == $rr) continue;
if (is_array($matrix[$x][ $location[$r][$value][0] ])) {
$pos = array_search($value, $matrix[$x][ $location[$r][$value][0] ]);
if ($pos !== false) {
$changed = true;
array_splice($matrix[$x][ $location[$r][$value][0] ], $pos, 1);
print "($x, {$location[$r][$value][0]}) is not $value because the $value in that column is in either ($r, {$location[$r][$value][0]}) or ($rr, {$location[$r][$value][0]})<br />";
}
}
}
for ($x = 1; $x < 10; $x++) {
if ($x == $r || $x == $rr) continue;
if (is_array($matrix[$x][ $location[$r][$value][1] ])) {
$pos = array_search($value, $matrix[$x][ $location[$r][$value][1] ]);
if ($pos !== false) {
$changed = true;
array_splice($matrix[$x][ $location[$r][$value][1] ], $pos, 1);
print "($x, {$location[$r][$value][1]}) is not $value because he $value in that column is in either ($r, {$location[$r][$value][1]}) or ($rr, {$location[$r][$value][1]})<br />";
}
}
}
}
}
}
}
}
// check columns
$location = array();
for ($r = 1; $r < 10; $r++)
for ($c = 1; $c < 10; $c++)
if (is_array($matrix[$r][$c]))
foreach ($matrix[$r][$c] as $value) {
if (!$location[$c][$value]) $location[$c][$value] = array();
array_push($location[$c][$value], $r);
}
for ($c = 1; $c < 10; $c++) {
for ($value = 1; $value < 10; $value++) {
if ($location[$c][$value] && count($location[$c][$value]) == 2) {
for ($cc = 1; $cc < 10; $cc++) {
if ($c >= $cc) continue;
if (!$location[$cc][$value]) continue;
$i = array_intersect($location[$c][$value], $location[$cc][$value]);
if (count($i) == 2 && count($location[$cc][$value]) == 2) {
print "$value appears in the same rows in columns $c and $cc<br />";
for ($x = 1; $x < 10; $x++) {
if ($x == $c || $x == $cc) continue;
if (is_array($matrix[ $location[$c][$value][0] ][$x])) {
$pos = array_search($value, $matrix[ $location[$c][$value][0] ][$x]);
if ($pos !== false) {
$changed = true;
array_splice($matrix[ $location[$c][$value][0] ][$x], $pos, 1);
print "({$location[$c][$value][0]}, $x) is not $value because the $value in that row is in either ({$location[$c][$value][0]}, $c) or ({$location[$c][$value][0]}, $cc)<br />";
}
}
}
for ($x = 1; $x < 10; $x++) {
if ($x == $c || $x == $cc) continue;
if (is_array($matrix[ $location[$c][$value][1] ][$x])) {
$pos = array_search($value, $matrix[ $location[$c][$value][1] ][$x]);
if ($pos !== false) {
$changed = true;
array_splice($matrix[ $location[$c][$value][1] ][$x], $pos, 1);
print "({$location[$c][$value][1]}, $x) is not $value because the $value in that row is in either ({$location[$c][$value][1]}, $c) or ({$location[$c][$value][1]}, $cc)<br />";
}
}
}
}
}
}
}
}
return $changed;
}
function display() {
global $matrix, $given;
print '<table border="0" cellpadding="0" cellspacing="2">';
for ($r = 1; $r < 10; $r++) {
print '<tr>';
for ($c = 1; $c < 10; $c++) {
// shade and bold the boxes with the givens
$styleextra = ($given[$r][$c] ? ' background-color: #DDDDFF; font-weight: bold;' : '');
// provide extra space so the 3x3 regions are easier to see
$styleextra .= ($r == 4 || $r == 7 ? ' margin-top: 8px;' : '');
$styleextra .= ($c == 4 || $c == 7 ? ' margin-left: 8px;' : '');
