Exploring NP-Completeness Proofs in Pencil Puzzles: The Case of Nondango
Delve into the realm of NP-Completeness proofs within pencil puzzles through the intriguing case of Nondango. Unravel the challenge of coloring circles in a rectangular grid to meet specific criteria, showcasing the complexity and depth of this puzzle type.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Nondango is NP-Complete Suthee Ruangwises The University of Electro-Communications, Tokyo, Japan EuroCG 2023 Ioannina, Greece March 13, 2024 1
Pencil Puzzles Sudoku Makaro Kakuro Bridges Hitori Slitherlink etc. 3
NP-Completeness Proof Yajilin Country Road Nonogram Ueda and Nagao 1996 Ishibashi et al. 2012 Bag Friedman 2002 Kurodoko K lker 2012 Masyu Friedman 2002 Shakashaka Shikaku Ripple Effect Demaine et al. 2013 Tentai Show Friedman Sudoku Kakuro Slitherlink 2002 Takenaga et al. 2013 Yato and Seta 2003 Yosenabe Iwamoto 2014 Numberlink Adcock et al. 2015 Nurikabe Holzer et al. 2004 Fillmat Satogaeri Hebi Slalom Uejima and Suzuki 2015 Kanehiro and Takenaga Akari McPhail 2005 Goishi Hiroi Andersson 2007 2015 Heyawake Holzer and Ruepp 2007 Iwamoto and Matsui Bridges Andersson Hearn and Demaine 2009 Skyscrapers 2016 Hitori 2009 = Nikoli original 4
NP-Completeness Proof Nurimisaki Sashigane Pipelink Norinori LITS Uejima et al. 2017 Iwamoto and Ide 2020 Biro and Schmidt 2017 Irasuto Butter 2021 Sto-stone Allen and Williams 2018 Iwamoto and Haruishi Iwamoto and Ibusuki Yin-Yang Moon-or-Sun Nagareru Nurimeizu Demaine et al. 2021 Usowan 2018 Iwamoto and Ide 2021 Dosun-fuwari 2018 Suguru Robert et al. 2022 Pencils Herugolf Makaro Packer et al. 2018 Roma Five Cells Tilepaint Goergen et al. 2022 Iwamoto et al. 2018 Iwamoto and Ide 2022 Tatamibari Adler et al. 2020 Sumplete R et al. 2023 Creek Kurotto Juosan Uejima and Oe Iwamoto and Ibusuki 2020 Toichika R 2023 Nondango R 2024 2020 = Nikoli original 5
NP-Completeness Proof See suthee.info/npc-puzzles for list of NP- completeness proofs of pencil puzzles. 6
Nondango 7
Nondango Nikoli original pencil puzzle First published in Nikoli vol. 152 8
Nondango Rectangular grid divided into polyominoes called regions Some cells containing a white circle 9
Nondango Objective: Color some circles black such that: 1. Every region has exactly one black circle. 2. No three consecutive (horizontally, vertically, or diagonally) circles have the same color. 11
Our Contribution Prove that deciding if a Nondango instance has a solution is NP-complete. via reduction from the 1-in-3-SAT+ problem 15
1-in-3-SAT+ problem Boolean variables ?1, ,?? Clauses ?1, ,?? ??= ??1 ??2 ??3 Is there an assignment that makes every clause has exactly one True literal? 17
1-in-3-SAT+ problem Variables ?1,?2,?3,?4 Clauses ?1,?2,?3 ?1= ?1 ?2 ?3 ?2= ?1 ?2 ?4 ?3= ?2 ?3 ?4 Assignment ?1= False ?2= True ?3= False ?4= False 18
1-in-3-SAT+ problem Variables ?1,?2,?3,?4 Clauses ?1,?2,?3 ?1= ?1 ?2 ?3 ?2= ?1 ?2 ?4 ?3= ?2 ?3 ?4 Assignment ?1= False ?2= True ?3= False ?4= False 19
Variable columns ?1 ?2 ?3 ?1 some gadgets Clause rows ?2 some gadgets ?3 some gadgets 21
Idea of Reduction Black circle = True White circle = False Exactly 1 literal in each clause is True Exactly 1 circle in each region is black Challenging task: How to force every circle in each column to have the same color? 22
Enforcing Two Circles with Different Colors 30
Connecting Two Clause Rows with Common Variables 34
Filling Empty Area Make each connected empty area into one region, with one circle inside, not touching any boundary. 38
Analysis Transformed Nondango puzzle has a solution the original 1-in-3-SAT+ problem has a solution Polynomial time reduction Nondango is NP-complete. 39
