[Kekke]

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.

<?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 />";
}

?>