33
$\begingroup$

Well you probably already knew that this was coming after the last two puzzles :) I believe this is the most beautiful one.

You are given a 5x5 grid with 3 crosses as shown below. Each turn, you can select a cross and slide it along horizontally or vertically. It will continue sliding until it hits another cross or a wall. Can you get a cross into the centre square?enter image description here

$\endgroup$
6
  • $\begingroup$ I like this puzzle, but was it really necessary to post a 3x3 version, then a 4x4 version, then this? $\endgroup$
    – xnor
    Commented Oct 19, 2023 at 23:55
  • 6
    $\begingroup$ I liked these three puzzles AND I appreciate that they have varying degrees of difficulty from the easiest(3x3) to hardest(5x5). $\endgroup$ Commented Oct 20, 2023 at 2:39
  • $\begingroup$ @xnor in hindsight this was probably overkill to make 3 puzzles. At the time I thought that 5x5 is not possible and was only going to do 3x3 and 4x4. $\endgroup$ Commented Oct 20, 2023 at 7:11
  • 1
    $\begingroup$ Just in case anyone wants to generalize this: with 3 crosses in a 6x6 you can also move one to the center 4 squares by the same solution posted here. $\endgroup$
    – quarague
    Commented Oct 20, 2023 at 10:45
  • 1
    $\begingroup$ Hey, I thought you might like to know that I made a little web browser game out of these 3 puzzles! vmi1489186.contaboserver.net/static/sliding-puzzle (licensed under CC BY-SA 4.0, like all stackexchange user content, and with credit given for the puzzle design, of course) $\endgroup$
    – Oli
    Commented Oct 30, 2023 at 21:17

3 Answers 3

22
$\begingroup$

The answer is (maybe surprisingly)

Yes


Lets reverse engineer the problem:

We need to get to this position (other orientations obviously fine):

enter image description here

so we can slide the X into the middle. This means we have one spare X to set this position up

So we can do so by doing the following:

enter image description here

For a total of 14 moves

$\endgroup$
21
  • 2
    $\begingroup$ @DmitryKamenetsky my initial assumption was also it would be impossible, but then I realised you could just about reach the set up as only 2 Xs are needed in the final step, very nice stuff! $\endgroup$ Commented Oct 19, 2023 at 13:29
  • 1
    $\begingroup$ @DmitryKamenetsky I've noticed some minor improvements I can make to reduce the amount of steps which I will update with in a second, but interesting idea, wonder if it would form some sort of pattern $\endgroup$ Commented Oct 19, 2023 at 13:37
  • 2
    $\begingroup$ I think this same method can be used with only 3 Xs on any size of (odd-numbered) grid. You keep repeating steps 4-7 until you have the 3 Xs centred along one side. Once you start firing them down the centre column, you just keep taking the lower one and rotating it back to the top (the last 4 steps). You can do this as many times as needed until an x ends up in the centre cell. $\endgroup$ Commented Oct 19, 2023 at 15:42
  • 1
    $\begingroup$ And I don't think it matters where the Xs start, since it's trivial to stack them all in the corner along one side (a la step 3 above), which you need to do anyway. $\endgroup$ Commented Oct 19, 2023 at 15:44
  • 1
    $\begingroup$ @DanielMathias Let's see it! $\endgroup$ Commented Oct 19, 2023 at 17:06
27
$\begingroup$

I saw these questions late, so I decided to answer all 3 (3x3, 4x4, 5x5 grids) as well as the general case (nxn grids). The answer is

Yes (for any nxn grid)

Regardless of initial position, we can move the Xs upwards so we have them in the following set-up:

XXX......
.........
.........
.........
.........
.........

Then, we can shift this chain of Xs to the right by rotating the leftmost one each time:

.XX......
.........
.........
.........
.........
X........
.XX......
.........
.........
.........
.........
........X
.XX.....X
.........
.........
.........
.........
.........
.XXX....
........
........
........
........
........

Regardless of size of the grid, we can continue this process until the middle X is aligned with the middle column:

...XXX...
.........
.........
.........
.........
.........

Then, we can move the middle X downwards. The leftmost X and bottom X will then be used to put the third X on top of the X in the bottom middle, which we can do repeatedly:

...X.X...
.........
.........
.........
.........
....X....
...XX....
.........
.........
.........
.........
....X....
...X.....
.........
.........
.........
....X....
....X....
...X.....
.........
.........
.........
....X....
........X
...X....X
.........
.........
.........
....X....
.........
...XX....
.........
.........
.........
....X....
.........
...X.....
.........
.........
....X....
....X....
.........

By continuing this process, we will end up with an X in the center of the grid (if n is odd) or 2 Xs in the center of the grid (if n is even).

...X.....
.........
....X....
....X....
.........
.........

$\endgroup$
5
  • 3
    $\begingroup$ great solution to the general case. Thank you. $\endgroup$ Commented Oct 20, 2023 at 7:13
  • 1
    $\begingroup$ This also means that any square is reachable in any NxN grid. Quite amazing $\endgroup$ Commented Oct 20, 2023 at 9:02
  • 2
    $\begingroup$ No problem @DmitryKamenetsky! I'm pretty confident that the reason for this result is that since the grid is 2-dimensional, 3 Xs are needed to access any square (since 1 X is needed to "fix" each dimension and the last X is used to move around). I think the more interesting result would be checking if k+1 Xs are needed to access any square in the k-dimensional case! $\endgroup$
    – Bryce
    Commented Oct 20, 2023 at 13:04
  • $\begingroup$ Wow I haven't even considered higher dimensions! Can we get into the centre with 4 Xs in a 5x5x5 cube? $\endgroup$ Commented Oct 20, 2023 at 14:17
  • 1
    $\begingroup$ @DmitryKamenetsky See this comment: chat.stackexchange.com/transcript/message/64600130#64600130 $\endgroup$ Commented Oct 20, 2023 at 16:40
6
$\begingroup$

Optimal solutions (fewest moves, confirmed via code) for odd grids.

For the 5x5 grid:

12 moves
enter image description here

For the 7x7 grid:

19 moves
enter image description here

For the 9x9 grid:

26 moves
enter image description here

For larger grids:

11x11: 33 moves
13x13: 40 moves
15x15: 47 moves
and so forth.

$\endgroup$
2
  • $\begingroup$ Is it an accident your moving circles are colored in the same order as the robots are in the default configuration of the board editor on robotsevolved.com ? $\endgroup$
    – ilkkachu
    Commented Oct 21, 2023 at 17:48
  • $\begingroup$ @ilkkachu pure chance $\endgroup$ Commented Oct 21, 2023 at 19:06

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.