Permutation Match Puzzles: How Young Tanvi Learned About Computational Complexity

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.