ましゅパズルをSugar制約ソルバーで解く


はじめに

Nikoliによる 「ましゅ」(Masyu)パズルを Sugar制約ソルバー (A SAT-based Constraint Solver)で解いてみます.

例題

Nikoliによる ましゅの例題 です.
例題
           
              
            
           
             
          
             
          
             
             

ましゅのルール

Nikoliによる「ましゅ」のルールは以下の通りです.
(Rule 1)
盤面に線を引き,全体で1つの輪っかを作ります. 輪っかを作る線はタテヨコにマスの中央を通り,1マスに1本だけ通過できます. 線をワクの外に出したり,交差や枝分かれさせてはいけません.
(Rule 2)
白丸・黒丸があるマスは必ず線が通ります.
(Rule 3)
白丸を通る線は,白丸のマスで必ず直進し, 白丸の両隣のマスの少なくとも片方で直角に曲がります.
(Rule 4)
黒丸を通る線は,黒丸のマスで必ず直角に曲がりますが, 黒丸の隣のマスで曲がってはいけません.
「ましゅ」を 制約充足問題(CSP, Constraint Satisfaction Problem)として表すための 方法について考えていきます.

なお,以下ではパズルの盤面の一番上の行を第0行, 一番左の列を第0列として数えます.

Rule 1とRule 2

(Rule 1)
盤面に線を引き,全体で1つの輪っかを作ります. 輪っかを作る線はタテヨコにマスの中央を通り,1マスに1本だけ通過できます. 線をワクの外に出したり,交差や枝分かれさせてはいけません.
(Rule 2)
白丸・黒丸があるマスは必ず線が通ります.
実は,このRule 1が一番難物です. 「全体で1つの輪っか」という条件は後回しにして, 複数の輪っかでも良いことにして話を進めます. 次にマス(節点)とその隣のマス(節点)を結ぶ辺(edge)に変数を割り当てます. これらの辺を表す変数は,辺を結ぶか結ばないかだけを表すのであれば, 0か1の値を取れば良いのですが,後述の処理のため, 辺の向きを含めて表現できるようにし,-1か0か1の値を取ることにします.

たとえば,左上の節点から下への辺v_0_0および 右への辺h_0_0の宣言は以下のようになります.

    (int v_0_0 -1 1)
    (int h_0_0 -1 1)
他の辺を表す変数についても同様に宣言します.

変数v_i_j (あるいはh_i_j)が1の場合, 対応する辺が下向き (あるいは右向き)であることを表し, -1の場合,対応する辺が上向き (あるいは左向き)であることを表すものとします.

線は交差や枝分かれができません. これは,すべての節点において, 結ばれている辺の個数(次数,degree)が0または2になるという条件で表すことができます. また,Rule 2より,白丸や黒丸のある節点の次数は2になります.

そのため,まず0または2のみを値とするドメインdegreeを宣言します.

    (domain degree (0 2))  ; degree = { 0, 2 }
次に,各節点n_i_jに対し, その節点の次数を表す変数d_i_jを用意します. たとえば,節点n_2_2については白マスなので,以下のように宣言します.
    (int d_2_2 degree)  ; d_1_2 ∈ degree
また,節点n_2_3は黒丸があり,次数は必ず2になるため, 以下のように宣言します.
    (int d_2_3 2 2)
また,節点n_0_1については白マスなので,以下のように宣言します.
    (int d_0_1 degree)  ; d_1_2 ∈ degree
他の節点についても同様に宣言します.

節点n_2_3を一方の端点とする辺は, v_1_3, h_2_2, v_2_3, h_2_3の4つですから, 節点n_2_3の次数は以下のようにして計算できます.

    (= d_2_3 (+ (abs v_1_3) (abs h_2_2) (abs v_2_3) (abs h_2_3)))
他の節点についても同様に次数の条件を追加します.

次に,辺の向きについての条件を追加します. すなわち,できた輪っかの辺の向きがそろっているようにします. この条件は,各節点について,入ってくる辺の数と出て行く辺の数が一致することで 表現できます. たとえば,節点n_2_3についての条件は以下のようになります.

    (= (+ v_1_3 h_2_2 (neg v_2_3) (neg h_2_3)) 0)
他の節点についても同様の条件を追加します.

Rule 3とRule 4

