Wednesday, November 14, 2007

PHP Eight queens

Here is recursive algorithm solving the problem with eight queens which don't threaten each other:



function check( $i )
{
global $column, $rows, $left_d, $right_d;
for( $j = 1; $j <= 8; $j++ )
{
// check is the row and both diagonals are free
if( $rows[$j] && $left_d[$i+$j] && $right_d[$i-$j] )
{
$column[$i] = $j;//put the qeen on the $i column in the $j position

//set row and diagonals to occupied
$rows[$j] = false;
$left_d[$i+$j] = false;
$right_d[$i-$j] = false;

// if $i == last column(8) we print the results
if( $i < 8 )
check( $i + 1 );
else
print_results();

//unset row and diagonals
$rows[$j] = true;
$left_d[$i+$j] = true;
$right_d[$i-$j] = true;
}
}
}

function print_results()
{
global $column;
foreach( $column as $value )
echo $value ."&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;";

echo "<br />\n";
}

for( $i = 1; $i <= 8; $i++ )
$rows[$i] = true;

for( $i = 2; $i <= 16; $i++ )
$left_d[$i] = true;


for( $i = -7; $i <= 7; $i++ )
$right_d[$i] = true;

check(1);

No comments: