Hashiwokakero
Hashiwokakero, o simplement Hashi, és un passatemps creat per l'editora japonesa Nikoli, especialitzada en jocs lògics i trencaclosques i que és mundialment coneguda per haver popularitzat el sudoku.[1] El nom prové del japonès Hashi o kakero, que vol dir "construeix ponts". També ha estat publicat en anglès amb el nom Bridges (ponts) o Chopsticks (escuradents) degut a una mala traducció de la paraula japonesa Hashi, que pot tenir ambdós significats. La revista The Times en publica regularment amb el nom de Hashi, i a França, Dinamarca, els Països Baixos i Bèlgica es publica sota el nom d'Ai-Ki-Ai.
Normes[modifica]
Hashiwokakero es juga a una graella rectangular sense una mida estàndard, tot i que la graella no s'acostuma a dibuixar. Algunes cel·les contenen nombres encerclats de l'1 al 8 inclosos, que reben el nom de 'illes'. La resta de cel·les estan buides.
L'objectiu del joc és connectar totes les illes dibuixant una sèrie de ponts entre elles. Els ponts han de seguir certs criteris:[2]
- Han de començar i acabar en illes diferents, recorrent una línia recta.
- No poden creuar cap altre pont ni illa.
- Només poden ser ortogonals, no diagonals.
- Com a màxim dos ponts poden connectar el mateix parell d'illes.
- El nombre total de ponts connectats a cada illa han de coincidir amb el nombre d'aquesta.
- En la graella final, tots els ponts han de connectar les illes formant un únic grup connex.
Generalment, els Hashiwokakero han de tenir una solució única per ser considerats vàlids.[1]
Mètodes de resolució[modifica]
Resoldre un Hashiwokakero és una qüestió de força procedimental: un cop determinat on s'ha de col·locar un pont, col·locar-lo allà pot eliminar altres llocs possibles per als ponts, forçant la col·locació d’un altre pont, i així successivament.[3]
Una illa que mostri un 3 en una cantonada, 5 al llarg de la vora exterior o 7 en qualsevol lloc ha de tenir almenys un pont que surti des de cada direcció vàlida. Una illa amb un 4 a la cantonada, 6 a la vora o 8 a qualsevol lloc ha de tenir dos ponts a cada direcció. Això es pot generalitzar al afegir més ponts que obstrueixen possibles rutes, fent que illes a l'interior de la graella ja no puguin tenir ponts en algunes de les direccions.
És una pràctica habitual marcar aquelles illes amb la quota de ponts assolida.[2] Això ajuda a reduir els errors i a localitzar els circuits potencials: tenint en compte que totes les illes han d’estar connectades per una xarxa de ponts, un pont que crearia una xarxa tancada a la qual no es podrien afegir més ponts només es pot permetre si dona immediatament la solució al trencaclosques complet. També es pot descartar cap pont que aïllés completament un grup d'illes d'un altre grup, ja que es dividiria la graella en dos grups d'illes que no podrien connectar-se.
Resolució computacional[modifica]
Determinar si un Hashiwokakero té solució i si aquesta és única és NP-complet, mitjançant una reducció de la cerca de cicles hamiltonians en grafs de distància de la unitat de coordenades enteres.[4] També es pot resoldre utilitzant programació lineal entera.[5]
Història[modifica]
Hashiwokakero es va presentar per primera vegada en el nº31 de la revista Puzzle Communication Nikoli (setembre de 1990), tot i que anteriorment una versió més senzilla del trencaclosques havia aparegut en el nº28 (desembre de 1989).
Referències[modifica]
- ↑ 1,0 1,1 Puzzle Cyclopedia, Nikoli, 2004. ISBN 4-89072-406-0
- ↑ 2,0 2,1 Wanko, Jeffrey J. «Deductive Puzzling». Mathematics Teaching in the Middle School, 15, 9, 2010, p. 524–529.
- ↑ Malik, Reza Firsandaya; Efendi, Rusdi; Pratiwi, Eriska Amrina «Solving Hashiwokakero puzzle game with Hashi solving techniques and depth first search». Bulletin of Electrical Engineering and Informatics, 1, 1, març 2012, p. 61–68. DOI: 10.11591/eei.v1i1.227.
- ↑ Andersson, Daniel «Hashiwokakero is NP-complete». Information Processing Letters, 109, 19, 2009, p. 1145–1146. DOI: 10.1016/j.ipl.2009.07.017.
- ↑ Coelho, L.C.; Laporte, G. & Lindbeck, A. et al. (2019), "Benchmark instances and branch-and-cut algorithm for the Hashiwokakero puzzle", arΧiv:1905.00973 [cs.DM]
Enllaços externs[modifica]
- Secció de Hashiwokakero a la pàgina de Nikoli Arxivat 2020-09-19 a Wayback Machine. (anglès)