(Rule 3)
白丸を通る線は,白丸のマスで必ず直進し, 白丸の両隣のマスの少なくとも片方で直角に曲がります.
(Rule 4)
黒丸を通る線は,黒丸のマスで必ず直角に曲がりますが, 黒丸の隣のマスで曲がってはいけません.
このRuleを表現するために,各マスで線が直進しているか曲がっているかを 表すブール変数を用意します. たとえば,節点n_2_3に対して,以下のように宣言します.
    (bool s_2_3)
他の節点についても同様に宣言します.

節点n_2_3について, 辺v_1_3と辺v_2_3が結ばれているか,あるいは 辺h_2_2と辺h_2_3が結ばれている時, この節点上で線が直進していますから, 以下の条件を追加します.

    (iff s_2_3 (or (and (!= v_1_3 0) (!= v_2_3 0)) (and (!= h_2_2 0) (!= h_2_3 0))))
他の節点についても同様に宣言します. ただし,垂直方向か水平方向かどちらかしか存在しない場合は, その方向についての条件だけを記述し, どちらの方向も存在しない場合(角の場合)は,対応するブール変数は偽となります. たとえば,節点n_0_8, n_0_9についての条件は以下のようになります.
    (iff s_0_8 (and (!= h_0_7 0) (!= h_0_8 0)))
    (iff s_0_9 false)
次に,白丸の条件について記述します. たとえば,節点n_6_4は白丸ですので, s_6_4は真となります. また,辺v_6_4が結ばれている(したがってv_6_3も結ばれている)場合, 上の節点n_5_4か下の節点n_7_4で, 線が曲がっている必要があります. さらに,辺h_6_4が結ばれている(したがってh_6_3も結ばれている)場合, 左の節点n_6_3か右の節点n_6_5で, 線が曲がっている必要があります. これらは,以下の条件で記述できます (=>は論理記号の「ならば」を表します).
    s_6_4  ; s_6_4 は真
    (=> (!= v_6_4 0) (or (not s_5_4) (not s_7_4)))
    (=> (!= h_6_4 0) (or (not s_6_3) (not s_6_5)))
他の白丸の節点についても同様に制約条件を追加します.

次に,黒丸の条件について記述します. たとえば,節点n_2_3は黒丸ですので, s_2_3は偽となります. また,辺v_1_3が結ばれている場合, 上の節点n_1_3では直線である必要があります. 同様に,回りの他の辺が結ばれている場合, 対応する節点で直線である必要があります. これらは,以下の条件で記述できます

    (not s_2_3)
    (=> (!= v_1_3 0) s_1_3)
    (=> (!= v_2_3 0) s_3_3)
    (=> (!= h_2_2 0) s_2_2)
    (=> (!= h_2_3 0) s_2_4)
他の白丸の節点についても同様に制約条件を追加します.

Rule 1 再び

(Rule 1)
盤面に線を引き,全体で1つの輪っかを作ります. 輪っかを作る線はタテヨコにマスの中央を通り,1マスに1本だけ通過できます. 線をワクの外に出したり,交差や枝分かれさせてはいけません.
ここまでで,「全体で1つの輪っか」という条件を除いて, 他の条件はすべて表現されています(辺の向きの条件も除いて良い).

ここまでは比較的簡単でしたが,「全体で1つの輪っか」という条件はかなり面倒です. 一つの方法は, できあがったグラフが連結(connected)であるという条件を追加することですが, 辺の個数の二乗に比例する制約条件が必要なように思われます. それだと,少し大きなパズルに対しては,制約条件の個数が膨大になり, 高速な制約ソルバーであるSugarでも解くことができません.

そこで,少し工夫をして, 以下のように辺の個数に比例する制約条件で表す方法を考えてみました. これより良い方法もあるかも知れません. ご存知の方は,著者までお知らせいただけましたら幸いです.

これまでの条件だと,複数の輪っかが存在する可能性があります. そこで,各輪っかについて,節点に1から順に番号を付けることにします. 番号は辺の向きにしたがって付けていきます. たとえば,二つの輪っかがある場合,以下のように各節点に番号を付けるのです.

1 2 3
6 5 4
3 2
4 1

左側の輪っかは左上の節点から順に辺の向きに番号が付けられており, 右側の輪っかは右下の節点から順に辺の向きに番号が付けられています.

このように節点に番号を付けることができれば, 「1の番号の付いた節点(始節点)がちょうど1つ」という条件により,輪っかを一つにできます.

