4. 運用実績

史上最も詳細な 8 クイーンズ アルゴリズムの分析 [php 版]

タイトル:

8 クイーンズ問題 は、チェス の背景に基づいた質問です。どのクイーンも他のクイーンを直接食べることができないように、8 × 8 のチェス盤上に 8 つのクイーン を配置する方法。これを達成するには、2 つのクイーンを同じ水平列、垂直列、または対角線上に置くことはできません。

1. 質問分析:

配置できる各ポジションは、要件 要件:

1) 行が配置されていません。

2) 列が配置されていません。 >

3) 左上から右下への斜線が配置されていません。

4) 右上から左下への斜線。は置かれていない。

2. 数学的モデリング

1) 座標系 を確立します。

2) 配置座標が (a, b) であると仮定すると、 は次の数学的条件を満たす必要があります。関係。

1. 行 row[a]=1 (行 a が配置されていないことを意味し、0 は行 a が配置されていないことを意味します)行 a が配置されていることを示します)。 b]=1 (列 b が配置されていないことを意味し、0 は列 b が配置されたことを意味します); >

対角線を計算する必要があります:

(a, b)、

3. 左上から右下への対角線 (主対角として設定) の傾きは -1 です:

すると、(y-b)/(x-a)=-1 となり、次の関係が得られます。

y+x= a+b。

したがって、a+b を使用して (a, b) の主対角をマークできます。a+b の範囲は [2] です。 , 16]、つまり、2 ～ 16 の数字を使用して、(1,1) から (8,8) までの 15 個の対角線をマークします。 >4.
右上から左下への対角線(下対角線として設定)の傾きは1:

すると、(y-b)/(x-a)=1 となり、次の関係が得られます: x-y=a-b;

したがって、a-b は (a, b) の下対角をマークするために使用できます。a-b の範囲は [-7,7] です。

3) 配置プロセス

1 行目から 8 行目まで、各行に 1 つずつ配置すると、2 番目のステップの最初の条件は無視できます (確かに異なる行)。

以下は、バックトラッキング方法の例である仮想の配置ステップです:

Q * * * * * * *
* * Q * * * * *
* * * * Q * * *
* Q * * * * * *
* * * * * * * Q
* * * * * * * *
* * * * * * * *
* * * * * * * *

1行目の(1,1)から開始し、2行目は(2,3)に配置されているとします。 ) 4行目(4,2)、5行目(5,8)このとき5行目に条件を満たす座標が見つからないことが分かります。最後に 4 行目に到達すると、選択できる位置がなくなり、3 行目に戻り、一致する 3 行目で (4,7) を見つける必要があります。条件を確認し、8 行目まで下向きに配置するプロセスを開始し、配置できる 8 つを見つけます。配置は解決策です。

3. プログラムの実装

注: プログラムを容易にするために、配列ペア 対角線 の注釈は、i 行目、j 列目の座標に対するもので、変更された座標の主対角線は $this->rup[$i+$j]=1 です。対角部分が占有されていないことを意味します。下対角は $this->lup[$i-$j+8]=1 (配列の添え字は負であってはならず、$i-$j は可能です)これは、対角線 が占有されていないことを意味し、$this->column[$j]=1 となり、列が占有されていないことを示します。

コードは次のとおりです:

4. 実行結果

<?php/*** function：解决八个皇后的问题* author：xiaojun* date：2015-5-16*/class Queen {    private  $column= array();//存放列是否占有标记，0为占有    private  $rup= array();//存放主对角线是否占有，0为占有    private  $lup= array();//存放次对角线是否占有，0为占有    private  $queen= array();//存放解中皇后的位置    private  $num;  //解的编号    function __construct() {        for($i=1;$i<=8;$i++){            $this->column[$i]=1;        }        for($i=1;$i<=(2*8);$i++)        $this->rup[$i]=$this->lup[$i]=1;    }    public function backtrack($i){//i从上往下        if($i>8){            $this->showAnswer();        }else{        for($j=1;$j<=8;$j++){            //从左往右横向                       if(($this->column[$j]==1)&&($this->rup[$i+$j]==1)&&($this->lup[$i-$j+8]==1)){                         $this->queen[$i]=$j;                //设定为占用                $this->column[$j]=$this->rup[$i+$j]=$this->lup[$i-$j+8]=0;                $this->backtrack($i+1);                $this->column[$j]=$this->rup[$i+$j]=$this->lup[$i-$j+8]=1;            }          }       }    }         protected function showAnswer(){        $this->num++;        print("解答");        print($this->num);        echo "<br>";        for($y=1;$y<=8;$y++){            for($x=1;$x<=8;$x++){                if($this->queen[$y]==$x){                    print("Q");                }else{                    print(" * ");                }            }            print("<br>");         }        print("<br>");     }}$queen=new Queen();$queen->backtrack(1);?>

.....

....................