Hashiwokakero
Hashiwokakero (橋をかけろ Hashi o kakero ; lit. "bygga broar!") är en typ av logikpussel publicerad av Nikoli . Den har också publicerats på engelska under namnet Bridges or Chopsticks (baserat på en felöversättning: titelns hashi , 橋 , betyder bro ; hashi skriven med ett annat tecken, 箸 , betyder ätpinnar ). Den har också dykt upp i The Times under namnet Hashi . I Frankrike , Danmark , Nederländerna och Belgien publiceras den under namnet Ai-Ki-Ai .
Regler
Hashiwokakero spelas på ett rektangulärt rutnät utan standardstorlek, även om själva rutnätet vanligtvis inte ritas. Vissa celler börjar med (vanligtvis inringade) siffror från 1 till 8 inklusive; dessa är "öarna". Resten av cellerna är tomma.
Målet är att koppla ihop alla öarna genom att rita en serie broar mellan öarna. Broarna måste följa vissa kriterier:
- De måste börja och sluta vid distinkta öar, som går en rak linje emellan.
- De får inte korsa några andra broar eller öar.
- De får bara löpa ortogonalt (dvs de får inte löpa diagonalt).
- Som mest två broar förbinder ett par öar.
- Antalet broar som är anslutna till varje ö måste matcha antalet på den ön.
- Broarna måste koppla samman öarna till en enda sammankopplad grupp.
Lösningsmetoder
Att lösa ett Hashiwokakero -pussel är en fråga om processuell kraft: att ha bestämt var en bro måste placeras, placera den där kan eliminera andra möjliga platser för broar, tvinga fram en annan bro, och så vidare.
En ö som visar '3' i ett hörn, '5' längs ytterkanten eller '7' var som helst måste ha minst en bro som strålar ut från den i varje giltig riktning, för om en riktning inte hade en bro, även om alla andra riktningar hade två broar, inte tillräckligt kommer att ha placerats. En "4" i ett hörn, "6" längs gränsen eller "8" var som helst måste ha två broar i varje riktning. Detta kan generaliseras eftersom tillagda broar hindrar rutter: en "3" som endast kan färdas från vertikalt måste ha minst en bro vardera för upp och ner, till exempel.
Det är vanligt att kryssa av eller fylla i öar vars brokvot har uppnåtts. Förutom att minska misstag kan detta också hjälpa till att lokalisera potentiella "kortslutningar": med tanke på att alla öar måste vara sammankopplade med ett nätverk av broar, en bro som skulle skapa ett slutet nätverk som inga ytterligare broar kan läggas till kan bara tillåts om det omedelbart ger lösningen på hela pusslet. Det enklaste exemplet på detta är två öar som visar '1' i linje med varandra; såvida de inte är de enda två öarna i pusslet, kan de inte kopplas samman med en bro, eftersom det skulle slutföra ett nätverk som inte kan läggas till, och skulle därför tvinga dessa två öar att vara oåtkomliga för andra.
Varje bro som helt skulle isolera en grupp öar från en annan grupp skulle inte vara tillåten, eftersom man då skulle ha två grupper av öar som inte kunde ansluta. Detta avdrag är dock inte särskilt vanligt i Hashiwokakero- pussel.
Att avgöra om ett Hashiwokakero-pussel har en lösning är NP-komplett , genom en minskning från att hitta Hamiltonska cykler i heltal- koordinatenhetsdistansgrafer . Det finns en lösning som använder linjär heltalsprogrammering i MathProg-exemplen som ingår i GLPK . Ett bibliotek med pussel som räknar upp till 400 öar samt heltals linjära programmeringsresultat rapporteras också.
Historia
Hashiwokakero dök först upp i Puzzle Communication Nikoli i nummer 31 (september 1990), även om en tidigare form av pusslet dök upp i nummer 28 (december 1989).