Étapes d'implémentation de l'algorithme Eight Queens Problem en PHP

É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

1. Initialiser l'échiquier : créez un tableau bidimensionnel 8x8 comme échiquier et initialisez tous ses éléments à 0, indiquant que la reine n'a pas été placée à la position actuelle.
2. Algorithme de backtracking : en commençant par la première rangée, essayez de placer la reine rangée par rangée. Pour chaque ligne, essayez de placer une reine sur chaque colonne et vérifiez si la condition de ne pas être attaquée est remplie. Si les conditions sont remplies, continuez de manière récursive pour placer la reine dans la rangée suivante. Si les conditions ne sont pas remplies, revenez à la ligne précédente et réessayez dans une autre position.
3. Condition finale : Lorsque toutes les reines sont placées avec succès sur l'échiquier, une solution est obtenue. Le retour en arrière se termine lorsque toutes les lignes ont été essayées sans solution.

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!