カーブデータというパズルがあります。
山本達也さんが考案したもので、シンプルで独特なルールが特徴的な魅力を放っています。と、個人的には思っています。
最近では、全日本パズル選手権2013で出題されたのが記憶に新しいですね。大会の主催窓口に確認を取りましたので、以下にルールと例題を引用します。
【ルール】
・全てのマスを図形で埋める。2つ以上の図形が1つのマスを共有することはない。
・全ての図形は、盤面にあらかじめある記号の上を通る。
・記号は、その上を通る図形がどのように曲がったり分岐したりするかを表す。(長さは、記号のとおりとは限らない)
どんなパズルかご理解いただけましたでしょうか。
今回の記事では、Sugar制約ソルバーを用いてカーブデータを解いてみたいと思います。
盤面に以下のように番号を振ります。この数値を座標として使用します。
各記号の交差点、端点に以下のように名前を付けます。
交差点、端点をまとめて『変化点』と呼ぶことにします。変化点に付けた名前をSugarの変数とし、これとその座標を同じ名前で呼びます。条件を満たした状態での、この変化点の座標をSugarに探してもらうことになります。
また、変化点どうしが線分で直接結ばれている場合、その線分を辺と呼びます。p11とp12を結ぶ辺を『辺p11-p12』と呼びます。
辺と呼んだ時、両端の変化点が含まれるかどうかは、はっきりしないと得てして問題が生じたりしますが、今回は面倒なのでてきとうに書くので、各自適宜補ってください。あと、みなさんはこんな大人になっちゃダメですよ。
まずはいつものように、変化点の定義を行います。
; 各変化点の定義 ( int p11 0 15 ) ; (中略) ( int p34 0 15 ) (alldifferent p11 p12 p13 p14 p21 p22 p23 p24 p31 p32 p33 p34 )
続いて、各辺の記述を行います。
縦方向の辺、例えば辺p11-p12に関しては以下のように書きました。
(= (% p11 4) (% p12 4) ) (< p11 p12)
p11とp12のx座標が等しく、p11のy座標がp12のy座標より上に来る、ということを書いています。4は盤面の横サイズですね。
次は横方向の辺、例えば辺p12-p14に関しては以下のように書きました。
(= (/ p12 4) (/ p14 4) ) (< p12 p14)
p12とp14のy座標が等しく、p11のx座標がp12のx座標より左に来る、ということを書いています。
この記述をすべての辺について行います。
この時点で、Sugarに動いてもらいましょう。例えば以下のようになります。(これは説明用に作ったもので、実際にこの解が出力されたというわけではありません)
p11 = 2 p12 = 6 p13 = 14 p14 = 7 p21 = 8 p22 = 1 p23 = 9 p24 = 3 p31 = 10 p32 = 12 p33 = 11 p34 = 15
わかりにくいので画像に展開してみます。
図形の形だけは満たした解になっていますね。
では次に、「図形どうしが重ならない」という条件を追加します。次の2ステップに分けて記述します。
1.辺上に(他の)変化点が乗らない。
2.辺どうしが(十字に)交差しない。
この2条件で、重ならないことは表現できていますよね。
辺上に(他の)変化点が乗らないということを記述します。まずは縦方向の辺。辺p11-p12にp31が乗らない、ということを以下のように表現しました。
(|| ( < p31 p11 ) ( < p12 p31 ) ( != (% p31 4) (% p11 4) ) )
次は横方向の辺です。辺p12-p14にp31が乗らない、ということを以下のように表現しました。
(|| ( < p31 p12 ) ( < p14 p31 ) )
この記述を各辺、各変化点すべてについて行います。位置関係によってはすぐに削れる条件もあるでしょうが、計算量を考えなければ単に無駄な記述になるだけなので、まあすべてでカンベンしてください。
次に、辺が十字にならないということを記述します。十字になる、ということを記述して、それを否定しています。
辺p11-p12、辺p32-34が十字にならないという記述です。
(! (&& ( < (/ p11 4) (/ p32 4) ) ( < (/ p32 4) (/ p12 4) ) ( < (% p32 4) (% p11 4) ) ( < (% p11 4) (% p34 4) ) ) )
この記述を各縦方向辺、横方向辺の組み合わせすべてについて行います。
この時点で、Sugarに動いてもらいましょう。解答は略して画像に展開したものを示します。例えば以下のようになります。
だんだん欲しい解に近づいてきました。
さて最後に、すべてのマスがいずれかの図形に含まれ、また、図形が表出されているマスはその図形を含む、を記述します。
すべてのマスがいずれかの図形に含まれるというのは、すべてのマスがいずれかの辺に含まれるということです。「座標9」のマスの例を以下に示します。
;; 9 (|| ( && (= 1 (% p11 4)) (<= (/ p11 4) 2) (<= 2 (/ p12 4) ) ) ( && (= 1 (% p12 4)) (<= (/ p12 4) 2) (<= 2 (/ p13 4) ) ) ( && (= 1 (% p22 4)) (<= (/ p22 4) 2) (<= 2 (/ p23 4) ) ) ( && (= 1 (% p33 4)) (<= (/ p33 4) 2) (<= 2 (/ p34 4) ) ) ( && (<= p12 9) (<= 9 p14 ) ) ( && (<= p21 9) (<= 9 p23 ) ) ( && (<= p22 9) (<= 9 p24 ) ) ( && (<= p31 9) (<= 9 p33 ) ) ( && (<= p32 9) (<= 9 p34 ) ) )
「;; 9」はコメントです。
1行目は辺p11-p12についての記述です。9のx座標が1、y座標が2なので、これは直接記述しています。もしこれを計算せずに書けば以下のようになるでしょうか。
( && (= (% 9 4) (% p11 4)) (<= (/ p11 4) (/ 9 4 ) ) (<= (/ 9 4 ) (/ p12 4) ) )
5行目以降は横方向辺です。これは見やすいですね。
さて最後に、図形が表出されているマスはその図形を含む、を記述しますが、これは簡単です。例えば13のマスは、p21,p22,p23,p24で構成される図形に含まれますから、これらの変化点で構成される辺だけに含まれる記述になるよう、上の条件を変更すればよろしい。以下のようになります。
;; 13 (|| ( && (= 1 (% p22 4)) (<= (/ p22 4) 3) (<= 3 (/ p23 4) ) ) ( && (<= p21 13) (<= 13 p23 ) ) ( && (<= p22 13) (<= 13 p24 ) ) )
これですべての条件が記述できたはずです。めでたい。
別解チェックが必要な場合は、解を否定する条件を追加してもうもう一度走らせてくださいということで。
自己流の問題ファイル形式と、それを使用して半自動でsugarスクリプトを作成するawkスクリプトも組んでありますが、それはまたの機会ということで。