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?