Ponder This Challenge - October 2021 - Sliding maze puzzle

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:

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

• Click here to view the solution

  The solutions can be found using DFS on the game configuration graph, or simply by playing it. Typical solutions to the 7x7 and the 10x10 boards are:

  [(0, 3), "C3", (4, 6), "R5", (5, 6), "C6", (6,6)]

  [(0,0), "C0", (1,3), "R1", (3,4), "R4", (4,5), "R4", (5,6), "R5", (6,7), "C7", (7,7), "R7", (9,9)]

Solvers

• Lorenz Reichel (4/10/2021 10:00 AM IDT)
• Daniel Chong Jyh Tar (4/10/2021 10:36 AM IDT)
• Paul Revenant (4/10/2021 1:13 PM IDT)
• *Guillaume Escamocher (4/10/2021 3:56 PM IDT)
• John Goh (4/10/2021 6:37 PM IDT)
• *Lazar Ilic (4/10/2021 8:46 PM IDT)
• *Phil Proudman (4/10/2021 9:07 PM IDT)
• Marcel Caria (4/10/2021 10:42 PM IDT)
• Kamil Jarosz (5/10/2021 12:08 AM IDT)
• *Bertram Felgenhauer (5/10/2021 5:57 AM IDT)
• *Amos Guler (5/10/2021 2:56 PM IDT)
• Nzube Ntube (5/10/2021 5:05 PM IDT)
• Reiner Martin (6/10/2021 2:15 AM IDT)
• *Aviv Nisgav (6/10/2021 10:11 PM IDT)
• *Yuval Yevnin (7/10/2021 11:45 AM IDT)
• *Vladimir Volevich (7/10/2021 7:48 PM IDT)
• *Andreas Stiller (8/10/2021 4:25 PM IDT)
• Ralf Jonas (8/10/2021 10:35 PM IDT)
• *Dieter Beckerle (9/10/2021 12:13 AM IDT)
• *Andy Greig (9/10/2021 2:48 PM IDT)
• Graham Hemsley (9/10/2021 5:59 PM IDT)
• *Dominik Reichl (9/10/2021 9:21 PM IDT)
• *Gary M. Gerken (9/10/2021 9:43 PM IDT)
• *Tim Walters (11/10/2021 1:49 AM IDT)
• Stefan Wirth (11/10/2021 3:37 PM IDT)
• *Mansi Pai (11/10/2021 9:58 PM IDT)
• *Latchezar Christov (12/10/2021 5:59 PM IDT)
• *Sean Egan (13/10/2021 7:49 AM IDT)
• *Daniel Bitin (13/10/2021 1:02 PM IDT)
• *Alper Halbutogullari (14/10/2021 1:53 PM IDT)
• *Hakan Summakoğlu (15/10/2021 2:31 AM IDT)
• Sri Mallikarjun J (15/10/2021 12:03 PM IDT)
• *Kevin Bauer (15/10/2021 5:23 PM IDT)
• *Harald Bögeholz (16/10/2021 3:58 AM IDT)
• Tamir Ganor & Shouky Dan (16/10/2021 7:02 PM IDT)
• *Moning Zhang (16/10/2021 10:19 PM IDT)
• Shirish C (17/10/2021 2:15 AM IDT)
• *Motty Porat (17/10/2021 2:40 AM IDT)
• *Vincent Beaud (17/10/2021 10:43 PM IDT)
• Karthik Kakarla (18/10/2021 6:53 AM IDT)
• *Sreeram Ramachandran (18/10/2021 7:17 AM IDT)
• *David Greer (19/10/2021 12:51 AM IDT)
• Vijay Nuthulapaty (19/10/2021 3:27 AM IDT)
• Fabio Michele Negroni (21/10/2021 11:23 AM IDT)
• *Kang Jin Cho (21/10/2021 12:43 AM IDT)
• *Walter Schmidt (21/10/2021 6:33 PM IDT)
• *Michael Liepelt (21/10/2021 10:49 PM IDT)
• *Andreas Knüpfer (22/10/2021 9:30 AM IDT)
• *Stéphane Higueret (22/10/2021 9:19 PM IDT)
• Liubing Yu (22/10/2021 11:47 PM IDT)
• *Chris Shannon (23/10/2021 12:30 PM IDT)
• *Quentin Higueret (24/10/2021 12:26 AM IDT)
• *Marco Bellocchi (24/10/2021 12:40 AM IDT)
• Evert van Dijken (24/10/2021 11:21 PM IDT)
• *Radu-Alexandru Todor (25/10/2021 1:06 AM IDT)
• Vijay Nuthulapaty (25/10/2021 1:57 AM IDT)
• *Josh Marza (25/10/2021 8:29 PM IDT)
• Nyles Heise (27/10/2021 8:16 AM IDT)
• Yasodhar Patnaik (27/10/2021 12:27 PM IDT)
• Patrik Holopainen (27/10/2021 8:36 PM IDT)
• *Pedro Soto (28/10/2021 3:16 AM IDT)
• Clive Tong (28/10/2021 5:16 PM IDT)
• *Govind Jujare (28/10/2021 8:17 PM IDT)
• Wolfgang Glas (29/10/2021 1:47 AM IDT)
• Kan Shen (29/10/2021 7:21 AM IDT)
• Guan Haibin (29/10/2021 3:03 PM IDT)
• *David McCullars (30/10/2021 1:51 AM IDT)
• *Erik Wünstel (30/10/2021 6:37 PM IDT)
• Charlie Robertson (31/10/2021 1:20 AM IDT)
• *Lawrence Au (31/10/2021 12:30 PM IDT)
• *Simeon Krastnikov (31/10/2021 9:49 PM IDT)
• *Li Li (4/11/2021 9:34 AM IDT)
• Charles Saidel (4/11/2021 5:51 PM IDT)
• Sebastian Bohm & Martí Bosch (8/11/2021 2:23 PM IDT)