Universal Command Sequence

Question

Universal Command Sequence

Definition

An \$n\$-maze is a \$n\times n\$ chessboard which has "walls" on some edges, and a "king" on the board that can move to the 4 adjacent cells, which cannot pass through any walls. Starting from any cell the king should be able to reach every cell on the board.

A command sequence is an array consisting of 4 distinct types of element (for example [1,2,3,4,1,4,2,3,1,...]). Each type of element means a direction of the movement of the king. A command sequence can be "applied to" a maze, if the king can traverse every cell on the board by following the command sequence. For example a command sequence [up,right,down] can be applied to a 2-maze that has no walls and the king is placed at the botton-left cell. If the king is going to pass through a wall or go outside the board, the command will be skipped.

Challenge

For a given positive integer \$n\$, output a command sequence that can be applied to any \$n\$-maze. The existence of this sequence can be proved mathematically.^{See 1998 All-Russian Math Olympiad, Grade level 9, Day 1, Problem 4.}

Input

A positive integer n. You can assume that n>1.

Output

An array consisting of 4 distince types of elements.

Python 3 validator

Try it online. Test your generated sequence here. Usage tips can be found in the footer.

---

This is code-golf. Shortest code wins.

• atzlt: Sandbox link: codegolf.meta.stackexchange.com/questions/2140/…
• Kevin Cruijssen: Related: Shortest universal maze exit string: sequence to go from any variable start to any variable exit in any 3x3 maze. This challenge will be quite a bit harder I assume, since it's not a hard-coded 3x3 maze but \$N\times N\$ based on the input \$N\$ instead. (The 'variable start to exit' versus 'visit all cells' shouldn't make a̶n̶y̶?̶ too much difference.)

Answer 1

Pyth, 7 bytes

s^S4^5*

We could construct a universal sequence of length \2ドル^{2n(n-1)} ⋅ n^2 ⋅ (2n^2 - 2) < 5^{n^2}\$. Start with the empty sequence; then for each of the at most \2ドル^{2n(n-1)}\$ mazes and \$n^2\$ possible starts, imagine following all the previously appended commands to get a new location, and append \2ドルn^2 - 2\$ more commands representing a complete traversal of that maze from that new location.

But, since we know we could construct it, we don’t have to actually do it. Instead, just concatenate all length \5ドル^{n^2}\$ sequences of \1,ドル 2, 3, 4\$. Since we just proved at least one of those sequences is universal, so is their concatenation.