デカルト言語 - 並列ロジック プログラミング言語
edit[ExPuzzle ← 前のページに戻る]
=== 8Queen
チェスのQueenは、縦横ななめ、どの方向にもまっすぐに進んでいけるオールマイティな至高な存在です。
そのような誇り高きQueenを、8x8のチェス盤に8人置いて、かつ互いに進んでいける進路上で干渉しないように配置するのが
古来よりある8Queenパズルであります。
[[Embed(8Q.jpg)]]
上のチェス盤に置いてある8つのQueenで確かめてみてください。
お互いの利き筋が重複していないことが確認できるはずです。
このような、Queenの配置を解決するプログラムをデカルト言語で解いてみましょう。
プログラムのソースを以下に示します。
[[BR]]
{{{
<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) すべての解を出力したら終了する。
[[BR]]
まず、最初のqprint述語は、8QUEENの盤面を表示する述語の定義です。
[[BR]]
{{{
<qprint #N>
<for (#i #N)
<for (#j #N)
(<q #j #i> <printf "Q ">
| <printf "_ ">)
>
<print>
>
<print>
;
}}}
2重のforループですから簡単ですね。
ポイントは、ループの中です。
[[BR]]
{{{
(<q #j #i> <printf "Q ">
| <printf "_ ">)
}}}
<q #j #i>によって、配列qのインデックス(#j, #i)に値が設定されていれば、そこにはqueenがいると判断して
"Q "を表示します。
それ以外ならば、空欄として"_ "を表示します。
その処理の切り替えの判定を"|"(論理和)によって選択しています。
"|"の前の処理が成功すれば、その後の処理は実行されません。
失敗すれば、後ろの処理が実行されます。
この処理で２重ループの中で盤面全体をスキャンしながら、結果の表示を行うのです。
[[BR]]
次のcheck述語は、引数の(#x,#y)の位置にqueenを置いても他のqueenと衝突しないかチェックするものです。
[[BR]]
{{{
<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の以下のような形になります。
[[BR]]
{{{
y = x + a
y = -x + b
}}}
そこで、同じ斜め方向にあるということは、切片aやｂが一致する場合です。
[[BR]]
{{{
a = y - x
b = y + x
}}}
よって、y-xとy+xの値が一致する場合には、斜め方向でqueenが衝突すると判定します。
その判定がcheck述語の中の以下の判定で行われます。
[[BR]]
{{{
<compare #i-#j != #y-#x>
<compare #i+#j != #y+#x>
}}}
つづく