# 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 . Shortest code wins.

• Sandbox link: codegolf.meta.stackexchange.com/questions/2140/… Jan 14 at 7:21
• 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.) Jan 14 at 8:34

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 $$\2n^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.