Étapes pour implémenter l'algorithme du problème des huit reines en PHP
Introduction :
Le problème des huit reines est un problème célèbre qui afflige le domaine de l'informatique. Il nécessite de placer huit reines sur un échiquier 8x8 afin qu'aucune reine ne puisse interagir avec chacune. autre. Cet article donnera les étapes de l'algorithme pour implémenter le problème des huit reines en PHP et joindra des exemples de code.
1. Analyse du problème
Le problème des Huit Reines peut être considéré comme un problème typique de retour en arrière. Sur un échiquier 8x8, une seule reine peut être placée dans chaque rangée, et les reines de chaque rangée ne peuvent pas être dans la même colonne, rangée ou diagonale que les reines des autres rangées.
2. Étapes de mise en œuvre de l'algorithme
3. Exemple de code PHP
Ce qui suit est un exemple de code qui utilise PHP pour implémenter l'algorithme du problème des huit reines :
<?php class EightQueens { private $board; // 棋盘 private $solutions; // 存放所有解的数组 public function __construct() { $this->board = array_fill(0, 8, array_fill(0, 8, 0)); $this->solutions = array(); } public function solve() { $this->placeQueen(0); return $this->solutions; } private function placeQueen($row) { if ($row == 8) { $this->solutions[] = $this->board; return; } for ($col = 0; $col < 8; $col++) { if ($this->isSafe($row, $col)) { $this->board[$row][$col] = 1; // 放置皇后 // 递归放置下一行的皇后 $this->placeQueen($row + 1); $this->board[$row][$col] = 0; // 回溯 } } } private function isSafe($row, $col) { // 检查当前列是否已有皇后 for ($i = 0; $i < $row; $i++) { if ($this->board[$i][$col] == 1) { return false; } } // 检查左上对角线是否有皇后 $i = $row - 1; $j = $col - 1; while ($i >= 0 && $j >= 0) { if ($this->board[$i][$j] == 1) { return false; } $i--; $j--; } // 检查右上对角线是否有皇后 $i = $row - 1; $j = $col + 1; while ($i >= 0 && $j < 8) { if ($this->board[$i][$j] == 1) { return false; } $i--; $j++; } return true; } } // 使用示例 $eightQueens = new EightQueens(); $solutions = $eightQueens->solve(); foreach ($solutions as $solution) { foreach ($solution as $row) { echo implode(" ", $row) . " "; } echo " "; }
Le code ci-dessus implémente la solution du problème des huit reines via l'algorithme de backtracking. Après avoir exécuté le programme, toutes les solutions qui remplissent les conditions seront affichées. Chaque solution est représentée par un tableau à deux dimensions, où 1 représente la position de la reine.
Conclusion :
Cet article présente les étapes de l'algorithme pour implémenter le problème des huit reines en PHP et joint des exemples de code correspondants. Grâce à cet algorithme, nous pouvons trouver toutes les solutions qui remplissent la condition, c'est-à-dire placer huit dames sur un échiquier 8x8 afin que deux reines ne puissent pas s'attaquer. L'algorithme de backtracking est une méthode courante pour résoudre le problème des huit reines et est également largement utilisé dans d'autres problèmes similaires.
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!