8 queens (problema de las 8 reinas php)

Aqui les dejo un problema de backtracking para aquellos entusiastas de la programación, se trata de un problema clásico que consiste en ordenar 8 reinas en un tablero de ajedrez de manera que no coincidan lineal o diagonalmente. El algoritmo busca todas las soluciones posibles y se puede parametrizar para diferentes tipos de tablero. Debe ser probado con un N<=25 para no elevear drásticamente el coste computacional.

<>
<>
<>
< ?php

/*************************************************************************
*
* This algorithm solves the 8 queens problem using backtracking.
* Please try with N<=25 * * * *************************************************************************/ class Queens { var $size; var $arr; var $sol; function Queens($n = 8) { $this->size = $n;
$this->arr = array();
$this->sol = 0;
// Inicialiate array;
for($i=0; $i<$n; $i++) { $this->arr[$i] = 0;
}
}

function isSolution($n) {
for ($i = 0; $i < $n; $i++) { if ($this->arr[$i] == $this->arr[$n] ||
($this->arr[$i] - $this->arr[$n]) == ($n - $i) ||
($this->arr[$n] - $this->arr[$i]) == ($n - $i)) return false;
}
return true;
}

function PrintQueens() {
echo("solution #".(++$this->sol)."\n");
for ($i = 0; $i < $this->size; $i++) {
for ($j = 0; $j < $this->size; $j++) {
if ($this->arr[$i] == $j) echo("& ");
else echo(". ");
}
echo("\n");
}
echo("\n");
}


// backtracking Algorithm
function run($n = 0) {
if ($n == $this->size) $this->PrintQueens();
else {
for ($i = 0; $i < $this->size; $i++) {
$this->arr[$n] = $i;
if ($this->isSolution($n)) $this->run($n+1);
}
}
}

}

$myprogram = new Queens(8);
$myprogram->run();

? >
< /pre>
< /body>
< /html>