「始節点がちょうど1つ」という条件は, 各節点について,その番号が1なら1の値を取り,それ以外の場合0の値を取る変数を用意し, すべての節点についてのそれらの合計が1に等しくなることで表現できます.

そこで,まず以下の変数を用意します.

たとえば,節点n_1_2について,以下の宣言を加えます.
    (int x_1_2 0 100)
    (int y_1_2 0 1)
さらに, 次数d_1_2が正の時だけx_1_2が正になるという条件と, x_1_2が1に等しい時だけy_1_2が1に等しくなるという条件を 加えます.
    (iff (> d_1_2 0) (> x_1_2 0))
    (iff (= x_1_2 1) (= y_1_2 1))
他の節点についても同様にします.

次に,すべてのy_i_jの和が1に等しいという条件を加え, 「始節点がちょうど1つ」すなわち「全体で1つの輪っか」という条件を表します.

    (= (+ y_0_0 y_0_1 ... y_9_9) 1)
最後は,つながっている辺への番号付けのための条件です.

たとえば,節点n_1_2から出る辺について考えます. v_0_2が負ならば, 節点n_1_2からn_0_2への辺があるので, 節点の番号x_0_2は,普通はx_1_2よりも一つ大きくなります. あるいは,節点n_0_2が始節点の場合もありえます. その場合x_0_2は1となります.

これを制約条件として書くと次のようになります (=>は論理記号の「ならば」を表します).

    (=> (< v_0_2 0) (or (> x_0_2 x_1_2) (= x_0_2 1)))
条件(> x_0_2 x_1_2)は, (= x_0_2 (+ x_1_2 1))のほうが上の説明に合致するのですが, 節点につける番号は必ずしも1ずつ増えなくても良いので, 単に大きいという条件で記述しています (このほうがSugar制約ソルバーに優しい(?)記述となるためです).

節点n_1_2から出る他の三つの辺についての制約条件を書くと 以下のようになります.

    (=> (< h_1_1 0) (or (> x_1_1 x_1_2) (= x_1_1 1)))
    (=> (> v_1_2 0) (or (> x_2_2 x_1_2) (= x_2_2 1)))
    (=> (> h_1_2 0) (or (> x_1_3 x_1_2) (= x_1_3 1)))
他の節点についても同様に記述します.

実行結果

