Universal Command Sequence


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.


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.


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


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.

  • \$\begingroup\$ Sandbox link: codegolf.meta.stackexchange.com/questions/2140/… \$\endgroup\$
    – atzlt
    Commented Jan 14, 2022 at 7:21
  • \$\begingroup\$ 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.) \$\endgroup\$ Commented Jan 14, 2022 at 8:34

1 Answer 1


Pyth, 7 bytes


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.