へやわけパズルをSugar制約ソルバーで解く


はじめに

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

例題

Nikoliによる へやわけの例題 です.
例題
2             
              
         5    
              
 0 1          
          2   
 1            
2             
    3         
              

へやわけのルール

Nikoliによる「へやわけ」のルールは以下の通りです.
(Rule 1)
以下のルールに従って,盤面に黒マスを配置します.
(Rule 2)
出ている数字は,太線で区切られた四角(部屋)の中に入る黒マスの数です. 数字の入っていない部屋には,いくつ黒マスが入るかわかりません.
(Rule 3)
白マスは,タテまたはヨコにまっすぐに3つの部屋にわたって続いてはいけません.
(Rule 4)
黒マスはタテヨコに連続しません. また,黒マスによって盤面が分断されることはありません.
「へやわけ」を 制約充足問題(CSP, Constraint Satisfaction Problem)として表すための 方法について考えていきます.

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

****************作成中****************

実行結果

すべての制約を記述したファイルを作成し, Sugarで実行すると以下のような結果が得られます.
s SATISFIABLE
a x_0_0	1
a x_0_1	0
a x_0_2	0
a x_0_3	1
a x_0_4	0
a x_0_5	0
a x_0_6	0
a x_0_7	1
a x_0_8	0
a x_0_9	1
a x_1_0	0
a x_1_1	1
a x_1_2	0
a x_1_3	0
a x_1_4	0
a x_1_5	1
a x_1_6	0
a x_1_7	0
a x_1_8	0
a x_1_9	0
a x_2_0	0
a x_2_1	0
a x_2_2	1
a x_2_3	0
a x_2_4	0
a x_2_5	0
a x_2_6	1
a x_2_7	0
a x_2_8	1
a x_2_9	0
a x_3_0	0
a x_3_1	0
a x_3_2	0
a x_3_3	1
a x_3_4	0
a x_3_5	0
a x_3_6	0
a x_3_7	1
a x_3_8	0
a x_3_9	0
a x_4_0	1
a x_4_1	0
a x_4_2	0
a x_4_3	0
a x_4_4	1
a x_4_5	0
a x_4_6	1
a x_4_7	0
a x_4_8	1
a x_4_9	0
a x_5_0	0
a x_5_1	0
a x_5_2	1
a x_5_3	0
a x_5_4	0
a x_5_5	1
a x_5_6	0
a x_5_7	0
a x_5_8	0
a x_5_9	0
a x_6_0	0
a x_6_1	1
a x_6_2	0
a x_6_3	0
a x_6_4	1
a x_6_5	0
a x_6_6	0
a x_6_7	1
a x_6_8	0
a x_6_9	1
a x_7_0	1
a x_7_1	0
a x_7_2	0
a x_7_3	0
a x_7_4	0
a x_7_5	0
a x_7_6	1
a x_7_7	0
a x_7_8	0
a x_7_9	0
a x_8_0	0
a x_8_1	0
a x_8_2	0
a x_8_3	1
a x_8_4	0
a x_8_5	1
a x_8_6	0
a x_8_7	0
a x_8_8	1
a x_8_9	0
a x_9_0	1
a x_9_1	0
a x_9_2	0
a x_9_3	0
a x_9_4	1
a x_9_5	0
a x_9_6	0
a x_9_7	1
a x_9_8	0
a x_9_9	0
a z_0_0	0
a r_0_0	0
a z_0_1	75
a r_0_1	0
a z_0_2	76
a r_0_2	0
a z_0_3	0
a r_0_3	0
a z_0_4	80
a r_0_4	0
a z_0_5	81
a r_0_5	0
a z_0_6	82
a r_0_6	0
a z_0_7	0
a r_0_7	0
a z_0_8	84
a r_0_8	0
a z_0_9	0
a r_0_9	0
a z_1_0	91
a r_1_0	0
a z_1_1	0
a r_1_1	0
a z_1_2	77
a r_1_2	0
a z_1_3	78
a r_1_3	0
a z_1_4	79
a r_1_4	0
a z_1_5	0
a r_1_5	0
a z_1_6	83
a r_1_6	0
a z_1_7	84
a r_1_7	0
a z_1_8	85
a r_1_8	0
a z_1_9	86
a r_1_9	0
a z_2_0	92
a r_2_0	0
a z_2_1	93
a r_2_1	0
a z_2_2	0
a r_2_2	0
a z_2_3	77
a r_2_3	0
a z_2_4	76
a r_2_4	0
a z_2_5	75
a r_2_5	0
a z_2_6	0
a r_2_6	0
a z_2_7	83
a r_2_7	0
a z_2_8	0
a r_2_8	0
a z_2_9	87
a r_2_9	0
a z_3_0	93
a r_3_0	0
a z_3_1	94
a r_3_1	0
a z_3_2	95
a r_3_2	0
a z_3_3	0
a r_3_3	0
a z_3_4	73
a r_3_4	0
a z_3_5	74
a r_3_5	0
a z_3_6	73
a r_3_6	0
a z_3_7	0
a r_3_7	0
a z_3_8	87
a r_3_8	0
a z_3_9	88
a r_3_9	0
a z_4_0	0
a r_4_0	0
a z_4_1	93
a r_4_1	0
a z_4_2	96
a r_4_2	0
a z_4_3	97
a r_4_3	0
a z_4_4	0
a r_4_4	0
a z_4_5	73
a r_4_5	0
a z_4_6	0
a r_4_6	0
a z_4_7	91
a r_4_7	0
a z_4_8	0
a r_4_8	0
a z_4_9	89
a r_4_9	0
a z_5_0	91
a r_5_0	0
a z_5_1	92
a r_5_1	0
a z_5_2	0
a r_5_2	0
a z_5_3	98
a r_5_3	0
a z_5_4	97
a r_5_4	0
a z_5_5	0
a r_5_5	0
a z_5_6	93
a r_5_6	0
a z_5_7	92
a r_5_7	0
a z_5_8	91
a r_5_8	0
a z_5_9	90
a r_5_9	0
a z_6_0	90
a r_6_0	0
a z_6_1	0
a r_6_1	0
a z_6_2	100
a r_6_2	1
a z_6_3	99
a r_6_3	0
a z_6_4	0
a r_6_4	0
a z_6_5	95
a r_6_5	0
a z_6_6	94
a r_6_6	0
a z_6_7	0
a r_6_7	0
a z_6_8	90
a r_6_8	0
a z_6_9	0
a r_6_9	0
a z_7_0	0
a r_7_0	0
a z_7_1	98
a r_7_1	0
a z_7_2	99
a r_7_2	0
a z_7_3	98
a r_7_3	0
a z_7_4	97
a r_7_4	0
a z_7_5	96
a r_7_5	0
a z_7_6	0
a r_7_6	0
a z_7_7	88
a r_7_7	0
a z_7_8	89
a r_7_8	0
a z_7_9	88
a r_7_9	0
a z_8_0	96
a r_8_0	0
a z_8_1	97
a r_8_1	0
a z_8_2	98
a r_8_2	0
a z_8_3	0
a r_8_3	0
a z_8_4	96
a r_8_4	0
a z_8_5	0
a r_8_5	0
a z_8_6	86
a r_8_6	0
a z_8_7	87
a r_8_7	0
a z_8_8	0
a r_8_8	0
a z_8_9	87
a r_8_9	0
a z_9_0	0
a r_9_0	0
a z_9_1	96
a r_9_1	0
a z_9_2	97
a r_9_2	0
a z_9_3	96
a r_9_3	0
a z_9_4	0
a r_9_4	0
a z_9_5	84
a r_9_5	0
a z_9_6	85
a r_9_6	0
a z_9_7	0
a r_9_7	0
a z_9_8	85
a r_9_8	0
a z_9_9	86
a r_9_9	0
a
Sugarの次期リリースには, 問題ファイルを読み込んで 制約条件を記述したCSPファイルを作成するツールを含める予定です. 以下は,その実行例です.
$ ./heyawake.pl data/heyawake-0.txt >csp/heyawake-0.csp