すべての制約を記述したファイルを作成し, Sugarで実行すると以下のような結果が得られます.
s SATISFIABLE
a v_0_0	1
a h_0_0	-1
a v_0_1	0
a h_0_1	-1
a v_0_2	0
a h_0_2	-1
a v_0_3	-1
a h_0_3	0
a v_0_4	1
a h_0_4	-1
a v_0_5	0
a h_0_5	-1
a v_0_6	0
a h_0_6	-1
a v_0_7	-1
a h_0_7	0
a v_0_8	0
a h_0_8	0
a v_0_9	0
a v_1_0	1
a h_1_0	0
a v_1_1	0
a h_1_1	0
a v_1_2	0
a h_1_2	0
a v_1_3	-1
a h_1_3	0
a v_1_4	1
a h_1_4	0
a v_1_5	0
a h_1_5	0
a v_1_6	0
a h_1_6	0
a v_1_7	-1
a h_1_7	0
a v_1_8	0
a h_1_8	0
a v_1_9	0
a v_2_0	1
a h_2_0	0
a v_2_1	-1
a h_2_1	1
a v_2_2	0
a h_2_2	1
a v_2_3	0
a h_2_3	0
a v_2_4	0
a h_2_4	1
a v_2_5	0
a h_2_5	1
a v_2_6	1
a h_2_6	0
a v_2_7	-1
a h_2_7	0
a v_2_8	1
a h_2_8	-1
a v_2_9	-1
a v_3_0	1
a h_3_0	0
a v_3_1	0
a h_3_1	-1
a v_3_2	0
a h_3_2	-1
a v_3_3	-1
a h_3_3	0
a v_3_4	1
a h_3_4	-1
a v_3_5	0
a h_3_5	-1
a v_3_6	0
a h_3_6	0
a v_3_7	-1
a h_3_7	0
a v_3_8	1
a h_3_8	0
a v_3_9	-1
a v_4_0	1
a h_4_0	0
a v_4_1	0
a h_4_1	0
a v_4_2	0
a h_4_2	0
a v_4_3	-1
a h_4_3	0
a v_4_4	1
a h_4_4	0
a v_4_5	-1
a h_4_5	1
a v_4_6	0
a h_4_6	1
a v_4_7	0
a h_4_7	0
a v_4_8	1
a h_4_8	0
a v_4_9	-1
a v_5_0	1
a h_5_0	0
a v_5_1	-1
a h_5_1	1
a v_5_2	0
a h_5_2	1
a v_5_3	0
a h_5_3	0
a v_5_4	1
a h_5_4	0
a v_5_5	-1
a h_5_5	0
a v_5_6	1
a h_5_6	-1
a v_5_7	0
a h_5_7	-1
a v_5_8	0
a h_5_8	0
a v_5_9	-1
a v_6_0	1
a h_6_0	0
a v_6_1	-1
a h_6_1	0
a v_6_2	1
a h_6_2	-1
a v_6_3	-1
a h_6_3	0
a v_6_4	1
a h_6_4	0
a v_6_5	0
a h_6_5	-1
a v_6_6	0
a h_6_6	0
a v_6_7	0
a h_6_7	0
a v_6_8	-1
a h_6_8	1
a v_6_9	0
a v_7_0	1
a h_7_0	0
a v_7_1	-1
a h_7_1	0
a v_7_2	1
a h_7_2	0
a v_7_3	-1
a h_7_3	0
a v_7_4	0
a h_7_4	1
a v_7_5	1
a h_7_5	0
a v_7_6	0
a h_7_6	0
a v_7_7	0
a h_7_7	0
a v_7_8	-1
a h_7_8	0
a v_7_9	0
a v_8_0	1
a h_8_0	0
a v_8_1	0
a h_8_1	-1
a v_8_2	0
a h_8_2	0
a v_8_3	0
a h_8_3	-1
a v_8_4	0
a h_8_4	-1
a v_8_5	0
a h_8_5	0
a v_8_6	-1
a h_8_6	1
a v_8_7	0
a h_8_7	1
a v_8_8	0
a h_8_8	0
a v_8_9	0
a h_9_0	1
a h_9_1	1
a h_9_2	1
a h_9_3	1
a h_9_4	1
a h_9_5	1
a h_9_6	0
a h_9_7	0
a h_9_8	0
a d_0_0	2
a d_0_1	2
a d_0_2	2
a d_0_3	2
a d_0_4	2
a d_0_5	2
a d_0_6	2
a d_0_7	2
a d_0_8	0
a d_0_9	0
a d_1_0	2
a d_1_1	0
a d_1_2	0
a d_1_3	2
a d_1_4	2
a d_1_5	0
a d_1_6	0
a d_1_7	2
a d_1_8	0
a d_1_9	0
a d_2_0	2
a d_2_1	2
a d_2_2	2
a d_2_3	2
a d_2_4	2
a d_2_5	2
a d_2_6	2
a d_2_7	2
a d_2_8	2
a d_2_9	2
a d_3_0	2
a d_3_1	2
a d_3_2	2
a d_3_3	2
a d_3_4	2
a d_3_5	2
a d_3_6	2
a d_3_7	2
a d_3_8	2
a d_3_9	2
a d_4_0	2
a d_4_1	0
a d_4_2	0
a d_4_3	2
a d_4_4	2
a d_4_5	2
a d_4_6	2
a d_4_7	2
a d_4_8	2
a d_4_9	2
a d_5_0	2
a d_5_1	2
a d_5_2	2
a d_5_3	2
a d_5_4	2
a d_5_5	2
a d_5_6	2
a d_5_7	2
a d_5_8	2
a d_5_9	2
a d_6_0	2
a d_6_1	2
a d_6_2	2
a d_6_3	2
a d_6_4	2
a d_6_5	2
a d_6_6	2
a d_6_7	0
a d_6_8	2
a d_6_9	2
a d_7_0	2
a d_7_1	2
a d_7_2	2
a d_7_3	2
a d_7_4	2
a d_7_5	2
a d_7_6	0
a d_7_7	0
a d_7_8	2
a d_7_9	0
a d_8_0	2
a d_8_1	2
a d_8_2	2
a d_8_3	2
a d_8_4	2
a d_8_5	2
a d_8_6	2
a d_8_7	2
a d_8_8	2
a d_8_9	0
a d_9_0	2
a d_9_1	2
a d_9_2	2
a d_9_3	2
a d_9_4	2
a d_9_5	2
a d_9_6	2
a d_9_7	0
a d_9_8	0
a d_9_9	0
a x_0_0	91
a y_0_0	0
a x_0_1	90
a y_0_1	0
a x_0_2	89
a y_0_2	0
a x_0_3	88
a y_0_3	0
a x_0_4	53
a y_0_4	0
a x_0_5	52
a y_0_5	0
a x_0_6	51
a y_0_6	0
a x_0_7	50
a y_0_7	0
a x_0_8	0
a y_0_8	0
a x_0_9	0
a y_0_9	0
a x_1_0	92
a y_1_0	0
a x_1_1	0
a y_1_1	0
a x_1_2	0
a y_1_2	0
a x_1_3	87
a y_1_3	0
a x_1_4	54
a y_1_4	0
a x_1_5	0
a y_1_5	0
a x_1_6	0
a y_1_6	0
a x_1_7	49
a y_1_7	0
a x_1_8	0
a y_1_8	0
a x_1_9	0
a y_1_9	0
a x_2_0	93
a y_2_0	0
a x_2_1	84
a y_2_1	0
a x_2_2	85
a y_2_2	0
a x_2_3	86
a y_2_3	0
a x_2_4	55
a y_2_4	0
a x_2_5	56
a y_2_5	0
a x_2_6	57
a y_2_6	0
a x_2_7	48
a y_2_7	0
a x_2_8	35
a y_2_8	0
a x_2_9	34
a y_2_9	0
a x_3_0	94
a y_3_0	0
a x_3_1	83
a y_3_1	0
a x_3_2	82
a y_3_2	0
a x_3_3	81
a y_3_3	0
a x_3_4	60
a y_3_4	0
a x_3_5	59
a y_3_5	0
a x_3_6	58
a y_3_6	0
a x_3_7	47
a y_3_7	0
a x_3_8	36
a y_3_8	0
a x_3_9	33
a y_3_9	0
a x_4_0	95
a y_4_0	0
a x_4_1	0
a y_4_1	0
a x_4_2	0
a y_4_2	0
a x_4_3	80
a y_4_3	0
a x_4_4	61
a y_4_4	0
a x_4_5	44
a y_4_5	0
a x_4_6	45
a y_4_6	0
a x_4_7	46
a y_4_7	0
a x_4_8	37
a y_4_8	0
a x_4_9	32
a y_4_9	0
a x_5_0	96
a y_5_0	0
a x_5_1	77
a y_5_1	0
a x_5_2	78
a y_5_2	0
a x_5_3	79
a y_5_3	0
a x_5_4	62
a y_5_4	0
a x_5_5	43
a y_5_5	0
a x_5_6	40
a y_5_6	0
a x_5_7	39
a y_5_7	0
a x_5_8	38
a y_5_8	0
a x_5_9	31
a y_5_9	0
a x_6_0	97
a y_6_0	0
a x_6_1	76
a y_6_1	0
a x_6_2	71
a y_6_2	0
a x_6_3	70
a y_6_3	0
a x_6_4	63
a y_6_4	0
a x_6_5	42
a y_6_5	0
a x_6_6	41
a y_6_6	0
a x_6_7	0
a y_6_7	0
a x_6_8	29
a y_6_8	0
a x_6_9	30
a y_6_9	0
a x_7_0	98
a y_7_0	0
a x_7_1	75
a y_7_1	0
a x_7_2	72
a y_7_2	0
a x_7_3	69
a y_7_3	0
a x_7_4	64
a y_7_4	0
a x_7_5	65
a y_7_5	0
a x_7_6	0
a y_7_6	0
a x_7_7	0
a y_7_7	0
a x_7_8	28
a y_7_8	0
a x_7_9	0
a y_7_9	0
a x_8_0	99
a y_8_0	0
a x_8_1	74
a y_8_1	0
a x_8_2	73
a y_8_2	0
a x_8_3	68
a y_8_3	0
a x_8_4	67
a y_8_4	0
a x_8_5	66
a y_8_5	0
a x_8_6	25
a y_8_6	0
a x_8_7	26
a y_8_7	0
a x_8_8	27
a y_8_8	0
a x_8_9	0
a y_8_9	0
a x_9_0	100
a y_9_0	0
a x_9_1	1
a y_9_1	1
a x_9_2	20
a y_9_2	0
a x_9_3	21
a y_9_3	0
a x_9_4	22
a y_9_4	0
a x_9_5	23
a y_9_5	0
a x_9_6	24
a y_9_6	0
a x_9_7	0
a y_9_7	0
a x_9_8	0
a y_9_8	0
a x_9_9	0
a y_9_9	0
a
Sugarの次期リリースには, 問題ファイルを読み込んで 制約条件を記述したCSPファイルを作成するツールを含める予定です. 以下は,その実行例です.
$ ./masyu.pl data/masyu-0.txt >csp/masyu-0.csp

