1
$\begingroup$

Here is a hard puzzle from my game. The aim is to change the color of all blue blocks (squares) to green using the following rules:

  • You can move any block or the red ball to an adjacent empty location (horizontally or vertically, but not diagonally).
  • Once the red ball touches any blue blocks it instantly turns them green. This can happen to multiple blocks in one move.
  • The blocks and the ball cannot leave the boundary of the level (black rectangle).

Can you solve this puzzle in 41 moves? Bonus question: is it possible to solve it in fewer moves?

enter image description here

$\endgroup$
2
  • 1
    $\begingroup$ The status space has cardinality $\binom{35}{10}\binom{10}1 = 1835793960$, and the number of possible moves for each status is at most $36$. This means that the graph has $~2e9$ vertices and at most $~7e10$ edges. Hence a brute force search is feasible, although may take some time. $\endgroup$
    – WhatsUp
    Jun 15, 2020 at 21:23
  • 2
    $\begingroup$ @WhatsUp It's larger than that. You can reach the same same layout of ball+blocks in multiple ways, but the number of blocks being green will be different depending on the path you took to reach it. Worst case, you end up with a cardinality of (35 10)(10 1) 2^25 $\endgroup$ Jun 16, 2020 at 0:44

2 Answers 2

6
$\begingroup$

Trying to recreate the 41-move answer, I accidentally got 40:

I'm going to notate by (column letter, row number, direction letter). Columns increase left-to-right, rows increase top-to-bottom, bold moves move the ball.
C1L C2U C3L C4L
A3U A2R B2R C2D
C3D D3L D4U C4R
C3D D3L D2L D4U
D3U E3L E2D D2R
D3U E3L E4L E2D
E3D F3L F4U E4R
E5U F5L G5L G4D
G3D F3R F2L F4U
F3U G3L G2D G1D!
40 move super blox animation

$\endgroup$
4
  • $\begingroup$ Very nice! Stepping through it, I can see where you managed to win the extra move. Looks very optimal now. $\endgroup$ Jun 17, 2020 at 16:17
  • $\begingroup$ Very nice work! You are the first person to find 40 steps without a computer (I assume). Now one last hint rot13(Vg vf cbffvoyr gb npuvrir guvegl avar zbirf. Pna lbh svaq vg?) $\endgroup$ Jun 18, 2020 at 11:41
  • $\begingroup$ SE thank you for adding the animation. It really helps. $\endgroup$ Jun 18, 2020 at 11:47
  • $\begingroup$ Great work! Now can you solve it in 39 moves? $\endgroup$ Jul 18, 2020 at 10:45
5
$\begingroup$

Found the 41 moves solution

super blox animation

There are multiple very similar solutions since the last part can be done in many ways.

Reasoning:

The "zig-zag" pattern looked very promising, since the middle blocks only had to be moved one layer outwards each time the red block went top-to-bottom or bottom-to-top. The symmetry is broken when the red block enters the zig-zag, so every "turn" ends up having a slightly different optimal solution.


Thoughts on bonus question

How many blocks can be turned green in a single move?

Moving blocks:

0 or 1, as you either move a block next to the ball or not. Furthermore, more than 4 blocks can't be turned green this way sustainably, as you will have to move green blocks away from one of the sides of the ball to make space for another blue block. $n$ blocks need at least $2n - 4$ moves to convert in this way.

But the ball can also move:

The ball move that gives the most block converted in one go

...is to move into a 3-block niche. moving into niche

But there's no way to convert any blocks in the next move after that, so it's still only 1.5 blocks per move. (but it's still the best last move).

There are two ways to move into a location with two neighbours, one better than the other:

diagonal movement orthogonal movement

It's possible to sustainably convert 2 blocks per move! But only if the blocks are correctly positioned to begin with.

Furthermore, the course is only 7x5, so after an alternating 7 and 5 moves of converting 2 blocks per move, a "turning" move must be inserted, converting at most 1 block.

As an additional observation, the first 4 moves on this level can't convert more than 4 blocks. Computer search update: the first 8 moves on this level can't convert more than 7 blocks.

That gives a lower bound:

  • First 7 blocks in 8 moves
  • Last 3 blocks in 1 move
  • 15 blocks in the middle moves, where at least 2 blocks can't be converted two at a time. That's 9 more moves.

Sum: 18.

But that's only moving the ball. It's easy to see that the level also requires moving blocks. At 4 block moves, it's not possible for all 5 blocks at the end to leave that column, so the ball has to travel to the second-to-last column in that case. But then 4 blocks in front must be moved away first. That means there are at least 4 extra block moves. (and probably much more).

Sum: 22.

That's probably way way lower than the actual limit (39?,40?), but at least it's provable.

$\endgroup$
3
  • $\begingroup$ I've gotten several 42's and 43's myself, going by layers. $\endgroup$ Jun 15, 2020 at 20:51
  • $\begingroup$ Very well done and I love the graphics! Have a go at the bonus question now. $\endgroup$ Jun 16, 2020 at 0:15
  • $\begingroup$ Excellent analysis for the bonus question! I will give you a hint rot13(vg vf cbffvoyr gb hfr yrff guna 41 zbirf) $\endgroup$ Jun 17, 2020 at 2:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.