P2739 [USACO4.4] Shuttle Puzzle

In the shuttle puzzle of size $3$, there are $3$ white pieces, $3$ black pieces, and a wooden box with $7$ cells arranged in a line. The $3$ white pieces are placed on one end, the $3$ black pieces are placed on the other end, and the middle cell is empty. - Initial state: `WWW_BBB` (`_` represents the empty cell) - Goal state: `BBB_WWW` Two types of moves are allowed in this game: - You may move a piece into the adjacent empty cell. - You may jump a piece over exactly one adjacent piece of the opposite color into the empty cell. The shuttle puzzle of size $N$ has $N$ white pieces, $N$ black pieces, and a wooden box with $2N+1$ cells. Here is a solution for the size $3$ puzzle, including the initial state, intermediate states, and the goal state: `WWW_BBB` $\rightarrow$ `WW_WBBB` $\rightarrow$ `WWBW_BB` $\rightarrow$ `WWBWB_B` $\rightarrow$ `WWB_BWB` $\rightarrow$ `W_BWBWB` $\rightarrow$ `_WBWBWB` $\rightarrow$ `BW_WBWB` $\rightarrow$ `BWBW_WB` $\rightarrow$ `BWBWBW_` $\rightarrow$ `BWBWB_W` $\rightarrow$ `BWB_BWW` $\rightarrow$ `B_BWBWW` $\rightarrow$ `BB_WBWW` $\rightarrow$ `BBBW_WW` $\rightarrow$ `BBB_WWW` Write a program to solve the shuttle puzzle of size $N$ ($1 \le N \le 12$). The number of moves must be minimized.

A single integer $N$, the size of the shuttle puzzle.

Output the sequence of positions on the board of the piece to be moved before each move (positions are numbered from left to right as $1, 2, \dots, 2N+1$). Print $20$ numbers per line (the last line may contain fewer than $20$ numbers). Among all solutions with the minimum number of moves, the output should be lexicographically smallest, i.e., if there are multiple optimal solutions, choose the one with the smallest first number; if still tied, the smallest second number; and so on.

Problem translation from NOCOW. USACO Training Section 4.3. Translated by ChatGPT 5