$ /usr/bin/time sugar csp/masyu-0.csp >log/masyu-0.log
9.85user 0.20system 0:05.81elapsed 172%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+2928outputs (2major+26594minor)pagefaults 0swaps

$ ./masyu.pl -s log/masyu-0.log data/masyu-0.txt
; Masyu Puzzle
; # http://www.nikoli.co.jp/en/puzzles/masyu/
; size 10 10
; 1 - - - - 0 0 - - -
; - - - - - - - - - -
; - - - 1 1 - - - - -
; - - - 1 1 - - - - 0
; - - - - - 1 - - - -
; - 1 - - - - - - 1 0
; - - - - 0 - - - - -
; - 0 0 0 - - - - - -
; - - - - - - - - 1 -
; - - - - - 0 - - - -

+   +   +   +   +   +   +   +   +   +   +
  1---+---+---+   +---0---0---+   +   +  
+ | +   +   + | + | +   +   + | +   +   +
  +   +   +   +   +   +   +   +   +   +  
+ | +   +   + | + | +   +   + | +   +   +
  +   +---+---1   1---+---+   +   +---+  
+ | + | +   +   +   +   + | + | + | + | +
  +   +---+---1   1---+---+   +   +   0  
+ | +   +   + | + | +   +   + | + | + | +
  +   +   +   +   +   1---+---+   +   +  
