Sudoku solver i php
Hade tråkigt och gjorde en sudoku-lösare i php, tänkte att någon kanske kan lära sig något ifrån koden?
Den kommer bara fungera på lättare sudokus, det kommer behövas ytterligare kollar om det ska fungera på svårare.
Koden är snabbt ihopskriven så kan va lite saker man kan ändra på för att få den att gå snabbare.
http://fuskbugg.se/file/Adb4T5/sudd.png
Kod:
<?php
function in_multiarray($elem, $array)
{
$top = sizeof($array) - 1;
$bottom = 0;
while($bottom <= $top)
{
if($array[$bottom] == $elem)
return true;
else
if(is_array($array[$bottom]))
if(in_multiarray($elem, ($array[$bottom])))
return true;
$bottom++;
}
return false;
}
$sudoku = array(
array(1, 5, 0, 0, 0, 9, 0, 0, 0),
array(0, 4, 0, 2, 0, 1, 0, 3, 5),
array(3, 0, 8, 0, 6, 5, 0, 2, 0),
array(0, 8, 6, 3, 0, 0, 0, 0, 0),
array(0, 0, 3, 9, 0, 6, 7, 0, 0),
array(0, 0, 0, 0, 0, 2, 4, 6, 0),
array(0, 6, 0, 1, 9, 0, 5, 0, 7),
array(9, 1, 0, 5, 0, 8, 0, 4, 0),
array(0, 0, 0, 6, 0, 0, 0, 1, 9
) );
//Skriv ut sudokun innan vi försöker lösa den
echo "INNAN:<br />";
foreach($sudoku as $inner)
{
foreach($inner as $val)
{
if($val == 0)
{
echo "<div style=\"border: 1px solid; float: left; width: 15px; height: 18px; background-color: red;\">" . $val . "</div>";
}
else
echo "<div style=\"border: 1px solid; float: left; width: 15px; height: 18px;\">" . $val . "</div>";
}
echo "<br />";
}
//Alla möjliga siffror
$posN = array(1, 2, 3, 4, 5, 6, 7, 8, 9);
//Så länge vi har en 0'a försöker vi lösa den
while(in_multiarray(0, $sudoku)) {
$foundVal = 0;
for($v = 0; $v < 9; $v++)
{
for($h = 0; $h < 9; $h++)
{
//Kolla alla rutor
if($sudoku[$v][$h] == 0)
{
//Om rutan är tom (= 0)
for($iNum = 1; $iNum < 10; $iNum++)
{
//Kolla om 1-9 finns i rutan
for($i = 0; $i < 9; $i++)
{
if($sudoku[$v][$i] == $iNum)
$posN[$iNum-1] = 0;
if($sudoku[$i][$h] == $iNum)
$posN[$iNum-1] = 0;
}
//Kolla 3x3-rutan det tomma värdet ligger i
checkBox($v, $h, $iNum);
}
//Ta bort alla 0'or
while(($key = array_search(0, $posN)) !== false) {
unset($posN[$key]);
}
//Finns de bara 1 värde i arrayen så finns det bara 1 möjlig siffra på platsen
if(sizeof($posN) == 1)
{
foreach($posN as $val)
{
$onlyVal = $val;
}
//Bara 1 möjlig siffra
$sudoku[$v][$h] = $onlyVal;
$foundVal = 1;
}
}
//Återställ arrayen
$posN = array(1, 2, 3, 4, 5, 6, 7, 8, 9);
}
}
//Hittar vi inget värde sitter vi fast och får ge upp
if($foundVal == 0)
break;
}
function checkBox($vert, $hor, $number, $d = false)
{
global $sudoku;
global $posN;
if($hor >= 0 && $hor <= 2)
{
$h = 0;
//rad 1 av 3
if($vert >= 0 && $vert <= 2)
{
$v = 0;
}
if($vert >= 3 && $vert <= 5)
{
$v = 3;
}
if($vert >= 6 && $vert <= 8)
{
$v = 6;
}
}
if($hor >= 3 && $hor <= 5)
{
$h = 3;
//rad 1 av 3
if($vert >= 0 && $vert <= 2)
{
$v = 0;
}
if($vert >= 3 && $vert <= 5)
{
$v = 3;
}
if($vert >= 6 && $vert <= 8)
{
$v = 6;
}
}
if($hor >= 6)
{
$h = 6;
//rad 1 av 3
if($vert >= 0 && $vert <= 2)
{
$v = 0;
}
if($vert >= 3 && $vert <= 5)
{
$v = 3;
}
if($vert >= 6 && $vert <= 8)
{
$v = 6;
}
}
$tmpH = $h;
$maxV = $v + 3;
$maxH = $h + 3;
for(; $v < $maxV; $v++)
{
for(; $h < $maxH; $h++)
{
//Kolla boxen (de 9 siffror i 3x3-rutan)
if($sudoku[$v][$h] == $number)
{
$posN[$number-1] = 0;
}
}
$h = $tmpH;
}
}
foreach($sudoku as $inner)
{
foreach($inner as $val)
{
if($val == 0)
{
echo "<div style=\"border: 1px solid; float: left; width: 15px; height: 18px; background-color: red;\">" . $val . "</div>";
}
else
echo "<div style=\"border: 1px solid; float: left; width: 15px; height: 18px;\">" . $val . "</div>";
}
echo "<br />";
}
?>
|
