Ich habe mich heute mit dem 8-Damen-Problem beschäftigt. Siehe https://de.wikipedia.org/wiki/Damenproblem
Mein Ergebnis schaut folgendermaßen aus:
Kann man das in PHP noch irgendwie besser programmieren?
Ausgangsbasis war ein Algorithmus aus dem Buch "Algorithmen und Datenstrukturen" vom dpunkt.verlag.
Mein Ergebnis schaut folgendermaßen aus:
PHP-Code:
<?php
error_reporting(~0);
class ChessQueens
{
private $n; // Anzahl Felder in Länge und Breite
private $queens; // Stack für positionierte Damen
private $results; // Sammlung der Endergebnisse
/**
* @param int $n > 0 Anzahl der Felder in der Länge und Breite.
* Ein Schachbrett hat normalerweise 8 Felder in Länge und Breite.
*/
function __construct($n = 8)
{
$this->n = $n;
$this->queens = $this->results = [];
$this->row(0);
}
/**
* Ob es auf diesem Feld noch keine Dame gibt und das Feld von keiner
* Dame bedroht wird.
* @param int $i Zeile
* Anzahl Zeilen > $i >= 0
* @param int $h Spalte
* Anzahl Spalten > $h >= 0
* @return bool
*/
private function isFree($i, $h)
{
foreach($this->queens as $queenI => $queenH)
{
if
(
($dI = $queenI - $i) == 0 || // Kontrolle auf gleiche Zeile
($dH = $queenH - $h) == 0 || // Kontrolle auf gleiche Spalte
abs($dI) == abs($dH) // Kontrolle auf gleiche Diagonale
)
{
return false;
}
}
return true;
}
/**
* In einer Zeile nach einer Position für eine Dame suchen.
* @param int $i Zeile
* Anzahl Zeilen > $i >= 0
*/
private function row($i)
{
for($h = 0; $h < $this->n; ++$h) // Spalten
{
if($this->isFree($i, $h)) // ob Feld unbedroht ist
{
$this->queens[] = $h; // Dame setzen (auf Stack legen)
if($i == $this->n - 1) // ob letzte Zeile
{
// Lösung gefunden. Positionen der Damen speichern.
$this->results[] = $this->queens;
}
else
{
$this->row($i + 1); // rekursiv in die nächste Zeile
}
// Ab hier bewegt man sich im Baum rekursiv rückwärts.
$queen = array_pop($this->queens); // Dame entfernen (von Stack holen)
}
}
}
/**
* Liefert die Positionen der Damen für alle Lösungen.
* @return array mehrdimensionales Array
* [] array eine Lösung
* [][] array die Position einer Dame
* [][] key int Zeile
* [][] value int Spalte
*/
function getResults()
{
return $this->results;
}
}
$chessQueens = new ChessQueens(8);
$results = $chessQueens->getResults();
echo "Anzahl: ",count($results),"<br />",PHP_EOL;
echo "===<br />",PHP_EOL;
foreach($results as $result)
{
foreach($result as $i => $h)
{
echo $i,"/",$h,"<br />",PHP_EOL;
}
echo "---<br />",PHP_EOL;
}
?>
Ausgangsbasis war ein Algorithmus aus dem Buch "Algorithmen und Datenstrukturen" vom dpunkt.verlag.
Kommentar