Nurikabi Solver

Authors(2) :-Deepika Dasari Soorasamharan, Pranamita Nanda

Nurikabe is logical puzzle game. Nurikabe puzzle normally has ‘m’ number of rows and ‘n’ number of columns. Even though it is a logical puzzle game, one cannot solve all the puzzles with pure set of logics. Because Nurikabe puzzle is a NP-complete game. Hence some assumptions must be made in order to solve the given puzzle. In this project in order to make this kind of assumptions with set of logics, SAT solver is used. SAT solver is an efficient tool to make the decisions with binary logics. SAT solver will accept only CNF format. So the puzzle rules and solving logics are converted into CNF format and given to SAT solver. Results from the SAT solver are checked with the rules and if the result satisfies the rules, then it is determined that the result as an appropriate solution for the given puzzle. And new Nurikabe puzzles also generated within certain limit in this project. SAT solver is used to generate new puzzles in this project.

Authors and Affiliations

Deepika Dasari Soorasamharan
Velammal Institute of Technology, Panchetti, Tiruvallur District, Tamilnadu, India
Pranamita Nanda
Velammal Institute of Technology, Panchetti, Tiruvallur District, Tamilnadu, India

NP-complete, Conjunctive Normal Form, T Veerarajan, Nurikabe puzzles

  1. http://www.nikoli.com/en/puzzles/nurik abe/
  2. http://www.satlive.org/
  3. Daniel Le Berre: From SAT to SAT4J
  4. Markus Holzer, Andreas Klein and Martin Kutrib: On The NP-Completeness of The Nurikabe Pencil Puzzle and Variants Thereof
  5. http://www.infosun.fim.uni-passau.de/br/lehrstuhl/Kurse/Proseminar ss01/graph_traversals.pdf
  6. http://www.dwheeler.com/essays/minisat-user-guide.html
  7. http://www.sat4j.org/howto.php
  8. Getting started with SAT4J by SAT4j community
  9. http://forge.ow2.org/project/showfiles.p hp?group_id=228
  10. http://www.daniweb.com/software-development/cpp/threads/351065
  11. http://stackoverflow.com/questions/5224877/java-generate-random-range-of-specific-numbers-without-duplication-of-those-num

Glossary SAT

Satisfiability CNF

  • Conjunctive Normal Form GUI
  • Graphical User Interface DFS
  • Depth First Search IDE
  • Integrated Development Environment JDK- Java Development Kit

Publication Details

Published in : Volume 1 | Issue 3 | May-June 2015
Date of Publication : 2015-05-25
License:  This work is licensed under a Creative Commons Attribution 4.0 International License.
Page(s) : 1-14
Manuscript Number : IJSRSET15132
Publisher : Technoscience Academy

Print ISSN : 2395-1990, Online ISSN : 2394-4099

Cite This Article :

Deepika Dasari Soorasamharan, Pranamita Nanda, " Nurikabi Solver, International Journal of Scientific Research in Science, Engineering and Technology(IJSRSET), Print ISSN : 2395-1990, Online ISSN : 2394-4099, Volume 1, Issue 3, pp.1-14, May-June.2015
URL : http://ijsrset.com/IJSRSET15132

Follow Us

Contact Us