Nurikabe (joc)

Nurikabe

Tipus	joc NP-complet i trencaclosques de lògica

El nurikabe (japonès: ぬりかべ o mur invisible) és un trencaclosques de col·locació, de l'estil del sudoku, que requereix només paciència i l'aplicació lògica d'una sèrie de regles. Aparentment, Nikoli ha inventat i donat el nom a aquest joc, que va aparèixer publicat per primera vegada el 1991. El nom del joc, nurikabe, és el d'un esperit de la mitologia japonesa, un mur invisible que barra el pas en un camí.

Regles

El joc es juga típicament en una àrea rectangular quadriculada en cel·les. Algunes de les cel·les contenen números. L'objectiu del joc és pintar determinades cel·les per acabar construint una figura contínua (segons la metàfora que fem servir, un camí o un riu) que ha de seguir aquestes regles:

• Qualsevol cel·la ha d'acabar formant part o bé d'una paret (o illa) o bé del camí (o riu). Les parets del camí (o les illes del riu) es formen amb blocs de cel·les contigües. Les parets (o illes) no es poden tocar costat per costat, però sí en diagonal o pels vèrtexs.

• Els números indiquen quantes cel·les ha de tenir exactament una paret (o illa), incloent-hi la cel·la del número. Cada paret (o illa) només pot contenir un número.

• El camí (o riu) ha d'acabar formant un sol continu (amb tantes ramificacions com calgui) i totes les seves cel·les han d'estar connectades costat per costat almenys amb una altra.

• El camí (o riu) no pot tenir blocs de 2 x 2 cel·les, és a dir, no poden haver-hi sales (ni llacs). Per altra banda, les parets (o illes) sí que poden tenir blocs de 2 x 2 cel·les o qualsevol altra forma.

Típicament, els jugadors marquen amb un punt les cel·les no numerades que ja s'ha determinat que han de ser parets, i ombregen les cel·les que ja s'ha determinat que han de ser part del camí continu. Per això, les cel·les de les parets també s'anomenen blanques i les del camí s'anomenen negres.

Solució

Com en altres trencaclosques de pura lògica, s'espera una única solució, i una quadrícula amb números a l'atzar és molt improbable que proporcioni un trencaclosques nurikabe amb una única solució.

Per a solucionar un nurikabe no s'ha d'intentar endevinar, sinó que cal seguir una sèrie de procediments i regles ben simples, assumint que el jugador és prou despert per a trobar on cal aplicar cadascuna.

L'errada més comuna dels jugadors novells és concentrar-se en determinar només cel·les negres o cel·les blanques, quan la majoria de nurikabe requereixen canviar alternativament de procediment. Per exemple, marcar alguna cel·la blanca pot comportar marcar-ne alguna altra de negra perquè no quedi aïllada, i recíprocament. Curiosament, la regla més fàcil d'oblidar és la més bàsica: totes les cel·les han de ser o bé negres o bé blanques, de manera que si es pot provar que una cel·la no pot ser d'una mena llavors ha de ser de l'altra.

Estratègia bàsica

Un nurikabe tal com el soluciona un humà. Els punts representen les cel·les considerades blanques.

• Les cel·les que queden entre dues illes incompletes (cel·les amb números i cel·les blanques adjacents) han de ser negres, ja que dues illes només es poden tocar diagonalment. Sovint aquesta és la manera de començar un nurikabe, marcant com negres les celles adjacents a dos o més números.

• Quan es completa una illa (quan ja conté tantes cel·les blanques com requereix el seu número), totes les cel·les que hi toquen de costat han de ser negres. Òbviament, qualsevol cel·la amb un '1' és una illa completa ja d'entrada, i ja es poden aïllar amb quatre negres al voltant de bon principi.

Exemple: si la cel·la central conté '1', les quatre al voltant seu han de ser negres:

	1

• Quan tres cel·les negres formen un angle en L o colze, la quarta cel·la que queda envoltada ha de ser blanca, altrament es formaria una sala o llac (que no pot ser d'acord amb la regla que no permet àrees negres de 2 x 2).

Exemple: si A, B, C són negres, llavors X no pot ser negre, X ha de ser blanc:

A	B
C	X

• Totes les cel·les negres han d'acabar connectades. Per tant, si queda una regió negra amb una única manera possible de connectar-se a la resta d'àrees negres, llavors aquest únic camí de connexió ha de ser negre.

• Totes les cel·les blanques han d'acabar formant part d'una illa en particular. Per tant, si queda una àrea blanca sense número amb una única manera possible de connectar-se a una regió numerada blanca, llavors aquest únic camí de connexió ha de ser blanc.

• Per a solucionar alguns trencaclosques caldrà determinar cel·les inabastables (cel·les que no es poden connectar amb cap número, o bé per ser massa lluny de cap d'ells o bé per tenir l'accés bloquejat per altres números). Aquestes cel·les inabastables han de ser negres. Sovint resoldre aquestes cel·les remotes permetrà continuar progressant cap a la solució, potser perquè només tindran un únic camí de connexió a la resta de cel·les negres, o potser formaran algun colze que requerirà donar per blanca la seva quarta cel·la i que potser només es pot connectar amb una àrea numerada determinada, etc.

Estratègia avançada

• Si hi ha una àrea quadrada amb dues cel·les negres i dues cel·les desconegudes, almenys una de les dues desconegudes ha de quedar blanca (d'acord amb la regla que no permet àrees negres de 2 x 2). Així que si una de les dues cel·les desconegudes (diguem-li 'X') només es pot connectar amb una cel·la numerada a través de l'altra cel·la desconeguda (diguem-li 'Y'), llavors Y ha de ser necessàriament blanca (ara bé, X tant podria ser blanca com negra).

Exemple: Si A i B són negres, llavors almenys un de X o Y ha de ser blanc. Si a més cal connectar amb F blanc, llavors Y ha de ser també blanc:

A	B
X?	Y?	F

• Si una illa de mida N ja té N-1 cel·les blanques identificades, i només queden dues cel·les per poder triar quina és la que falta, i aquestes dues cel·les desconegudes es toquen per una punta (en diagonal), llavors la cel·la per on es toquen, a la banda més lluny de l'illa, ha de ser necessàriament negra.

Exemple: Si A i B són blancs, i per acabar la seva illa només falta per decidir una cel·la que pot ser X o Y, llavors Z ha de ser negre, perquè almenys un de X o Y ha de ser blanc:

A	B	X?
	Y?	Z

• Com a corol·lari de l'anterior, per a qualsevol cel·la que conté '2', si dos costats contigus ja s'han identificat com a negres, la cel·la al vèrtex oposat ha de ser negra.

Exemple: Si la cel·la central conté '2', i A i B són negres, llavors X ha de ser negre:

	A
?	2	B
X	?

• Un altre exemple: Si la cel·la amb 3 està arraconada, o bé A o bé B o bé tots dos han de ser blancs, per tant, davant de la cel·la amb 2, la cel·la X ha de ser negra:

2
X?	A
B	3

Enllaços externs

• Pàgina sobre Nurikabe de Nikoli, en anglès Arxivat 2007-06-20 a Wayback Machine.
• Nurikabe is NP-Complete Arxivat 2011-06-09 a Wayback Machine. (en anglès) (cal Adobe Acrobat Reader)