18
$\begingroup$

Here is a sliding puzzle with 6 blocks on a 2x4 grid.

You can move each block. But the 8-shaped block with two O's cannot be moved separately.

Note that the 8-shaped block can be moved into a vertical or horizontal position. Such a block is called a Conway car: it moves in a zigzag way at corners of 90 degrees. So, this problem is an homage to John Horton Conway in some sense, who died due to COVID-19 complications.

enter image description here

enter image description here

What can you change CORONA to? What is the minimal number of steps?

$\endgroup$
5
  • $\begingroup$ (to clarify, does this Conway car exist outside of this puzzle, or was it made and named only for the purposes of this puzzle? (It seems I can't find relevant results for "Conway car" on the Internet)) $\endgroup$
    – oAlt
    Nov 3, 2020 at 23:35
  • 1
    $\begingroup$ @oAlt It is related to moving sofa problem (Wikipedia), and an article linked there does mention the Conway car as "a shape that can move around both left and right corners and/or orient itself backwards via a T-junction". $\endgroup$
    – Bubbler
    Nov 4, 2020 at 0:12
  • $\begingroup$ Ohhh, I see I see; thanks $\endgroup$
    – oAlt
    Nov 4, 2020 at 0:36
  • $\begingroup$ To Clarify: Does the OO block have to rotate? Or can it also translate( <-- OO -->) if there is room? $\endgroup$ Nov 4, 2020 at 15:19
  • 1
    $\begingroup$ @ChrisCudmore Both. $\endgroup$
    – P.-S. Park
    Nov 5, 2020 at 5:37

2 Answers 2

8
+500
$\begingroup$

It is known that, for any plain rectangular sliding puzzle (larger than 2x2), any parity-conforming configuration is reachable from the solved state, and all of those with wrong parity are unreachable. "Parity-conforming" means that the parity of the entire board, plus the Manhattan distance of the hole from its solved position, must be even. Relevant info can be found on Wikipedia and MathWorld.

The CORONA board has two distinctions from a plain 2x4 board: there are two O's, and they're stuck together. I observed that the vertical OO in the middle can change its own parity, but only by changing the location of the hole (relative to the blocking vertical OO) at the same time. When OO is somewhere at the border (either horizontal or vertical), it looks like the pair can have only one orientation.

Informal proof

In order to swap two O's in place, we need to move the piece like a T-junction.

?? O1 ?? ??  =>  ?? ?? ?? ??  =>  ?? ?? ?? ??  =>  ?? O2 ?? ??
?? O2 ?? ??      O2 O1 ?? ??      ?? O2 O1 ??      ?? O1 ?? ??

However, note that the first move requires a hole to be present on the left side, and the third requires a hole on the right side. A hole cannot move across the vertical piece without moving the vertical piece first.

Also, assume the first state has the hole on its left. Regardless of how you move the holes around, moving the OO will result in one of the following two states:

O1 O2 ?? ??  or  ?? ?? ?? ??
?? ?? ?? ??      O2 O1 ?? ??

and moving it from the last state will result in one of the following:

?? O1 O2 ??  or  ?? ?? ?? ??
?? ?? ?? ??      ?? O2 O1 ??

all of which orient O2 on the clockwise direction from O1. There is no way to flip the orientation of OO on the border.

To summarize all of the above, given the position of the OO and the hole, the orientation of OO is fixed. This means that the parity argument applies even though two O's are present, declaring all the odd-parity states unreachable.

I think proving that all the even-parity states are reachable is easy: just go through a state where OO is placed vertically on the left side, and freely move the remaining 2x3 portion of the board.


Now to the actual task. If non-words are allowed,

I can get CRAOON in 16 steps:

         1            4            1            3
C O R x  =>  C . R x  =>  C R x A  =>  C R x A  =>
. O N A      O O N A      O O . N      . O O N
         1            4            1            1
R x . A  =>  R x O A  =>  C R O A  =>  C R . A  =>  C R A .
C O O N      C . O N      x . O N      x O O N      x O O N

For an actual word,

I'm getting CORONA again, in 19 moves (starting with the state after 15 moves):

         2            2
C R . A  =>  C O R A  =>  C O R .
x O O N      x O . N      x O N A

I guess the message from this puzzle is that

CORONA is persistent.


jafe suggested the word (then confirmed by OP)

RACOON

which turned out to be possible but apparently too far away (slightly improved after edit):

It took 32 30 28 moves.

         3            3            3            3
C O R x  =>  O C R x  =>  O . C x  =>  O N . x  =>
. O N A      O . N A      O N R A      O R C A
         5            11
O N x A  =>  O x R A  =>  R A C .
O R . C      O . N C      x O O N

30 moves:

         1            5            6            4
C O R x  =>  C . R x  =>  C R x A  =>  R x A N  =>
. O N A      O O N A      . O O N      C . O O
         5            6            3
R A N O  =>  A C N O  =>  R A C N  =>  R A C .
C x . O      R . x O      . x O O      x O O N

32 moves:

         2            2            2            4
C O R x  =>  O O R x  =>  O . R x  =>  O R N x  =>
. O N A      C . N A      O C N A      O C . A
         4            3            6            9
O R A N  =>  O A C N  =>  O A . C  =>  O x R C  =>  R A C .
O C . x      O R . x      O R x N      O . A N      x O O N

According to the result of anagram search on Qat, the two words already presented are the only reachable words.

CAROON has wrong parity (because RACOON is reachable and CAROON is RACOON with R and C swapped), and ORACON would tear apart the two O's.

$\endgroup$
6
  • 1
    $\begingroup$ Maybe there's a way to make rot13(enpbba)? $\endgroup$
    – Jafe
    Nov 3, 2020 at 9:18
  • $\begingroup$ @jafe It's possible (it has the correct parity), but it took 32 moves. $\endgroup$
    – Bubbler
    Nov 3, 2020 at 9:36
  • 2
    $\begingroup$ Yes. The answer is RACOON. It can be made in less than 32 moves. $\endgroup$
    – P.-S. Park
    Nov 3, 2020 at 11:34
  • 1
    $\begingroup$ @P.-S.Park Found a slightly shorter path. Is it still far away from optimal? $\endgroup$
    – Bubbler
    Nov 3, 2020 at 23:36
  • $\begingroup$ @Bubbler Correct! $\endgroup$
    – P.-S. Park
    Nov 4, 2020 at 13:18
2
$\begingroup$

OP's comment:

You can see the answer in moving gif file. 28 moves.

enter image description here

$\endgroup$
1
  • 2
    $\begingroup$ This seems like it would have been better as and edit or comment on Bubbler's answer $\endgroup$
    – bobble
    Nov 5, 2020 at 5:40

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.