+ | +   +   + | + | + | +   +   + | + | +
  +   1---+---+   +   +   +---+---1   0  
+ | + | +   +   + | + | + | +   +   + | +
  +   +   +---+   0   +---+   +   +---+  
+ | + | + | + | + | +   +   +   + | +   +
  +   0   0   0   +---+   +   +   +   +  
+ | + | + | + | +   + | +   +   + | +   +
  +   +---+   +---+---+   +---+---1   +  
+ | +   +   +   +   +   + | +   +   +   +
  +---+---+---+---+---0---+   +   +   +  
+   +   +   +   +   +   +   +   +   +   +

; END
以下は, Nikoli: ましゅのおためし問題中の おためし問題10 (36x20)をLet's Note CF-W5で解いた結果です(MiniSat2を使用). 8分半程度で解けています.
$ ./masyu.pl data/masyu-10.txt >csp/masyu-10.csp

$ /usr/bin/time sugar csp/masyu-10.csp >log/masyu-10.log
513.14user 1.63system 8:29.27elapsed 101%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+163784outputs (2major+91480minor)pagefaults 0swaps

$ ./masyu.pl -s log/masyu-10.log data/masyu-10.txt
; Masyu Puzzle
; # http://www.nikoli.co.jp/en/puzzles/masyu/
; size 36 20
; - - - - - - - - - - - 0 1 - 0 - - 0 1 - - - - 1 - - 0 - - - - 1 - - - -
; 1 - - - 0 - 1 - - - - - - - - 1 - - - - - 1 - - - - - - - - 0 - - - 1 -
; - - - 1 - - - - - 1 - - 0 - - - - - - - - - - - - - - - 1 - 0 - - - - -
; - - - 1 - - - - - - - - - 1 - - - 1 - 1 - - - - 1 1 - - - - - - - - - -
; - - 0 - - - - 0 - - 1 1 - - - - 1 - - - - 0 - - - - 0 - 1 1 - - 0 - - 1
; - 0 - - - 1 - - - - - - - 0 - - - - - - - - - 0 - - - - - - - - 0 - - 0
; - - - - - - - - - - 0 - - - - 1 - - 0 - - - - - 1 - 1 - - - - 0 - - 0 -
; 1 - - - 1 - - - 1 - - - 0 - 0 - - - - - - 1 - - 1 - - - 1 - - - - - - -
; - - - - - - - - 1 - - 0 - - - - - - - 0 - 1 0 - - - 0 - - - - - 1 - 1 -
; 1 - - 0 - - - 0 - - - - - - 1 - 0 - - - - - - - 0 - - - - - - 0 - - - -
; - - - - 1 - - - - 0 - - - - - - - 0 - - - 1 - - - - - - - - 1 - 1 - 1 -
; - 1 - 0 - - - - - - - 1 - - 0 - 1 - - 0 - - - - 0 0 - - - - - 0 - - - -
; - - - - - - 1 - 1 - 0 - - 1 0 - 1 - - - - - - 1 - - - 0 1 - 0 - 0 - - -
; - 0 - 1 - - - - - - - 0 - - - - - - - - - 1 - - - - - - - - - - - 1 - -
; - - 0 - - - 1 1 - - 1 - - - - - 0 1 - 1 - - - - - - 1 - - 0 0 - - 1 - -
; - - - - - - - - - - - 0 - 1 - - - - - - - - 1 1 - - - 0 - - - 1 - - - -
; - - - - - - - - 0 - - - - - - - - - 0 - - 0 - - - - - 0 - - - - - - - 1
; 1 - - - 0 - 1 - - - - - - - - 1 - - - - - - - 1 - - - - - - - - 0 0 - -
; - 0 - 1 - - 0 0 - - 1 - - - - - 0 - - 0 - - - - - 0 - - - 1 - - - - - -
; - - - - - - - - - - - - - 1 - - - - - - 1 - - - - - 1 - - - - - 0 - 0 -

