Ice Walk is ASP-Complete

2026/07/24 by Papangkorn Apinyanon
Computer Science · #cs.CC

paper · pdf

Abstract

We prove that the solution-search problem for the pencil puzzle Ice Walk is ASP-complete. Our reduction maps Hamiltonian cycles in an undirected maximum-degree-3 spanning subgraph of a rectangular grid graph bijectively to Ice Walk solutions.

Related

• NP-Completeness Proofs of All or Nothing and Water Walk Using the T-Metacell Framework
• ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles
• Polynomial solvability of NP-complete problems
• ASP-Completeness Proofs of Puzzles Using the T-Metacell Framework
• Solving the Rubik's Cube Optimally is NP-complete