Permutation Match Puzzles: How Young Tanvi Learned About Computational Complexity
This paper addresses the solvability and repairability of a new family of combinatorial puzzles, which could be of interest to researchers in discrete mathematics and theoretical computer science.
This paper introduces permutation match puzzles, a grid-based sorting puzzle, and provides a complete characterization of solvable puzzles based on an acyclic constraint graph. For unsolvable puzzles, an O(n) algorithm is presented to compute the minimum label flips for solvability, and a generalized version is shown to be NP-complete.
We study a family of sorting match puzzles on grids, which we call permutation match puzzles. In this puzzle, each row and column of a $n \times n$ grid is labeled with an ordering constraint -- ascending (A) or descending (D) -- and the goal is to fill the grid with the numbers 1 through $n^2$ such that each row and column respects its constraint. We provide a complete characterization of solvable puzzles: a puzzle admits a solution if and only if its associated constraint graph is acyclic, which translates to a simple "at most one switch" condition on the A/D labels. When solutions exist, we show that their count is given by a hook length formula. For unsolvable puzzles, we present an $O(n)$ algorithm to compute the minimum number of label flips required to reach a solvable configuration. Finally, we consider a generalization where rows and columns may specify arbitrary permutations rather than simple orderings, and establish that finding minimal repairs in this setting is NP-complete by a reduction from feedback arc set.