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.