51 citations · 330 across the 30 of their papers we have counts for
7 papers · 1 filter
Wataridori is NP-Complete
Suthee Ruangwises
Wataridori is a pencil puzzle that involves drawing paths in a rectangular grid to connect circles into pairs while satisfying several constraints. In this paper, we prove that dec…
NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
Pakapim Eua-anant, Papangkorn Apinyanon, Thunyatorn Jirachaisri +2
All or Nothing, Water Walk, and Remembered Length are pencil puzzles that involve constructing a continuous loop on a rectangular grid under specific constraints. In this paper, we…
NP-Completeness Proofs of Puzzles using the T-Metacell Framework
Nattapol Kiatchaipipat, Suthee Ruangwises
Pencil puzzles are puzzles that can be solved by writing down solutions on a paper, using only logical reasoning. In this paper, we utilize the "T-metacell" framework developed by…
NP-Completeness and Physical Zero-Knowledge Proofs for Zeiger
Suthee Ruangwises
Zeiger is a pencil puzzle consisting of a rectangular grid, with each cell having an arrow pointing in horizontal or vertical direction. Some cells also contain a positive integer.…
Nondango is NP-Complete
Suthee Ruangwises
Nondango is a pencil puzzle consisting of a rectangular grid partitioned into regions, with some cells containing a white circle. The player has to color some circles black such th…
Sumplete is Hard, Even with Two Different Numbers
Suthee Ruangwises
Sumplete is a logic puzzle famous for being developed by ChatGPT. The puzzle consists of a rectangular grid, with each cell containing a number. The player has to cross out some nu…
An Improved Physical ZKP for Nonogram and Nonogram Color
Suthee Ruangwises
Nonogram is a pencil puzzle consisting of a rectangular white grid where the player has to paint some cells black according to given constraints. In 2010, Chien and Hon constructed…