Generating rationally solvable instances of NP-hard logic puzzles

Abstract

Nurikabe, en form for logisk hjerntrim oppkalt etter en ånd fra japansk folklore, er et underholdende og enagsjerende tidsfordriv. I likhet med mange lignende spill er det dessuten NP-hardt i sin generelle form. I denne oppgaven har kompleksiteten til Nurikabe blitt undersøkt, både i dets generelle form og i dets mer spesifikke, løsbare form som ofte er brukt i aviser og lignende. Videre har mulgheten for å utvikle en generasjonsalgoritme, i stand til å generere løsbare Nurikabe-brett, blitt undersøkt og diskutert.

For å utføre disse undersøkelsene ble et sett med teknikker, som kan brukes til å løse Nurikabe-brett, bestemt. Basert på disse har en prototype Nurikabe generator blitt utviklet, ved hjelp av programmeringsspråket Haskell. En web-app som forenkler bruken av denne generatoren har også blitt utviklet, i tillegg til en app som lar brukere løse Nurikabe-brett. Begge disse er utviklet ved hjelp av programmeringsspråket C\#.

Den utviklede generatoren har vist seg i stand til å generere brett av ikke-triviell vanskelghetsgrad, som dessuten er garantert å være unikt løsbare for mennesker, ved hjelp av de etablerte teknikkene.

Den utviklede appen har videre vist seg i stand til å la brukere løse Nurikabe-brett av enhver størrelse på en intuitiv og brukervennlig måte.

For å konkludere har altså arbeidet med dette prosjektet vist at generasjon av Nurikabe-brett som er løsbare for mennesker uten tvil er mulig. Brukbarheten til en slik generator avhenger likevel i stor grad av størrelsen til brettet som genereres, ettersom kompleksiteten til Nurikabe-problemet gjør det vanskelig å holde generatoren effektiv.

Nurikabe, a pen-and-paper logic puzzle named for a spirit from japanese folklore, is an entertaining pastime that benefits the brain. Like many other similar puzzles it is also NP-Hard in its general form. In this project, the computational complexity of Nurikabe has been investigated, both in its general form, and in its more specific, solvable form, which is how it is commonly presented in newspapers and the like. Furthermore, the possibility of developing a generator algorithm capable of generating solvable instances of Nurikabe has also been investigated and discussed.

To perform these investigations, a set of techniques that can be used to solve Nurikabe boards has been established. Based on these, a prototype Nurikabe generator has been developed, using the Haskell programming language. A web app that simplifies the use of this generator has also been developed, as well as an app that allows users to solve Nurikabe puzzles. These were both developed using the C\# programming language.

The developed generator has been proven to be able to generate puzzles of non-trivial difficulty, that are furthermore guaranteed to be uniquely solvable to humans, using the established techniques.

Likewise, the developed app has been proven to allow solution of Nurikabe puzzles of any size, in an intuitive and user-friendly way.

To conclude, implementing a generator capable of generating Nurikabe puzzles solvable to a human solver is most definitely possible. The usability of such a generator is however much dependent on the size of the boards being generated, as the computational complexity of the Nurikabe problem makes keeping the generator performant a challenge.