0

Given a table containing some instruction in each cell ($L$ - $U$ - $R$ - $D$ = Left - Up - Right - Down). The coefficient of the instruction means the number of steps (for example, $2L$ means you should move two squares to your left). The task is to find which cell you should start from if you are to visit all cells and finish at the blank square. Also, find the value (instruction) of the cell with $"?"$. $$ \begin{array}{|c|c|c|c|c|c|c|c|c|} \hline 2D & ? & 2D & 3R & 1L & 2R & 2D & 1D & 1D \\ \hline 1U & 1R & 2R & 1D & 1U & 2L & 5L & 2L & 8L\\ \hline & 2U & 3R & 4R & 4R & 2U & 5L & 3L & 2U\\ \hline \end{array} $$

Update: Solution

Well, at first glance, this reminds me of Knight's tour problem. However, I don't really know if the current problem restricts the number of visits to each cell, as well as "Knight's tour" does.

I have done some further research on the "Knight's tour" problem on $3 \times 9$ grid and found this page representing the following picture:

enter image description here

Despite these two problems have something in common, I can't reduce the current problem to KT (since the trajectory of steps is not (always) the same).

Any help is appreciated.

Attaching the picture of the problem anyway:

enter image description here

Rushabh Mehta
  • 13,663
VIVID
  • 11,604
  • In general, convince yourself that each square will only be visited once (otherwise you'll walk in a loop forever). Walk backwards from the blank square, to see that the second-to-last square must be the top-left 2D square. The 1U square below it must be the third-to-last square. – Alex R. Aug 24 '20 at 17:55

2 Answers2

1

Start from the blank square as the end because you can't leave it. Look for a square that can go there. You have to come from the top left corner. Then to get there you need to come from the middle left. Keep going backwards. You should get to a square you can't get to unless it is from the question mark square, which tells you what to put in there. Then go until you have gone through all the squares and you know where to start.

Ross Millikan
  • 374,822
  • I'm quite confused. Indeed, there are two ways that one can arrive at the blank cell ($1U$ that is 1 above the cell and $4R$ that is 4 left to the cell). Assume that we came to the blank from the cell above ($1U$). Then, at that cell, the face will be looking down (so that $1U$ leads to the blank cell). But it's impossible since we can't appear at that $1U$ cell with "down-looking face". Hence choose the 2nd option. After some steps, this also ends up with the cell at 2nd row 4th column... Am I wrong here? Thank you! – VIVID Aug 24 '20 at 18:16
  • I made the same mistake. You can only arrive at the bottom left from the top left. The $4R$ that we are looking at sends you right, not left. – Ross Millikan Aug 24 '20 at 18:24
  • I don't see anything in the problem about a face. – Ross Millikan Aug 24 '20 at 18:32
  • Haha, I thought the phrase "left to you" meant left to the direction you are looking at. If you have moved, say, down, your face keeps looking down unless you take an action. In this particular case, I thought "left to you" actually meant $R$ in the table. – VIVID Aug 24 '20 at 18:46
  • Oh, I did it! Thanks a lot, @Ross Millikan. Will update the question body with the result soon! Or I better post an answer referencing to your answer :) – VIVID Aug 24 '20 at 19:16
1

Here is the order of the steps to be taken ($i$ in the table stands for the $(27-i+1)^{\text{th}}$ step).

As @RossMillikan mentioned in his answer, we should start from the end (it means we assume the movements start from the blank cell marked with $1$ in the table below): $$ \begin{array}{|c|c|c|c|c|c|c|c|c|} \hline 2 & \color{blue}{18^{\boxed{1R}}} & 17 & 22 & 23 & 14 & 21 & 13 & 5 \\ \hline 3 & 26 & 25 & 10 & 24 & 11 & \color{green}{27_\text{start}} & 12 & 4 \\ \hline \color{red}{1_\text{finish}} & 19 & 16 & 9 & 7 & 15 & 20 & 8 & 6\\ \hline \end{array} $$ Hence, we observe that $ \ \ \boxed{?}=1R$ (marked as $18$ in the table). And the starting cell seems to be the cell on the $2^{\text{nd}}$ row and $7^\text{th}$ column

VIVID
  • 11,604