ぬりかべパズルをSugar制約ソルバーで解く


はじめに

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

例題

Nikoliによる ぬりかべの例題 です.
例題
 3     1  
    1     
2         
 1    2   
   2      
1     1  6
          

ぬりかべのルール

Nikoliによる「ぬりかべ」のルールは以下の通りです.
(Rule 1)
以下のルールに従って盤面のマスをぬりつぶします.
(Rule 2)
数字が入っているマスは黒マスにはなりません.
(Rule 3)
数字は,その数字が含まれる, 黒マスによって分断されたところ(シマとよぶ)のマスの数です. すべてのシマには数字が1つずつ入っていなければなりません.
(Rule 4)
すべての黒マスはタテヨコにひとつながりになっていなければなりません.
(Rule 5)
黒マスが2x2マス以上のカタマリになってはいけません.
「ぬりかべ」を 制約充足問題(CSP, Constraint Satisfaction Problem)として表すための 方法について考えていきます.

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

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

実行結果

すべての制約を記述したファイルを作成し, Sugarで実行すると以下のような結果が得られます.
s SATISFIABLE
a x_0_0	0
a x_0_1	1
a x_0_2	1
a x_0_3	1
a x_0_4	0
a x_0_5	2
a x_0_6	0
a x_1_0	0
a x_1_1	0
a x_1_2	0
a x_1_3	0
a x_1_4	0
a x_1_5	0
a x_1_6	0
a x_2_0	3
a x_2_1	3
a x_2_2	0
a x_2_3	4
a x_2_4	0
a x_2_5	10
a x_2_6	10
a x_3_0	0
a x_3_1	0
a x_3_2	0
a x_3_3	0
a x_3_4	0
a x_3_5	0
a x_3_6	10
a x_4_0	0
a x_4_1	5
a x_4_2	0
a x_4_3	6
a x_4_4	6
a x_4_5	0
a x_4_6	10
a x_5_0	0
a x_5_1	0
a x_5_2	7
a x_5_3	0
a x_5_4	0
a x_5_5	0
a x_5_6	10
a x_6_0	8
a x_6_1	0
a x_6_2	7
a x_6_3	0
a x_6_4	9
a x_6_5	0
a x_6_6	10
a r_0_0	0
a r_0_1	1
a r_0_2	0
a r_0_3	0
a r_0_4	0
a r_0_5	1
a r_0_6	0
a r_1_0	0
a r_1_1	0
a r_1_2	0
a r_1_3	0
a r_1_4	0
a r_1_5	0
a r_1_6	1
a r_2_0	1
a r_2_1	0
a r_2_2	0
a r_2_3	1
a r_2_4	0
a r_2_5	0
a r_2_6	0
a r_3_0	0
a r_3_1	0
a r_3_2	0
a r_3_3	0
a r_3_4	0
a r_3_5	0
a r_3_6	0
a r_4_0	0
a r_4_1	1
a r_4_2	0
a r_4_3	0
a r_4_4	1
a r_4_5	0
a r_4_6	0
a r_5_0	0
a r_5_1	0
a r_5_2	1
a r_5_3	0
a r_5_4	0
a r_5_5	0
a r_5_6	0
a r_6_0	1
a r_6_1	0
a r_6_2	0
a r_6_3	0
a r_6_4	1
a r_6_5	0
a r_6_6	1
a v_0_0	1
a h_0_0	0
a v_0_1	0
a h_0_1	-1
a v_0_2	0
a h_0_2	-1
a v_0_3	0
a h_0_3	0
a v_0_4	1
a h_0_4	0
a v_0_5	0
a h_0_5	0
a v_0_6	1
a v_1_0	0
a h_1_0	1
a v_1_1	0
a h_1_1	1
a v_1_2	-1
a h_1_2	1
a v_1_3	0
a h_1_3	1
a v_1_4	0
a h_1_4	1
a v_1_5	0
a h_1_5	1
a v_1_6	0
a v_2_0	0
a h_2_0	-1
a v_2_1	0
a h_2_1	0
a v_2_2	-1
a h_2_2	0
a v_2_3	0
a h_2_3	0
a v_2_4	1
a h_2_4	0
a v_2_5	0
a h_2_5	1
a v_2_6	1
a v_3_0	-1
a h_3_0	1
a v_3_1	0
a h_3_1	1
a v_3_2	-1
a h_3_2	-1
a v_3_3	0
a h_3_3	-1
a v_3_4	0
a h_3_4	-1
a v_3_5	-1
a h_3_5	0
a v_3_6	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	0
a h_4_3	1
a v_4_4	0
a h_4_4	0
a v_4_5	-1
a h_4_5	0
a v_4_6	1
a v_5_0	0
a h_5_0	-1
a v_5_1	-1
a h_5_1	0
a v_5_2	-1
a h_5_2	0
a v_5_3	-1
a h_5_3	1
a v_5_4	0
a h_5_4	1
a v_5_5	-1
a h_5_5	0
a v_5_6	1
a h_6_0	0
a h_6_1	0
a h_6_2	0
a h_6_3	0
a h_6_4	0
a h_6_5	0
a z_0_0	29
a z_0_1	27
a z_0_2	28
a z_0_3	29
a z_0_4	29
a z_0_5	29
a z_0_6	29
a z_1_0	28
a z_1_1	27
a z_1_2	19
a z_1_3	18
a z_1_4	17
a z_1_5	16
a z_1_6	15
a z_2_0	28
a z_2_1	29
a z_2_2	20
a z_2_3	29
a z_2_4	29
a z_2_5	29
a z_2_6	28
a z_3_0	25
a z_3_1	24
a z_3_2	21
a z_3_3	22
a z_3_4	23
a z_3_5	24
a z_3_6	27
a z_4_0	26
a z_4_1	29
a z_4_2	29
a z_4_3	29
a z_4_4	28
a z_4_5	25
a z_4_6	26
a z_5_0	27
a z_5_1	28
a z_5_2	28
a z_5_3	28
a z_5_4	27
a z_5_5	26
a z_5_6	25
a z_6_0	29
a z_6_1	29
a z_6_2	29
a z_6_3	29
a z_6_4	29
a z_6_5	29
a z_6_6	24
a c_0_0	6
a c_0_1	3
a c_0_2	2
a c_0_3	1
a c_0_4	6
a c_0_5	1
a c_0_6	6
a c_1_0	6
a c_1_1	6
a c_1_2	6
a c_1_3	6
a c_1_4	6
a c_1_5	5
a c_1_6	1
a c_2_0	2
a c_2_1	1
a c_2_2	1
a c_2_3	1
a c_2_4	6
a c_2_5	1
a c_2_6	2
a c_3_0	6
a c_3_1	6
a c_3_2	1
a c_3_3	1
a c_3_4	2
a c_3_5	3
a c_3_6	3
a c_4_0	6
a c_4_1	1
a c_4_2	1
a c_4_3	1
a c_4_4	2
a c_4_5	6
a c_4_6	4
a c_5_0	6
a c_5_1	6
a c_5_2	2
a c_5_3	1
a c_5_4	2
a c_5_5	6
a c_5_6	5
a c_6_0	1
a c_6_1	6
a c_6_2	1
a c_6_3	6
a c_6_4	1
a c_6_5	6
a c_6_6	6
a
Sugarの次期リリースには, 問題ファイルを読み込んで 制約条件を記述したCSPファイルを作成するツールを含める予定です. 以下は,その実行例です.
$ ./nurikabe.pl data/nurikabe-0.txt >csp/nurikabe-0.csp

