Sort a Matrix into Snake Order Using Adjacent Swaps

A square board contains each integer from 1 through `n*n` exactly once. Rearrange it into increasing snake order: the first row increases left to right, the second increases right to left, and subsequent rows alternate direction. One operation swaps two orthogonally adjacent cells. Return **any valid sequence** of swaps that produces the target board. Represent each swap as a pair of the two values immediately before that swap. You do not need to minimize the number of operations. ### Constraints & Assumptions - Use `snake_sort_swaps(board)` as a practice function name; a returned sequence contains pairs of integers. - The board is an `n` by `n` permutation of `1..n*n`. For the practice implementation, assume `1 <= n <= 20`. - Adjacency uses the four grid directions. Diagonal swaps are not allowed. - Values are unique, so a pair identifies their current cells unambiguously. Check adjacency at the time of the operation, not at the initial board positions. - Return an empty sequence if the board is already in the target order. - The exercise accepts multiple correct outputs. The examples illustrate valid sequences and do not prescribe a required algorithm or exact output. ### Examples For `[[2,1],[3,4]]`, one valid sequence is `[[2,1],[4,3]]`, producing `[[1,2],[4,3]]`. For `[[1,2,3],[6,5,4],[7,8,9]]`, an empty sequence is valid. ### Clarifying Questions Does the interviewer require a shortest sequence or only a valid one? Are operations represented by values or coordinates? May the input board be modified while constructing the answer? ### What a Strong Answer Covers Give a constructive algorithm, justify the legality of every swap, prove it reaches the target, and analyze both computation and the length of the returned sequence. Supply tests because the reported exercise did not provide them. ### Follow-up Questions How could you reduce the total number of swaps by using more of the grid's adjacency edges? What would you measure to compare two valid constructions? Explain the difference between an improvement heuristic and a proof of globally minimum swaps. ```hint Find a legal route through the board A path that visits every cell can connect the two-dimensional task to a familiar one-dimensional problem. Check that transitions between rows remain adjacent. ```