PHP での Eight Queens 問題アルゴリズムの実装手順

PHP で 8 クイーン問題アルゴリズムを実装する手順

はじめに:
8 クイーン問題は、コンピューター サイエンスの分野を悩ませる有名な問題であり、8x8 のチェス盤上に 8 つのクイーンを配置する必要があります。 2人の女王が互いに攻撃できないようにするためです。この記事では、PHP でエイト クイーン問題を実装するアルゴリズムの手順を示し、コード例を添付します。

1. 問題分析
Eight Queens 問題は、典型的なバックトラッキング問題とみなすことができます。 8x8 のチェス盤では、各行に配置できるクイーンは 1 つだけであり、各行のクイーンは他の行のクイーンと同じ列、行、または対角に配置することはできません。

2. アルゴリズムの実装手順

1. チェス盤の初期化: 8x8 の 2 次元配列をチェス盤として作成し、そのすべての要素を 0 に初期化し、クイーンがまだ決定されていないことを示します。現在の位置に配置されます。
2. バックトラッキング アルゴリズム: 最初の行から始めて、クイーンを行ごとに配置してみます。各行について、各列にクイーンを配置して、攻撃されない条件が満たされているかどうかを確認してください。条件が満たされた場合は、再帰的にクイーンを次の行に配置します。条件が満たされない場合は、前の行に戻り、別の位置で再試行します。
3. 終了条件: すべてのクイーンがチェス盤に正常に配置されると、解決策が得られます。すべての行を試行しても解決策が見つからない場合、バックトラッキングは終了します。

3. PHP コード例
次は、PHP を使用してエイト クイーン問題アルゴリズムを実装するコード例です:

<?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 "
";
}

上記のコードは、エイト クイーン問題の解決策を実装します。バックトラッキング アルゴリズムによるクイーンズ問題。プログラムを実行すると、条件を満たすすべての解が出力され、各解はクイーンの位置を 1 とした 2 次元配列で表現されます。

結論:
この記事では、PHP でエイト クイーン問題を実装するアルゴリズムの手順を紹介し、対応するコード例を添付します。このアルゴリズムを通じて、条件を満たすすべての解を見つけることができます。つまり、2 つのクイーンが互いに攻撃できないように 8 x 8 のチェス盤に 8 つのクイーンを配置します。バックトラッキング アルゴリズムは、エイト クイーン問題を解決するための一般的な方法であり、他の同様の問題でも広く使用されています。

以上がPHP での Eight Queens 問題アルゴリズムの実装手順の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。