ExPzNQueen - デカルト言語 - 並列ロジック プログラミング言語 Wiki - デカルト言語 - 並列ロジック プログラミング言語

←　前のページに戻る

8Queen

チェスのQueenは、縦横ななめ、どの方向にもまっすぐに進んでいけるオールマイティな至高な存在です。

そのような誇り高きQueenを、8x8のチェス盤に8人置いて、かつ互いに進んでいける進路上で干渉しないように配置するのが 古来よりある8Queenパズルであります。

上のチェス盤に置いてある8つのQueenで確かめてみてください。 お互いの利き筋が重複していないことが確認できるはずです。

このような、Queenの配置を解決するプログラムをデカルト言語で解いてみましょう。 プログラムのソースを以下に示します。

<qprint #N>
        <for (#i #N)
                <for (#j #N)
                  (<q #j #i> <printf "Q "> 
                            | <printf "_ ">)
                >
                <print>
        >
        <print>
        ;

<check #x #y>
        <for (#i #y)
                <q #j #i>
                <compare #j != #x>
                <compare #i-#j != #y-#x>
                <compare #i+#j != #y+#x>
        >
        ;


<nqueen #y #N>
        <compare #y >= #N>
        <qprint #N>
        <print>
        ;

<nqueen #y #N>
        <#y1 = #y + 1>
        <for (#x #N)
                [
                  <check #x #y>
                  <setArray q #x #y>
                  <nqueen #y1 #N>
                ]
        >
        ;


? <nqueen 0 8>;

以下のように考えて解きます。

1) 1行には必ず1つのQueeenしかないので、0行目から順にQueenを0桁目から入れて試す。

2) 新しく設定したQueenが行が縦と斜めの方向で衝突しないかチェックして、衝突していたら次の位置を探す。

3) 最後の行までQueenの位置が決定したら、結果を表示する。

4) 異なる解がないか探索するため1)を別の位置の桁から試す。

5) すべての解を出力したら終了する。

1. qprint述語

まず、最初のqprint述語は、8QUEENの盤面を表示する述語の定義です。

<qprint #N>
        <for (#i #N)
                <for (#j #N)
                  (<q #j #i> <printf "Q "> 
                            | <printf "_ ">)
                >
                <print>
        >
        <print>
        ;

2重のforループですから簡単ですね。

ポイントは、ループの中です。

                      (<q #j #i> <printf "Q "> 
                            | <printf "_ ">)

<q #j #i>によって、配列qのインデックス(#j, #i)に値が設定されていれば、そこにはqueenがいると判断して "Q　"を表示します。 それ以外ならば、空欄として"_ "を表示します。 その処理の切り替えの判定を"|"(論理和)によって選択しています。 "|"の前の処理が成功すれば、その後の処理は実行されません。 失敗すれば、後ろの処理が実行されます。

この処理で２重ループの中で盤面全体をスキャンしながら、結果の表示を行うのです。

2. check述語

次のcheck述語は、引数の(#x,#y)の位置にqueenを置いても他のqueenと衝突しないかチェックするものです。

<check #x #y>
        <for (#i #y)
                <q #j #i>
                <compare #j != #x>
                <compare #i-#j != #y-#x>
                <compare #i+#j != #y+#x>
        >
        ;

最初のfor述語により、0から#y-1までループさせます。 これは、0行目から順にqueenを置いていくため、現在queeenを置く位置を探っている#yより後ろにはqueenはないため、この範囲で十分なのです。

次の<q #j #i>で、#i行目にあるqueenを見つけ出します。

<compare #j != #x>は、見つけ出したqueenが、#xと同じ列にないかをチェックします。 これは、縦方向のチェックに相当します。

斜め方向については、次のように考えます。

チェス盤をｘ、ｙの座標と考えると、斜め方向の方程式は傾きが1および-1の以下のような形になります。

    y =  x + a
    y = -x + b

そこで、同じ斜め方向にあるということは、切片aやｂが一致する場合です。

   a = y - x
   b = y + x

よって、y-xとy+xの値が一致する場合には、斜め方向でqueenが衝突すると判定します。 その判定がcheck述語の中の以下の判定で行われます。

               <compare #i-#j != #y-#x>
             <compare #i+#j != #y+#x>

3. nqueen述語

次のnqueen述語は、2つ定義があります。 これは、最初の定義が成功すれば、それを実行し、 失敗すれば２つ目の定義を実行するように動作します。

<nqueen #y #N>
        <compare #y >= #N>
        <qprint #N>
        <print>
        ;

<nqueen #y #N>
        <#y1 = #y + 1>
        <for (#x #N)
                [
                  <check #x #y>
                  <setArray q #x #y>
                  <nqueen #y1 #N>
                ]
        >
        ;

最初のnqueen定義は、まず、<compare #y >= #N>で引数#yが#Nを超えている場合には解が求められたと判定して 先に説明したqprint述語で結果を表示します。

ちなみに8queenではなく、nqueenなのは、8以外の盤でも解が求められるようにするために、盤の幅を#Nで指定できるようにするためです。

次のnqueenの定義が実際の解を求める処理を再帰的に行っているものです。

check述語で、(#x, #y)にqueenを置いて問題ないかチェックし、 問題なければ組み込み述語のsetArrayで配列qの(#x, #y)のインデックスを設定します。

その後、#yに1を足した座標で、nqueen述語を再帰的に呼び出しています。

4. 実行

最後の行で、nqueen述語を呼び出して、プログラムの実行を行います。

? <nqueen 0 8>;

引数の0は、0行目から開始するということです。

引数の8は、8queenを調べることを指定しています。 たとえば、この値が10になれば、10x10の盤で10個のqueenを配置する解を求めます。

5. 最後に

どうでしょうか？

以外に簡単ですね。デカルト言語は論理言語としての特徴を持つのですが、 手続き的なプログラムも同様に間単に書けます。

つまり、デカルト言語では論理的な処理と手続き的な処理を融合させて 書きやすい方法でプログラムを記述することができるようになっているのです。