Sliding crosses in a 5x5 grid

Question

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?

I like this puzzle, but was it really necessary to post a 3x3 version, then a 4x4 version, then this? — xnor, Oct 19 '23 at 23:55
I liked these three puzzles AND I appreciate that they have varying degrees of difficulty from the easiest(3x3) to hardest(5x5). — Will Octagon Gibson, Oct 20 '23 at 02:39
@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. — Dmitry Kamenetsky, Oct 20 '23 at 07:11
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. — quarague, Oct 20 '23 at 10:45
Hey, I thought you might like to know that I made a little web browser game out of these 3 puzzles! https://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) — Oli, Oct 30 '23 at 21:17
@Oli that is very cool! Thanks for making. If you want more levels then you can add walls that cannot move and change the starting ball locations. — Dmitry Kamenetsky, Oct 30 '23 at 22:56

score 27 · Answer 1 · answered Oct 19 '23 at 23:56

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....
.........
.........

This also means that any square is reachable in any NxN grid. Quite amazing — Dmitry Kamenetsky, Oct 20 '23 at 09:02
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! — Bryce, Oct 20 '23 at 13:04
Wow I haven't even considered higher dimensions! Can we get into the centre with 4 Xs in a 5x5x5 cube? — Dmitry Kamenetsky, Oct 20 '23 at 14:17
@DmitryKamenetsky See this comment: https://chat.stackexchange.com/transcript/message/64600130#64600130 — GentlePurpleRain, Oct 20 '23 at 16:40

Beastly Gerbil · Accepted Answer · 2023-10-19T13:45:40.447

22

The answer is (maybe surprisingly)

Yes

Lets reverse engineer the problem:

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

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:

For a total of 14 moves

edited Oct 19 '23 at 13:45

answered Oct 19 '23 at 13:26

Beastly Gerbil

58,036
8
166
314

wow that was super quick! Well done. I used the same approach. Initially I thought that it will be impossible – Dmitry Kamenetsky Oct 19 '23 at 13:28
2

@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! – Beastly Gerbil Oct 19 '23 at 13:29
Indeed I am quite happy how this one worked out. I am now wondering about the general case: what is the fewest X needed to get an X into the centre of an odd sized NxN grid. But that's a puzzle for another day... – Dmitry Kamenetsky Oct 19 '23 at 13:33
1

@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 – Beastly Gerbil Oct 19 '23 at 13:37
I am thinking there could be a recursive solution that generalises to any NxN. Of course the initial placement of X matters and to make it harder it must be somewhere near one edge – Dmitry Kamenetsky Oct 19 '23 at 13:43
Think 14 is the lowest I can make it, if anyone spots any improvements (or can tell me if 14 is optimal) then that would be great! – Beastly Gerbil Oct 19 '23 at 13:58
@DmitryKamenetsky: Three Xs suffice. – Daniel S Oct 19 '23 at 14:37
2

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. – GentlePurpleRain Oct 19 '23 at 15:42
1

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. – GentlePurpleRain Oct 19 '23 at 15:44
@DmitryKamenetsky ^ – GentlePurpleRain Oct 19 '23 at 15:44
I have a solution in 12. – Daniel Mathias Oct 19 '23 at 17:04
It seems like the number of moves required (with the Xs initially arranged as in the question) is $4n - 6$ for any odd $n$ (where $n$ is the length of one side of the grid). – GentlePurpleRain Oct 19 '23 at 17:05
1

@DanielMathias Let's see it! – GentlePurpleRain Oct 19 '23 at 17:06
CR BD BR BU AD CL AU AR BD BL BU BR @GentlePurpleRain – Daniel Mathias Oct 19 '23 at 19:05
Also CR CU CL AD AR BD AL AU CR CD CL CU @Dmitry – Daniel Mathias Oct 19 '23 at 19:06
@DanielMathias feel free to post your own answer with those! Or I can add that here with credit for you, but that's more than enough for your own answer! – Beastly Gerbil Oct 19 '23 at 19:22
1

I will write code to prove optimal and confirm the generalization before posting. That will likely be tomorrow. – Daniel Mathias Oct 19 '23 at 21:35
@GentlePurpleRain can you show this on 7x7 please – Dmitry Kamenetsky Oct 19 '23 at 21:39
I haven't done any coding yet, but I can tell you that $4n-8$ is not generally optimal. I have 7x7 in 19 moves, and 9x9 in 26. image @Dmitry – Daniel Mathias Oct 20 '23 at 03:49
nice work @DanielMathias – Dmitry Kamenetsky Oct 20 '23 at 07:15
@DmitryKamenetsky Bryce's answer shows the general case below, exactly as I was describing it. – GentlePurpleRain Oct 20 '23 at 16:43

score 6 · Answer 3 · answered Oct 21 '23 at 03:25

6

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

For the 5x5 grid:

12 moves

For the 7x7 grid:

19 moves

For the 9x9 grid:

26 moves

For larger grids:

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

answered Oct 21 '23 at 03:25

Daniel Mathias

14,926
2
30
62

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 https://robotsevolved.com ? – ilkkachu Oct 21 '23 at 17:48
@ilkkachu pure chance – Daniel Mathias Oct 21 '23 at 19:06

Sliding crosses in a 5x5 grid

3 Answers3

Linked