+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
  +   +   +---+   +---+---+---+---+---+   +---0---1   +---0---+---+---0---1   +---+---+---+   1---+---+---0---+   +---+---+   1---+---+---+---+  
+   +   + | + | + | +   +   +   +   + | + | +   + | + | +   +   +   +   + | + | +   +   + | + | +   +   +   + | + | +   + | + | +   +   +   + | +
  1---+---+   +   0   +   1---+---+   +   +---+   +   +   +   1---+---+   +   +---+---1   +   +   +---+   +---+   +   +   0   +   +---+---1   +  
+ | +   +   + | + | +   + | +   + | + | +   + | + | + | +   + | +   + | + | +   +   + | + | + | + | + | + | +   + | +   + | + | + | +   + | + | +
  +   +---+---1   +---+   +   +---+   1---+---+   0   +   +   +   +---+   +---+---+   +   +---+   +   +   +---+---1   +   0   +   +---+   +   +  
+ | + | +   +   +   + | + | + | +   +   +   +   + | + | +   + | + | +   +   +   + | + | +   +   + | + | +   +   +   +   + | + | +   + | + | + | +
  +   +---+   1---+---+   +   +   +---+---+---+---+   1---+---+   +   1---+---1   +---+   +---+---1   1---+---+---+---+---+   +---+   +   +---+  
+ | +   + | + | +   +   + | + | + | +   +   +   +   +   +   +   + | + | +   + | +   +   + | +   +   +   +   +   +   +   +   +   + | + | +   +   +
  +---+   0   +   +---+---+   0   +---+---1   1---+---+---+---+---1   +   +   +   +---0---+   +---+   +---0---+---1   1---+---+   0   +---+---1  
+   + | + | + | + | +   +   + | +   +   + | + | +   +   +   +   +   + | +   + | + | +   +   + | + | + | +   +   + | + | +   + | + | +   +   + | +
  +   0   +---+   +   1---+---+   +---+   +   +   +---0---+---+---+---+   +---+   +   +---+   0   +   +---+---+   +   +   +---+   0   +---+   0  
+   + | +   +   + | + | +   +   + | + | + | + | + | +   +   +   +   +   + | +   + | + | + | + | + | +   +   + | + | + | + | +   + | + | + | + | +
  +   +---+---+---+   +   +   +   +   +   0   +---+   +---+   1---+---+   0   +---+   +   +---+   1---+---1   +   +---+   +---0---+   +   0   +  
+   +   +   +   +   + | +   +   + | + | + | +   +   + | + | + | +   + | + | + | +   + | +   +   +   +   + | + | +   +   +   +   +   + | + | + | +
  1---+---+---+---1   +   +---+---1   +---+   +---0---+   0   +   +   +---+   +---+---1   +---+---1   +   +   +   1---+---+---+---+---+   +   +  
+ | +   +   +   + | + | + | +   +   +   +   + | +   +   + | + | +   +   +   +   +   +   + | +   + | +   + | + | + | +   +   +   +   +   + | + | +
  +   +   +---+   +   +   +---+   1---+---+   0   +   +   +   +   +---+   +---0---+---1   0   +   +   +   0   +   +   +   +---+   1---+---1   +  