$ /usr/bin/time sugar csp/nurikabe-0.csp >log/nurikabe-0.log
5.96user 0.15system 0:03.56elapsed 171%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+1192outputs (2major+25853minor)pagefaults 0swaps

$ ./nurikabe.pl -s log/nurikabe-0.log data/nurikabe-0.txt
; Nurikabe Puzzle
; # http://www.nikoli.co.jp/en/puzzles/nurikabe/
; size 7 7
; - 3 - - - 1 -
; - - - - - - -
; 2 - - 1 - - -
; - - - - - - -
; - 1 - - 2 - -
; - - 2 - - - -
; 1 - - - 1 - 6

### 3  -  - ### 1 ###
#####################
 2  - ### 1 ### -  - 
################## - 
### 1 ### -  2 ### - 
###### 2 ######### - 
 1 ### - ### 1 ### 6 

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

$ /usr/bin/time sugar csp/nurikabe-10.csp >log/nurikabe-10.log
502.85user 2.46system 8:18.77elapsed 101%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+243944outputs (2major+124014minor)pagefaults 0swaps

$ ./nurikabe.pl -s log/nurikabe-10.log data/nurikabe-10.txt
; Nurikabe Puzzle
; # http://www.nikoli.co.jp/en/puzzles/nurikabe/
; size 36 20
;  -  -  -  -  -  -  -  -  -  -  -  4  -  -  -  -  -  -  -  -  -  -  -  -  2  -  -  -  -  -  -  -  -  -  -  -
;  3  -  4  -  -  -  -  -  -  -  -  -  -  2  -  -  -  7  -  -  -  -  -  -  -  -  -  8  -  -  -  -  -  -  2  -
;  -  -  -  -  7  -  -  -  -  -  -  5  -  -  -  1  -  -  -  8  -  5  -  -  -  1  -  -  2  -  -  4  -  -  -  2
;  6  -  -  -  -  4  -  -  -  -  -  -  -  3  -  -  -  -  -  -  -  -  -  -  2  -  2  -  -  -  -  -  -  -  -  -
;  -  -  -  -  -  -  -  -  -  -  -  6  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  4  -  -  -  -
;  -  -  -  -  2  -  -  -  -  -  -  -  -  -  -  -  -  -  1  -  -  2  -  -  -  -  -  -  -  -  -  -  -  2  -  -
;  -  -  -  -  -  -  -  -  1  -  -  -  -  -  -  -  4  -  -  -  -  -  4  -  -  -  -  4  -  -  1  -  -  -  -  -
;  -  1  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  3  -  -  -  -  -  -  -  -  -  -  -  -  4  -  4
;  -  -  -  -  -  2  -  -  -  -  -  4  -  -  4  -  -  -  -  -  -  -  -  -  -  -  -  4  -  -  -  -  -  -  -  -
;  -  -  -  -  -  -  -  5  -  -  3  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  2  -  4  -  -  -
;  -  5  -  1  -  -  -  -  -  -  -  -  -  -  -  -  -  -  1  -  -  -  -  3  -  -  -  8  -  -  -  2  -  -  -  -
;  -  -  -  -  -  1  -  -  -  2  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
;  2  -  -  -  -  -  -  -  -  -  -  -  -  2  -  5  -  -  -  -  -  -  -  -  -  -  -  4  -  -  -  -  -  2  -  1
;  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  2  -  -  -  -  -  -
;  1  -  -  2  -  -  -  4  -  -  7  -  -  - 18  -  -  -  1  -  -  -  -  -  -  -  -  -  -  -  -  1  -  -  -  1
;  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  2  -  -  -  8  -  4  -  -  -  -  -  -  -  -
;  -  -  -  -  3  -  -  -  -  -  -  -  -  -  -  - 18  -  -  -  -  -  1  -  -  -  -  -  -  -  -  -  -  4  -  -
;  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  4  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  4  -
;  -  -  -  -  -  -  3  -  1  -  -  -  4  -  -  -  -  -  -  4  -  -  -  -  2  -  -  -  -  4  -  -  -  4  -  -
;  6  -  -  -  -  -  -  1  -  -  3  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  4  -  -  -  -  -  -  -

 -  - ##################### -  -  4  - ######### -  -  -  -  -  - ### -  2 ### -  -  -  -  -  - ############
 3 ### 4 ### -  -  -  - ############### 2  - ###### 7 ######################## -  8 ############### -  2 ###
