IBM Ponder This #282 · October 2021

Let's assume we are guiding a robotic mouse in a two-dimensional maze. The mouse is situated in the upper-left corner of the maze and must reach the lower-right corner. Unfortunately, there is no direct path in the maze between those two corners. However, we can slide the rows and columns of the maze: by sliding a row one cell-length to the right, for example, we move all the cells in that row exactly one cell-length to the right, re-inserting the rightmost cell from the left. By sliding a column we do the same, sliding cells down. If the mouse is in the row/colum, it will be moved along with its cell.

We proceed in turns: In each turn, we can guide the robotic mouse into any cell reachable from its current cell. Between each two consecutive turns we slide one row or column. Our goal is to minimize the number of turns it takes the mouse to reach its goal.

We represent a maze by a hexadecimal string in the following manner: First, each cell in the maze is represented by a 4-digit binary string representing which passages are blocked (0) and which are open (1) for the directions "up", "right", "down", and "left", in that order. Every such 4-digit string can be converted to a single hexadecimal digit; this correspondence can be seen in the following illustration:

An $nxm$ maze can be represented by a hexadecimal string of length $n\cdot m$ where the first $m$ digits give the upper row, the next $m$ digits give the second row, and so forth. For example, the string:
9182df2ec797b9c88df0af877be505daa6f6575a3cf4c5623

represents the following maze:

We denote cells in the maze by $(a,b)$, where $a$ is the row number and $b$ is the column number, both starting from 0. For example, if the mouse is in the second row from the top and the third column from the left, its location is $(1,2)$. The mouse starts from $(0,0)$ and for a $nxm$ maze needs to reach $(n-1,m-1)$.

Your goal: Given the 7x7 maze:
65dd9ac3e53d7aaa7aac39ea399a57cc6aa9393ac5399399a

Find a sequence of moves for the mouse and row/column slides such that the mouse reaches the exit in at most 6 turns.

An example of the format for the move list:

[(3,5), "C2", (6,3), "R0", (7,7)]

Where each pair $(a,b)$ means "move the mouse to the square $(a,b)$", the "C2" move means "slide column number 2" and "R0" means "slide row number 0".

A bonus "*" will be given for solving the 10x10 maze:
7e3593b53ec55e9e7a6ec759e9a66cb35ea9639c753c356633599336a5a97599556a9c6aa553cc6355a3da56aa693aaae3c9
In at most 14 moves.

Solution

Best opened after a real attempt

To be added.