好きだってほど数を解いてない気がしますけどそれはさておき。
Sugarという制約ソルバーがあります。以下略。前提や使用ツールはしばらく前の記事を参照のこと。
ビルディングパズルのルールや歴史等はwikipedia:ビルディングパズルを参照して下さい。
Sugarに慣れている人はすぐ判断が付くと思いますが、ビルディングパズルのルールを制約に落とすのに、特に難しいことはありません。まあ難しいことは能力のある人がやってくれると思うです。
例題は以下。さきほど適当に作ったんですが、サイズが小さいと先例とぶつかるかもしんないなと危惧してはいます。
さてそれでは、この例題をSugarスクリプトに落とすことを考えます。
盤面の各マスに、以下のように変数を割り当てます。
変数には１から盤面の辺長（例題では４）までの整数が入ります。
Sugarでは以下のように書くことができます。
(int b_00_00 1 4) ...(中略)... (int b_03_03 1 4)
各列に入る数は重複しないという条件は、すべての列についてalldifferentを適用すればいいですね。
(alldifferent b_00_00 b_01_00 b_02_00 b_03_00 ) ...(中略)... (alldifferent b_03_00 b_03_01 b_03_02 b_03_03 )
最後に、あるところから見えるビルの数を記述します。
例として、下図で赤枠で囲われた部分を説明します。
u_0n_0mがなにを表しているかというと、「そのマスのビルは、指定された方向から見えているか否か」です。見えていたら１、見えなければ０を割り当てます。一番手前のマス用にu_03_00を設定してもいいのですが、一番手前のビルは常に見えるので省略します。
定義は以下のようになります。
(int u_03_01 0 1) (int u_03_02 0 1) (int u_03_03 0 1)
次に、あるマスのビルが見えるかどうかを考えます。そのマスより手前のマスに、そのマスのビルより高いビルがひとつでもあれば、そのマスのビルは見えません。そうでなければ見えます。これをSugarスクリプトに記述すると以下のようになるでしょう。
( = u_03_01 (if ( or (> b_03_00 b_03_01) ) 0 1 ) ) ( = u_03_02 (if ( or (> b_03_00 b_03_02) (> b_03_01 b_03_02) ) 0 1 ) ) ( = u_03_03 (if ( or (> b_03_00 b_03_03) (> b_03_01 b_03_03) (> b_03_02 b_03_03) ) 0 1 ) )
これらの変数の合計が、その方向から見えるビルの数になります。一番手前のビルは常に見えているのでこれを省略したため、合計は２から１を引いた１になります。
( = 1 ( + u_03_01 u_03_02 u_03_03 ) )
数字が表出されているすべての方向について、この記述を行えばスクリプトは完成です。私の環境では６ｘ６の問題が数10秒で解けました。めでたい。
ということで今回はここまで。