$ /usr/bin/time sugar csp/heyawake-0.csp >log/heyawake-0.log
3.79user 0.10system 0:02.47elapsed 157%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+2216outputs (2major+16774minor)pagefaults 0swaps

$ ./heyawake.pl -s log/heyawake-0.log data/heyawake-0.txt
; Heyawake Puzzle
; # http://www.nikoli.co.jp/en/puzzles/heyawake/
; size 10 10
; 1  2 2 2 X 1 2 X 3 2 X 4 1
; 2  X 3 1 X 1 4
; 3  X 4 2 X 2 3 5 3 3
; 4
; 5  X 1 3 0 1 2 1 2 3
; 6  X 3 2 2 3 2
; 7  1 1 1
; 8  2 1 3 X 2 3 X 3 1 X 2 3 X 2 1
; 9  3 3 2 X 2 2
; 10
; 

### -  - ### -  -  - ### - ###
 - ### -  -  - ### -  -  -  - 
 -  - ### -  -  - ### - ### - 
 -  -  - ### -  -  - ### -  - 
### -  -  - ### - ### - ### - 
 -  - ### -  - ### -  -  -  - 
 - ### -  - ### -  - ### - ###
### -  -  -  -  - ### -  -  - 
 -  -  - ### - ### -  - ### - 
### -  -  - ### -  - ### -  - 

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

$ /usr/bin/time sugar csp/heyawake-10.csp >log/heyawake-10.log
50.11user 1.16system 0:48.30elapsed 106%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+133912outputs (2major+75490minor)pagefaults 0swaps

