Tatami Printer: Physical ZKPs for Tatami Puzzles

Abstract

Tatami puzzles are pencil puzzles with an objective to partition a rectangular grid into rectangular regions such that no four regions share a corner point, as well as satisfying other constraints. In this paper, we develop a physical card-based protocol called Tatami printer that can help verify solutions of Tatami puzzles. We then use the Tatami printer to construct zero-knowledge proof protocols for two such puzzles: Tatamibari and Square Jam. These protocols enable a prover to show a verifier the existence of the puzzles' solutions without revealing them.

arXiv commentThis paper has appeared at CIAC 2025

References in corpus (5)

• Physical Zero-Knowledge Proof for Numberlink Puzzle and $k$ Vertex-Disjoint Paths Problem
• Physical Zero-Knowledge Proof for Ripple Effect
• An Improved Physical ZKP for Nonogram and Nonogram Color
• Printing Protocol: Physical ZKPs for Decomposition Puzzles
• Verifying the First Nonzero Term: Physical ZKPs for ABC End View, Goishi Hiroi, and Toichika