+ | +   + | + | + | + | +   + | + | +   + | + | +   +   + | + | + | + | + | +   +   + | + | +   + | +   + | + | + | +   + | + | + | +   +   + | +
  1---+---+   0   +   +---+   0   +   +---+   +   +---+---1   +   0   +   +   +   +   +   +   +   0   +   +---+   +   +   +   0   +   +   +   +  
+   +   +   + | + | +   + | + | + | + | +   + | + | +   +   + | + | + | + | +   +   + | + | +   + | +   +   +   + | +   + | + | + | +   +   + | +
  +---+---+---+   1---+---+   +   +   0   +   +   +   +---+---+   +   0   +   +---+---1   +   +---+   +   +---+   +---+---1   +   1---+---1   +  
+ | +   +   +   +   +   +   + | + | + | +   + | + | + | +   +   + | + | + | + | +   +   + | + | +   +   + | + | +   +   +   + | +   +   + | + | +
  +   1---+---0---+   +---+---+   +   +---+---1   +   +---0---+---1   +---+   0   +---+   +   +---0---0---+   +---+---+   +   0   +---+   +   +  
+ | + | +   +   + | + | +   +   + | +   +   +   + | +   +   +   +   +   +   + | + | + | + | +   +   +   +   +   +   + | +   + | + | + | + | + | +
  +   +   +---+---+   +   1---+---1   +---0---+---+   1---0---+---1   +---+   +---+   +   +   1---+---+   +---0---1   +---0---+   0   +   +---+  
+ | + | + | +   +   + | + | +   +   + | +   +   +   + | +   +   + | + | + | +   +   + | + | + | +   + | + | +   + | +   +   +   + | + | +   +   +
  +   0   +   1---+---+   +   +   +   +---+---0---+   +   +   +   +   +   +---+---+---1   +   +   +---+   +   +   +   +   +   +---+   1---+---+  
+ | + | + | + | +   +   + | +   +   +   +   +   + | + | +   +   + | + | +   +   +   +   + | + | + | +   + | +   + | +   +   + | +   +   +   + | +
  +---+   0   +   +---+---1   1---+---+---1   +---+   +   +   +   0   1---+---1   +   +   +   +   +---+---1   +   +---0---0---+   +   1---+---+  
+   +   + | + | + | +   +   + | +   +   + | + | +   + | +   +   + | +   +   + | +   +   + | + | +   +   +   +   +   +   +   +   +   + | +   +   +
  +---+---+   +---+   +---+   +   +   +   +   0   +   1---+---+   +---+   +   +   +---+---1   1---+---+   +---0---+---+---+---1   +   +   +   +  
+ | +   +   +   +   + | + | + | +   +   + | + | +   +   +   + | +   + | +   + | + | +   +   +   +   + | + | +   +   +   +   + | +   + | +   +   +
  +   +   +---+   +---+   +   +---0---+   +   +---+---+---+   +   +   +---0---+   +---0---+---+---+---+   +---0---+   +---+   +   +   +---+---1  
+ | +   + | + | + | +   + | +   +   + | + | +   +   +   + | + | +   +   +   +   +   +   +   +   +   +   +   +   + | + | + | + | +   +   +   + | +
  1---+---+   +   0   +   1---+---+   +   +   +   +---+   +   1---+---+   +   +---+   +---+---1   +   +---+   +---+   +   +   +---0---0---+   +  
+   +   +   + | + | +   +   +   + | + | + | +   + | + | + | +   +   + | +   + | + | + | +   + | +   + | + | + | +   + | + | +   +   +   + | + | +
  +---0---+---1   +   +---0---0---+   +   1---+---+   +   +---+---0---+   +   0   +   +---+   +   +   0   +   +---+---1   +   +---+---+---+   +  
+ | +   +   +   + | + | +   +   +   + | +   +   +   + | +   +   +   +   +   + | + | +   + | + | +   + | + | +   +   +   + | + | +   +   +   + | +
  +---+---+---+---+   +---+---+---+---+   +   +   +   1---+---+---+---+---+---+   1---+---+   +---+---+   1---+---+---+---+   +---0---+---0---+  
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +

; END

「パズルをSugar制約ソルバーで解く」に戻る


Naoyuki Tamura
( Last modified: Tue Jul 1 02:17:57 2008 JST ,   ?????  Since June 4, 2008 )