Card-Based Zero-Knowledge Proof Protocols for the 15-Puzzle and the Token Swapping Problem

The 15-puzzle is a puzzle game played with 15 square tiles numbered from 1 to 15 on a 4 x 4 board. It has been popular for generations because of its simplicity and challenge. The (w x h)-puzzle is a generalization of the 15-puzzle, which is played with wh - 1 square tiles numbered from 1 to wh - 1 on a w x h board. Solving the (w x h)-puzzle is NP-hard, and hence it is valuable to know its solution. In this paper, we apply the concept of zero-knowledge proof to the (w x h)-puzzle. We propose a physical zero-knowledge proof protocol, in which a prover who knows a solution to the (w x h)-puzzle can convince a verifier that the prover knows the solution without revealing any information about it. We also design physical zero-knowledge proof protocols of two token swapping problems closely related to the (w x h)-puzzle.