Traveling Salesperson Dadas

Choose the village placed at position $i$ as follows.

• If $i$ is odd, choose the unvisited village with the smallest $Y$-coordinate.
• If $i$ is even, choose the unvisited village with the smallest $X$-coordinate.

This always produces a valid order. Suppose that $i$ is odd. When $P_i$ is chosen, $P_{i+1}$ is still unvisited. Since $P_i$ has the minimum $Y$-coordinate among all currently unvisited villages and all $Y$-coordinates are distinct, $Y_{P_i}<Y_{P_{i+1}}$. The even case is identical with $X$ in place of $Y$. Thus every movement condition is satisfied, so a valid order always exists.

Each coordinate value from $1$ to $N$ occurs exactly once. Store the village having each $X$-coordinate and each $Y$-coordinate. Advance a minimum-coordinate pointer until it refers to an unvisited village. Each of the two pointers advances at most $N$ times, so the total time complexity is $O(N)$ and the space complexity is $O(N)$.

Solution written by GPT5.6