● | ○ | ○ | |||||||
● | ● | ||||||||
● | ● | ○ | |||||||
● | |||||||||
● | ● | ○ | |||||||
○ | |||||||||
○ | ○ | ○ | |||||||
● | |||||||||
○ |
なお,以下ではパズルの盤面の一番上の行を第0行, 一番左の列を第0列として数えます.
たとえば,左上の節点から下への辺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)他の節点についても同様の条件を追加します.
(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)他の白丸の節点についても同様に制約条件を追加します.
ここまでは比較的簡単でしたが,「全体で1つの輪っか」という条件はかなり面倒です. 一つの方法は, できあがったグラフが連結(connected)であるという条件を追加することですが, 辺の個数の二乗に比例する制約条件が必要なように思われます. それだと,少し大きなパズルに対しては,制約条件の個数が膨大になり, 高速な制約ソルバーであるSugarでも解くことができません.
そこで,少し工夫をして, 以下のように辺の個数に比例する制約条件で表す方法を考えてみました. これより良い方法もあるかも知れません. ご存知の方は,著者までお知らせいただけましたら幸いです.
これまでの条件だと,複数の輪っかが存在する可能性があります. そこで,各輪っかについて,節点に1から順に番号を付けることにします. 番号は辺の向きにしたがって付けていきます. たとえば,二つの輪っかがある場合,以下のように各節点に番号を付けるのです.
|
|
左側の輪っかは左上の節点から順に辺の向きに番号が付けられており, 右側の輪っかは右下の節点から順に辺の向きに番号が付けられています.
このように節点に番号を付けることができれば, 「1の番号の付いた節点(始節点)がちょうど1つ」という条件により,輪っかを一つにできます.
「始節点がちょうど1つ」という条件は, 各節点について,その番号が1なら1の値を取り,それ以外の場合0の値を取る変数を用意し, すべての節点についてのそれらの合計が1に等しくなることで表現できます.
そこで,まず以下の変数を用意します.
(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)))他の節点についても同様に記述します.
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 aSugarの次期リリースには, 問題ファイルを読み込んで 制約条件を記述した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