$ ./heyawake.pl -s log/heyawake-10.log data/heyawake-10.txt
; Heyawake Puzzle
; # http://www.nikoli.co.jp/en/puzzles/heyawake/
; size 36 20
; 1  2 2 2  X 2 2  2 2 2  X 2 2  X 2 2  X 2 4  3 2 3  2 2 6  X 2 3  3 2 4  4 2 5  X 2 2  1 2 4  X 2 3  2 2 3  2 2 2  X 2 2  X 2 2
; 2
; 3  X 2 3  2 2 2  X 2 2  3 2 4  X 2 2  X 2 2  2 2 4  1 2 2  0 2 2
; 4  2 2 2  2 2 2  3 2 3  X 2 2
; 5  1 2 4  2 2 2  1 2 2  2 2 2  3 2 4  X 2 2  2 2 2  1 2 2  2 2 2
; 6  3 2 3  1 2 3  3 2 4  1 2 3  X 2 5
; 7  1 2 3  2 2 2  2 2 2  X 2 2  X 2 2  1 2 2  1 2 2  X 2 4  1 2 2  0 2 2  2 2 3
; 8
; 9  X 2 3  X 2 2  2 2 2  X 2 4  1 2 2  2 2 2  X 2 2  0 2 2  2 2 3  X 2 3  X 2 5  X 2 6  2 2 6
; 10 2 2 3  3 2 3  2 2 3
; 11 2 2 4  2 2 4  X 2 2  1 2 2  1 2 2  X 2 2  3 2 4  0 2 2
; 12 0 2 2  0 2 2  X 2 2
; 13 0 2 2  X 2 2  2 2 3  3 2 3  X 2 2  X 2 2  X 2 2  X 2 2  2 2 2
; 14 1 2 2  X 2 3  X 2 2  3 2 4
; 15 4 2 6  X 2 2  X 2 2  X 2 2  1 2 3  X 2 4  0 2 2  2 2 3  2 2 2  2 2 3  X 2 6  2 2 3
; 16 X 2 3  2 2 5  X 2 5  3 2 3
; 17 X 2 2  2 2 2  X 2 2  1 2 2  X 2 2  0 2 2
; 18 1 2 3  1 2 3  X 2 3  3 2 3  2 2 3
; 19 0 2 2  2 2 2  X 2 2  2 2 2  1 2 2  1 2 2  X 2 2  X 2 2  X 2 2
; 20

### -  -  - ### -  - ### -  - ### -  - ### -  -  -  - ### -  - ### -  -  -  - ### - ### -  - ### -  -  -  - 
 - ### -  -  - ### -  - ### -  -  - ### -  -  - ### -  - ### -  - ### -  - ### -  -  -  - ### -  - ### - ###
 -  -  - ### -  -  - ### -  - ### -  - ### -  -  -  - ### -  - ### -  -  -  - ### - ### -  - ### -  -  -  - 
### - ### -  -  - ### -  - ### -  - ### -  - ### - ### -  - ### -  - ### -  -  - ### -  -  -  - ### -  -  - 
 -  -  -  - ### -  - ### -  - ### -  - ### -  - ### -  - ### - ### -  - ### - ### -  - ### -  -  -  - ### - 
 - ### -  -  - ### -  -  - ### - ### -  - ### -  - ### -  -  -  - ### -  - ### - ### -  - ### -  - ### - ###
### -  - ### -  - ### - ### -  -  - ### -  -  - ### -  - ### -  -  -  - ### -  -  - ### -  - ### -  -  -  - 
 - ### -  - ### -  - ### - ### -  -  -  - ### -  -  - ### - ### -  - ### -  - ### -  - ### -  -  -  - ### - 
 -  - ### -  -  - ### -  -  - ### -  - ### - ### - ### -  -  -  - ### -  - ### - ### -  -  -  - ### -  - ###
 -  -  - ### -  -  - ### -  -  -  - ### -  -  - ### -  -  - ### -  -  - ### -  -  - ### - ### -  -  - ### - 
### -  -  - ### -  -  - ### -  - ### -  - ### -  - ### - ### - ### - ### -  -  - ### -  -  - ### -  -  -  - 
 -  - ### -  - ### -  -  - ### -  -  - ### -  - ### - ### -  -  - ### -  -  - ### -  -  - ### -  -  - ### - 
 -  -  - ### -  -  - ### -  - ### - ### -  - ### -  -  - ### -  -  -  - ### -  - ### - ### -  - ### -  - ###
 - ### -  -  -  - ### -  - ### -  -  - ### -  -  -  - ### - ### - ### -  - ### -  -  -  - ### -  -  - ### - 
 -  - ### - ### -  -  - ### - ### - ### - ### -  - ### -  -  - ### -  - ### - ### - ### -  - ### - ### -  - 
### -  - ### - ### - ### -  -  - ### -  -  -  - ### -  -  - ### -  - ### -  -  - ### - ### -  - ### -  - ###
 - ### -  -  -  - ### -  - ### -  -  - ### -  -  - ### - ### -  - ### -  - ### -  -  -  - ### -  -  - ### - 
 -  -  - ### -  -  - ### -  -  -  - ### -  - ### -  -  -  - ### -  - ### -  -  - ### -  -  - ### -  -  -  - 
 -  -  -  - ### -  -  - ### - ### -  - ### -  -  -  - ### -  - ### -  -  - ### -  - ### - ### -  -  - ### - 
 -  - ### -  - ### -  -  - ### -  - ### -  -  - ### -  -  - ### -  - ### -  -  - ### -  -  - ### -  -  - ###

; END

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


Naoyuki Tamura
( Last modified: Thu Jun 19 12:08:33 2008 JST ,   ?????  Since June 4, 2008 )