movement rule: right-else-left-else-stop ========================= note that the starting position of this robot is sideways in the dead end, otherwise it can't get out. with (i,j)||j meaning the robot is in (i,j) parallel to the j-axis, the only possible single-step movements in this scenario are from (i,j)||j to (i+/-1,j)||i and from (i,j)||i to (i,j+/-1)||j. so, the only possible multi-step movements are from (i,j)||j to (i+2n-1,j+2m)||i or to (i+2n,j+2m)||j; and from (i,j)||i to (i+2n-1,j+2m)||j or to (i+2n,j+2m)||i. from this we see that the robot can't return to the dead end where it started from, because if it's aligned parallel to the j-axis at the start, it would have to finish in the same dead end parallel to the i-axis (otherwise it can't get in) which is impossible according to the above movement possiblities. so, the permutations (1)(...) cannot be realized. now suppose the robot finished in some dead end at (i,j)||i, then in order to start its next trip, it is rotated 90 degrees to (i,j)||j so it can leave from the dead end. so, we get the following possible movements from a position in trip k to a position in trip k+1: from (i,j)||j to (i+2n-1,j+2m)||j or to (i+2n,j+2m)||i; and from (i,j)||i to (i+2n-1,j+2m)||i or to (i+2n,j+2m)||j. now the robot might be able to finish in the dead end where it started trip k. extending this, we see that permutations (123..2n+1)(...) cannot be realized, but that permutations (123..2n)(...) might be realized. permutation no indoor walls indoor walls allowed ----------- --------------- -------------------- (1)(...) not possible not possible (123)(...) (12345)(...) etc. 1_ _2 (12) |_ _| same _4 (1234) 1_| |_ same |_ _| |_| 3 2 _1 (12)(34) 2_| |_ _4 same |_ _ _| |_| 3 6_ _5 _| | |_ (123456) not possible |_ _| 1 |_|_| 4 2 3 _5 _1 (12)(3456) _| |_ 2_| |_ _ _| _ |_ |_ _ |_ _| _|_|_ |_ |_ _| 6_| _|1| |_|_ |_ 3 |_|_| 6 |_ |_2>| _|_| _| 4 5 |_ |_| |_| _| 4 |_ _| |_ _| |_| 3 1_ _4 (12)(34)(56) _| |_| |_ _6 same |_ _ _ _| 2 |_| |_| 3 5