3
$\begingroup$

Bejeweled. Candy Crush. A match-three game always follows the same basic rules, with each one adding its tweaks to gameplay.

A mathematician would describe the state of one such game as a two-dimensional matrix whose elements ("blocks") range in a finite set of colors or shapes.

A valid move swaps the positions of two orthogonally adjacent blocks, and is required to form a horizontal or vertical line of more than two of the same type.

After each valid move, the state of the game is updated by destroying every block that belongs to one such line, then allowing remaining blocks to fall down, while creating new blocks at the top until the board is full again. If new lines are formed, they are also destroyed as soon as all the blocks stop moving.

One can easily form lines of size 3, 4 and 5 by moving a single block inbetween sets of blocks of lengths 1 or 2. However, it is not clear how two create a line of length six, since one side would be too long and break before another block could be placed.

It turns out that, by creating block breaking chains, many blocks can be moved simultaneously, and this allows for the construction of lines of length six and longer:

Diagram

For the largest lines, it is extremely hard to get the correct positions and timings for each piece. Many of the techniques I used to create these are not easily applied to the other cases, some are completely ad-hoc.

Can you always find a way to construct these lines? Is there a general strategy that works with arbitrarily large lines? Or, otherwise, is there a limit to our engineering possibilities, beyound which the constraints for the system would prevent the existence of new solutions?

EDIT: It seems that the situation is trivial for vertical lines, as a simple setup may make arbitrarily large solutions. The question for horizontal lines still stands.

$\endgroup$
  • $\begingroup$ Great question! I just fixed a small typo in your question; while I was in there, I changed it to match the current version of the Q. Feel free to edit further if you'd rather it read differently. $\endgroup$ – Steven Stadnicki Jun 9 '15 at 4:36
  • $\begingroup$ I will be interested to see if anyone can find a more space-efficient strategy than mine below. Although to prove for "arbitrary length" lines, we are clearly not working on a game board of limited size, my strategy very quickly will not fit into a traditionally sized game board. That being said, this is a fun and interesting problem. Make more solutions guys! $\endgroup$ – JMoravitz Jun 9 '15 at 5:25
4
$\begingroup$

Yes: here is a strategy:

Using two rows, you may start a chain reaction of arbitrary width (albeit starting at different times) using the repeating pattern:

$$\begin{matrix} \Delta & \Delta & \circ & \circ & + & + & \Delta & \Delta & \cdots & \Delta & \Delta\\ \circ & \circ & + & + & \Delta & \Delta & \circ & \circ & \cdots& \circ & \circ & * & \circ\end{matrix}$$

where the chain reaction is initiated by moving the $\circ$ on the far right one space to the left. Once the $\circ$'s on the far right disappear, this will cause the $\Delta$'s next to them to disappear which cause the $+$'s to disappear which cause the...

We can also have the horizontal chain reaction cause vertical chain reactions of arbitrary height using the following:

$$\begin{matrix} \vdots & \vdots\\ \heartsuit & \heartsuit \\\spadesuit & \spadesuit\\\heartsuit & \heartsuit\\ \Delta & \Delta\\ \heartsuit & \heartsuit \\ \heartsuit & \heartsuit \\ \spadesuit & \spadesuit \\ \spadesuit & \spadesuit\\ \heartsuit & \heartsuit\\ \heartsuit & \heartsuit\\ \vdots & \vdots\end{matrix}$$

where the start of the chain reaction is triggered by the $\Delta$'s being removed during the horizontal chain reaction. This causes the hearts in the middle to cancel which cause the spades next to them to cancel which cause the...

Let us set up as the following:

$$\begin{matrix} & & & & \color{red}{X} & \color{red}{X} & \color{blue}{X} & \color{blue}{X} & \color{red}{X} & \color{red}{X} & \cdots & \color{blue}{X} & \color{blue}{X} & \\ & &\color{blue}{X} & \color{blue}{X} & \circ & \circ & + & + & \Delta & \Delta & \cdots & \Delta & \Delta\\ X & X &\circ & \circ & + & + & \Delta & \Delta & \circ & \circ & \cdots& \circ & \circ & * & \circ\end{matrix}$$

Allow the red $\color{red}{X}$'s to fall as quickly as possible. We wish to delay the blue $\color{blue}{X}$'s by using the $\heartsuit \& \spadesuit$ vertical combination mentioned above for as long as necessary to have all blue $\color{blue}{X}$'s reach the target line at the same time. In doing so we will have reduced the height of the blue $X$'s tremendously however, but it is trivial to see that we can use a checkerboard pattern of unused symbols in such a way that they will never cancel to have the final resting height be level with the rest of the $X$'s.

Here is the strategy in action for a length 14 line. (pardon the bad camera-phone quality)

enter image description here

In general, it should follow from easy induction that after laying the center two rows and the first four columns, you can continue constructing the $(4k+1)^{st}$ and $(4k+2)^{nd}$ (for $k\geq 1$) columns by simply placing $X$'s two rows above the target row, and the $(4k-1)^{st}$ and $(4k)^{th}$ columns (with $k\geq 2$) as a two $X$'s atop a rectangle of height $4(k-1)$ of irreducible peices atop $2(k-1)$ alternating $\heartsuit,\spadesuit$ atop the initial two rows, with $2(k-1)$ sets of $\heartsuit,\spadesuit$ below that.


For vertical lines, as you say, it is rather trivial.

$$\begin{matrix} \Delta & \circ & \circ\\ \circ & + & +\\ \Delta & + & +\\ \Delta & \circ & \circ\\ \circ & + & +\\ \Delta & + & +\\ \Delta & \circ & \circ\\ \vdots\\ \Delta & + & + & \Delta & +\end{matrix}$$

$\endgroup$
  • $\begingroup$ Nice work! And you can also start from the middle (with an AABABB formation) and expand outwards to use half as much delay, while being able to put pairs of X's on both sides. $\endgroup$ – MathET Jun 9 '15 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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