Essays/Nurikabe
< Essays
Jump to navigation
Jump to search
Introduction
Nurikabe ぬりかべ is a binary determination puzzle invented by the Japanese games publisher Nikoli in March 1991. A puzzle is specified as a matrix of zeros and positive integers. The zeros are to be colored black or white; the positive integers are to be left alone and are considered to be colored white. In a solution:
- "Connected" means rectangularly connected.
- Each cell numbered k is part of an island of k connected white cells, and every white cell must be part of such an island.
- All the black cells are connected.
- There are no 2x2 blocks of black cells.
- A puzzle has a unique solution.
n1 below is a Nurikabe puzzle, and s1 is its solution wherein 0 denotes white and _1 denotes black. (In addition, _2 denotes "free", not yet known to be black or white.) The verb see makes a more appealing display of a solution.
n1
0 1 0 0 0
0 0 0 0 2
0 0 0 0 0
3 0 0 0 0
0 0 0 2 0
s1
_1 1 _1 _1 _1
_1 _1 _1 0 2
_1 0 _1 _1 _1
3 0 _1 0 _1
_1 _1 _1 2 _1
WHITE=: 0
BLACK=: _1
FREE =: _2
init=: + FREE*0=]
see =: 3 : 'y { _1|.(":&.>1+i.>./,y),<"0 ''?X '''
init n1
_2 1 _2 _2 _2
_2 _2 _2 _2 2
_2 _2 _2 _2 _2
3 _2 _2 _2 _2
_2 _2 _2 2 _2
see init n1
┌─┬─┬─┬─┬─┐
│?│1│?│?│?│
├─┼─┼─┼─┼─┤
│?│?│?│?│2│
├─┼─┼─┼─┼─┤
│?│?│?│?│?│
├─┼─┼─┼─┼─┤
│3│?│?│?│?│
├─┼─┼─┼─┼─┤
│?│?│?│2│?│
└─┴─┴─┴─┴─┘
see s1
┌─┬─┬─┬─┬─┐
│X│1│X│X│X│
├─┼─┼─┼─┼─┤
│X│X│X│ │2│
├─┼─┼─┼─┼─┤
│X│ │X│X│X│
├─┼─┼─┼─┼─┤
│3│ │X│ │X│
├─┼─┼─┼─┼─┤
│X│X│X│2│X│
└─┴─┴─┴─┴─┘
Check
Checking a solution (other than the uniqueness part) is much easier than deriving it. Here, the connected components are computed by transitive closure on the connection matrix.
connect=: 3 : 0 NB. connection matrix for Nurikabe
s=. WHITE<.y
i=. I., (}.=}:) s
j=. I., 0,.~(}."1 = }:"1) s
(+.|:) 1 (<"1 (i+/0,{:$y),j+/0 1)}=i.*/$y
)
tc=: +./ .*~^:(>.@(2&^.)@#)
NB. transitive closure of a reflexive graph
islands=: ~. @ (<@I."1"_) @ tc @ connect
NB. connected components
check=: 3 : 0 NB. 1 iff y is a Nurikabe solution
assert. (y e. BLACK,WHITE) +. 0<y
assert. -. 2 2 (2 2$BLACK)&-:;._3 y
c=. islands y
assert. (#c) = 1++/,0<y
i=. c{&.><,y
n=. #&>i
b=. i = n$&.><BLACK
assert. 1=+/b
assert. b +. *./@(0&<:)&>i
assert. b +. 1 = +/@(0&<)&>i
assert. b +. n = +/&>i
1
)
For example:
check s1
1
check n1
|assertion failure: check
| (#c)=1++/,0<y
'01' {~ connect s1
1000010000000000000000000
0100000000000000000000000
0011000100000000000000000
0011100000000000000000000
0001100000000000000000000
1000011000100000000000000
0000011100000000000000000
0010001100001000000000000
0000000011000000000000000
0000000011000000000000000
0000010000100000000000000
0000000000010000100000000
0000000100001100010000000
0000000000001110000000000
0000000000000110000100000
0000000000000001100000000
0000000000010001100000000
0000000000001000010000100
0000000000000000001000010
0000000000000010000100001
0000000000000000000011000
0000000000000000000011100
0000000000000000010001100
0000000000000000001000010
0000000000000000000100001
$ connect s1
25 25
islands s1
┌───────────────────────────────────────────┬─┬───┬────────┬─────┐
│0 2 3 4 5 6 7 10 12 13 14 17 19 20 21 22 24│1│8 9│11 15 16│18 23│
└───────────────────────────────────────────┴─┴───┴────────┴─────┘
All Possibilities
check makes possible a brute force solver: Generate an array of all possibilities and then choose the one that "checks-out".
If y is a partially solved puzzle, the number of cells remaining to be colored is n=.+/,y=FREE ; of these, m=.(+/,0>.y)-+/,(0<y)+.y=WHITE cells are white. Therefore, the number of possibilities is bounded by m!n .
] t=: init n1 _2 1 _2 _2 _2 _2 _2 _2 _2 2 _2 _2 _2 _2 _2 3 _2 _2 _2 _2 _2 _2 _2 2 _2 ] n=: +/,t=FREE 21 ] m=: (+/,0>.t) - +/,(0<t)+.t=WHITE 4 m!n 5985 wf=: 3 : 0 NB. # white cells, # free cells t=. ,y m=. (+/0>.t)-+/(0<t)+.t=WHITE n=. +/t=FREE m,n ) wf t 4 21 !/ wf t 5985
Another approach is to check all colorings of the n non-numbered cells. It is less efficient because 2^n is much bigger than m!n .
comb=: 4 : 0 NB. All size x combinations of i.y
k=. i.>:d=.y-x
z=. (d$<i.0 0),<i.1 0
for. i.x do. z=. k ,.&.> ,&.>/\. >:&.> z end.
; z
)
bf=: 3 : 0 NB. brute force solver
t=. ,y
b=. t=FREE
'm n'=. wf t
t=. ($y) $"1 (t*-.b) +"1 b #^:_1"1 ((i.n) e."1 m comb n){BLACK,WHITE
t {~ (check :: 0:"2 i. 1:) t
)
see bf init n1 ┌─┬─┬─┬─┬─┐ │X│1│X│X│X│ ├─┼─┼─┼─┼─┤ │X│X│X│ │2│ ├─┼─┼─┼─┼─┤ │X│ │X│X│X│ ├─┼─┼─┼─┼─┤ │3│ │X│ │X│ ├─┼─┼─┼─┼─┤ │X│X│X│2│X│ └─┴─┴─┴─┴─┘
Heuristics
The number of possibilities can be reduced by applying some heuristics. Heuristics are a reasonable approach as Nurikabe is NP-complete by reduction from Boolean circuits.
- Set to black cells too far from a numbered cell. h2far
- Set to white the free cell of a 2x2 block with 3 black cells. h22
- If a 2-cell has only two possibilities for a white neighbor, and the three cells together form an "L", then set to black the neighbor of the two limbs of the "L". h2ell
- Set to black neighbors of complete white islands. hislands
- Set to white the only free neighbor of an incomplete white island surrounded by blacks. hislands
- Set to black the only free neighbor of a black island, if there is more than one black island. hislands
- Set to black a free cell neighboring >1 numbered white islands. hislands
- Set to x cells of a free island surrounded by x cells. hislands
- Set to black all free cells if no white cells are left. hendgame
- Set to white all free cells if the number of missing white cells equals the number of free cells hendgame
The implementation of these heuristics can be found in Collected Definitions below.
t3=: hislands t2=: h22 t1=: h2far t=: init n1 q=: t;t1;t2;t3 see&.> q ┌───────────┬───────────┬───────────┬───────────┐ │┌─┬─┬─┬─┬─┐│┌─┬─┬─┬─┬─┐│┌─┬─┬─┬─┬─┐│┌─┬─┬─┬─┬─┐│ ││?│1│?│?│?│││X│1│X│X│?│││X│1│X│X│?│││X│1│X│X│X││ │├─┼─┼─┼─┼─┤│├─┼─┼─┼─┼─┤│├─┼─┼─┼─┼─┤│├─┼─┼─┼─┼─┤│ ││?│?│?│?│2│││?│X│X│?│2│││?│X│X│ │2│││X│X│X│ │2││ │├─┼─┼─┼─┼─┤│├─┼─┼─┼─┼─┤│├─┼─┼─┼─┼─┤│├─┼─┼─┼─┼─┤│ ││?│?│?│?│?│││?│?│X│X│?│││?│ │X│X│?│││?│ │X│X│X││ │├─┼─┼─┼─┼─┤│├─┼─┼─┼─┼─┤│├─┼─┼─┼─┼─┤│├─┼─┼─┼─┼─┤│ ││3│?│?│?│?│││3│?│?│?│X│││3│?│?│?│X│││3│?│?│?│X││ │├─┼─┼─┼─┼─┤│├─┼─┼─┼─┼─┤│├─┼─┼─┼─┼─┤│├─┼─┼─┼─┼─┤│ ││?│?│?│2│?│││?│?│?│2│?│││?│?│?│2│?│││?│?│?│2│?││ │└─┴─┴─┴─┴─┘│└─┴─┴─┴─┴─┘│└─┴─┴─┴─┴─┘│└─┴─┴─┴─┴─┘│ └───────────┴───────────┴───────────┴───────────┘ wf&.> q ┌────┬────┬────┬───┐ │4 21│4 13│2 11│2 8│ └────┴────┴────┴───┘ !/@wf&> q 5985 715 55 28
For the n1 puzzle application of the heuristics h2far , h22 , and hislands reduces the number of possibilities from 5985 to 715 to 55 to 28.
heuristics=: hendgame @ (hislands @ h2ell @ h22 ^:_) @ h2far
bfh=: bf @ heuristics @ init
NB. brute force with heuristics
see bfh n1
┌─┬─┬─┬─┬─┐
│X│1│X│X│X│
├─┼─┼─┼─┼─┤
│X│X│X│ │2│
├─┼─┼─┼─┼─┤
│X│ │X│X│X│
├─┼─┼─┼─┼─┤
│3│ │X│ │X│
├─┼─┼─┼─┼─┤
│X│X│X│2│X│
└─┴─┴─┴─┴─┘
see bfh n7
|out of memory: comb
| z=.k,.&.> ,&.>/\.>:&.>z
see t=: heuristics init n7
┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│?│?│?│?│5│?│?│?│?│?│?│?│?│?│ │ │ │ │X│X│X│X│?│?│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
│?│?│X│?│?│?│?│?│?│?│2│X│6│?│?│X│X│7│X│3│ │?│?│4│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
│?│X│1│X│?│?│?│5│?│?│?│?│?│?│?│?│3│X│5│X│?│?│X│X│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
│?│7│X│?│?│6│?│?│?│?│?│?│?│?│?│?│?│X│ │?│?│?│X│1│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
│?│?│?│X│?│?│?│?│4│?│X│?│?│?│?│?│?│?│?│?│?│?│?│X│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
│?│?│X│1│X│?│?│?│?│X│1│X│?│?│5│?│?│?│?│?│?│3│?│?│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
│?│?│2│X│?│3│?│?│?│?│X│?│?│?│?│?│?│?│?│?│?│?│?│?│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
│?│X│?│?│?│?│?│?│3│?│?│?│3│?│?│?│2│?│?│7│?│?│?│?│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
│?│?│?│?│X│?│?│?│?│?│?│?│?│?│?│?│?│X│?│?│?│?│?│?│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
│6│?│?│X│1│X│?│?│?│5│?│?│?│5│?│?│X│1│X│?│?│X│5│?│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
│?│?│?│?│X│?│6│?│?│?│?│?│?│?│?│5│?│X│?│?│?│3│X│?│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
│?│?│?│4│?│?│?│?│?│?│?│?│X│?│?│?│?│?│?│4│?│?│?│?│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
│?│5│?│?│?│?│?│?│?│X│?│X│1│X│?│?│?│?│?│?│?│?│?│?│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
│?│?│?│?│?│?│?│?│3│X│4│?│X│?│?│?│5│?│?│?│?│X│?│X│
└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
wf t
106 244
106 ! 244
1.77394e71
For the n7 puzzle the number of remaining possibilities is too large to be practically computable by brute force. More heuristics are required.
Collected Definitions
Solver
WHITE=: 0
BLACK=: _1
FREE =: _2
init =: + FREE*0=]
see =: 3 : 'y { _1|.(":&.>1+i.>./,y),<"0 ''?X '''
connect=: 3 : 0 NB. connection matrix for Nurikabe
s=. WHITE<.y
i=. I., (}.=}:) s
j=. I., 0,.~(}."1 = }:"1) s
(+.|:) 1 (<"1 (i+/0,{:$y),j+/0 1)}=i.*/$y
)
tc=: +./ .*~^:(>.@(2&^.)@#)
NB. transitive closure of a reflexive graph
islands=: ~. @ (<@I."1"_) @ tc @ connect
NB. connected components
check=: 3 : 0 NB. 1 iff y is a Nurikabe solution
assert. (y e. BLACK,WHITE) +. 0<y
assert. -. 2 2 (2 2$BLACK)&-:;._3 y
c=. islands y
assert. (#c) = 1++/,0<y
i=. c{&.><,y
n=. #&>i
b=. i = n$&.><BLACK
assert. 1=+/b
assert. b +. *./@(0&<:)&>i
assert. b +. 1 = +/@(0&<)&>i
assert. b +. n = +/&>i
1
)
wf=: 3 : 0 NB. # white cells, # free cells
t=. ,y
m=. (+/0>.t)-+/(0<t)+.t=WHITE
n=. +/t=FREE
m,n
)
comb=: 4 : 0 NB. All size x combinations of i.y
k=. i.>:d=.y-x
z=. (d$<i.0 0),<i.1 0
for. i.x do. z=. k ,.&.> ,&.>/\. >:&.> z end.
; z
)
bf=: 3 : 0 NB. brute force solver
t=. ,y
b=. t=FREE
'm n'=. wf t
t=. ($y) $"1 (t*-.b) +"1 b #^:_1"1 ((i.n) e."1 m comb n){BLACK,WHITE
t {~ (check :: 0:"2 i. 1:) t
)
heuristics=: hendgame @ (hislands @ h2ell @ h22 ^:_) @ h2far
bfh=: bf @ heuristics @ init
NB. brute force with heuristics
Heuristics
h2far=: 3 : 0 NB. set to black cells too far from a numbered cell
i=. ($y)#:I.,_2=y
j=. ($y)#:I.,1<y
b=. (i +/@:|@:-"1/ j) */ .>: (1<y)#&,y
p=. (i.$y) e. ($y)#.b#i
(p*BLACK) + y*-.p
)
neighborhood=: 3 3 ,;._3 [,.([,],[),.[
NB. neighborhood of each atom in y, bordering y by x
h22=: 3 : 0 NB. set to white the free cell of a 2x2 block with 3 black cells
p=. (FREE=y) *. +./"1 (=i.4) e.~ (,/2 2 ,;._3 i.3 3) {"2 1 (BLACK,FREE) i. WHITE neighborhood y
(p*WHITE) + y*-.p
)
NB. If a 2-cell has only two possibilities for a white neighbor,
NB. and the three cells together form an "L",
NB. then set to black the neighbor of the two limbs of the "L".
h2ell=: 3 : 0
k=. #: 12 10 5 3
t=. FREE = (* (2=4{"1]) * (k{BLACK,FREE) e.~ 1 3 5 7{"1 ]) ,/ BLACK neighborhood y
i=. I. -. t-:"1 (9$0)
j=. (k i.(<i;1 3 5 7){t){(-1 _1+n),_1 1+n=. {:$y
p=. (i.$y) e. i+j
(p*BLACK) + y*-.p
)
NB. set to black neighbors of complete white islands
NB. set to white the only free neighbor of an incomplete white island surrounded by blacks
NB. set to black the only free neighbor of a black island, if there is more than one black island
NB. set to black a free cell neighboring >1 numbered white islands
NB. set to x cells of a free island surrounded by x cells
hislands=: 3 : 0
N=. 1 3 5 7 {"1 ,/_1 neighborhood i.$y NB. neighbors for each cell
t=. islands y NB. islands
c=. t{&.><,y NB. corresp. colors
n=. (t ,@:{&.> <N) ~.@-.&.> _1,&.>t NB. neighbors of each island
d=. n{&.><,y NB. corresp. colors
s=. (#&>c) (= * 0<]) +/&>c NB. for white islands, 1 iff complete
y=. BLACK i"_} y [ i=. ;p#n [ p=. w * s [ w=. WHITE<:{.&>c
y=. WHITE i"_} y [ i=. ((p#d)i.&>FREE){&>p#n [ p=. w * s < (FREE e.&>d) * (<:#&>d)=+/@(BLACK&=)&>d
y=. BLACK i"_} y [ i=. ((p#d)i.&>FREE){&>p#n [ p=. (1=+/@(FREE&=)&>d) (* * 1<+/@]) BLACK={.&>c
y=. BLACK i"_} y [ i=. (I.FREE=,y) (e.#[) (-.@~: # ]) ;n#~0<+/&>c
y=. BLACK i"_} y [ i=. ; t #~ f * */@(BLACK&=)&>d [ f=. FREE={.&>c
y=. WHITE i"_} y [ i=. ; t #~ f * WHITE=<./&>d
)
NB. set to black all free cells if no white cells are left
NB. set to white all free cells if # missing white cells equals # free cells
hendgame=: 3 : 0
c=. wf y
(p*i{BLACK,WHITE,FREE) + y*-.p=. (FREE=y)*2>i=. ((0={.c),=/c)i.1
)
NB. apply heuristics and pick a cell that can be colored
NB. the result is (i,j,COLOR), or '' if no hints are available
hint=: 3 : 0
if. -. y -: h=. h2far y do. h ijv y~:h return. end.
if. -. y -: h=. h22 y do. h ijv y~:h return. end.
if. -. y -: h=. h2ell y do. h ijv y~:h return. end.
if. -. y -: h=. hislands y do. h ijv y~:h return. end.
if. -. y -: h=. hendgame y do. h ijv y~:h return. end.
''
)
ijv=: 4 : '(, x {~ <) ($y) #: (?@# { ]) I.,y'
NB. (row,column,value) in x of a cell having value 1 in boolean y
Puzzles
n1=: ".;._2 (0 : 0)
0 1 0 0 0
0 0 0 0 2
0 0 0 0 0
3 0 0 0 0
0 0 0 2 0
)
n2=: ".;._2 (0 : 0)
0 0 0 0 2
0 0 2 0 0
0 0 0 0 0
0 0 2 0 0
2 0 0 0 0
)
n3=: ".;._2 (0 : 0)
0 0 0 0 0
3 0 0 0 0
0 1 0 2 0
0 0 0 0 5
0 0 0 0 0
)
n4=: ".;._2 (0 : 0)
0 5 0 0 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
2 0 0 1 0
)
n5=: ".;._2 (0 : 0)
0 0 1 0 5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
7 0 1 0 0
)
n6=: ".;._2 (0 : 0) NB. Sample problem 6 ("medium") by OX from the Nikoli page
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 12 0 0 0 0 0 3 0 12 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2
2 0 0 0 0 3 0 0 0 0 0 3 0 0 0 0 3 0
0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0
3 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 2 0 0 2 0 3 0 2 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12 0 1
)
n7=: ".;._2 (0 : 0) NB. Sample problem 7 ("hard") by Takei Daisuke from the Nikoli page
0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 2 0 6 0 0 0 0 7 0 3 0 0 0 4
0 0 1 0 0 0 0 5 0 0 0 0 0 0 0 0 3 0 5 0 0 0 0 0
0 7 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 1 0 0 0 5 0 0 0 0 0 0 3 0 0
0 0 2 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 3 0 0 0 3 0 0 0 2 0 0 7 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 0 0 0 1 0 0 0 0 5 0 0 0 5 0 0 0 1 0 0 0 0 5 0
0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 5 0 0 0 0 0 3 0 0
0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0
0 5 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 3 0 4 0 0 0 0 0 5 0 0 0 0 0 0 0
)
See also
- Addons/games/nurikabe a Nurikabe game player
- http://en.wikipedia.com/wiki/Nurikabe
- http://www.logicgamesonline.com/nurikabe/
- http://www.nikoli.com/en/puzzles/nurikabe/
Contributed by Roger Hui.