###### - ### 7 ###### -  - ### -  5 ######### 1 ######### 8 ### 5  -  - ### 1 ###### 2  - ### 4  - ###### 2 
 6 ### -  - ### 4 ######### -  - ###### 3 ######### -  -  -  - ### - ### 2 ### 2 ############### -  - ### - 
 - ############ -  -  - ### - ### 6 ### - ### -  -  - ############ - ### - ### - ### -  -  -  4 ############
 -  -  - ### 2 ################## - ### - ############ 1 ### -  2 ################################# 2  - ###
###### - ### - ### - ### 1 ### -  - ###### - ### 4 ############### 4  -  -  - ### 4  - ### 1 ### - ###### - 
### 1 ############ -  - ### -  - ###### -  - ### - ### -  -  3 ##################### -  - ### -  -  4 ### 4 
###### -  - ### 2 ### - ######### 4  - ### 4 ### -  - ######### -  - ### -  -  -  4 ##################### - 
### -  - ###### - ### 5 ### -  3 ### - ################## -  -  - ##################### -  2 ### 4  - ### - 
### 5 ### 1 ################## - ### - ### -  -  - ### 1 ### - ### -  3 ### -  -  8  - ###### 2 ### -  - ###
############### 1 ### - ### 2 ############### - ############ - ### - ### -  - ###### -  - ### - ############
 2  - ### -  - ###### - ### - ### - ### 2 ### 5 ### -  -  -  - ################## 4 ############ -  2 ### 1 
############ -  - ### - ###### -  - ### - ###### -  - ###### -  - ### - ### -  -  - ### 2  - ###############
 1 ### -  2 ### - ### 4 ### -  7  -  - ###18 ### - ### 1 ############ - ##################### 1 ### - ### 1 
############### -  - ##################### - ### - ######### -  2 ### -  -  8 ### 4  -  -  - ### -  - ######
 - ### -  -  3 ### -  -  -  -  -  -  -  -  - ###18 ### - ######### 1 ### -  - ##################### 4 ### - 
 - ################################################ 4  - ### - ############ - ### -  -  - ### - ###### 4  - 
 -  -  - ### -  -  3 ### 1 ### - ### 4  -  -  - ### - ### 4  -  - ### -  2 ############ 4 ### -  -  4 ### - 
 6 ################## 1 ###### 3  - ####################################### -  -  -  4 #####################

; END

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


Naoyuki Tamura
( Last modified: Fri Jun 13 14:47:51 2008 JST ,   ?????  Since June 4, 2008 )