Zmieńmy CORONĘ!

Question

Oto przesuwana łamigłówka z 6 blokami na siatce 2x4.

Możesz przesuwać każdy blok. Ale bloku w kształcie 8 z dwoma O nie można przesuwać oddzielnie.

Zwróć uwagę, że klocek w kształcie 8 można ustawić w pozycji pionowej lub poziomej. Taki blok nazywa się samochodem Conway: porusza się zygzakiem na rogach 90 stopni. Tak więc ten problem jest w pewnym sensie hołdem dla Johna Hortona Conwaya, który zmarł z powodu powikłań COVID-19.

Na co możesz zmienić CORONĘ? Jaka jest minimalna liczba kroków?

Answer 1

Wiadomo, że w przypadku każdej zwykłej prostokątnej układanki przesuwnej (większej niż 2x2) każda konfiguracja zgodna z parzystością jest osiągalna ze stanu rozwiązanego, a wszystkie te z nieprawidłową parzystością są nieosiągalne. „Zgodny z parzystością” oznacza, że ​​parzystość całej planszy plus odległość Manhattan dołka od jego ułożonej pozycji muszą być równe. Odpowiednie informacje można znaleźć w Wikipedii i MathWorld .

Deska CORONA ma dwie różnice w stosunku do zwykłej planszy 2x4: są dwa O i są ze sobą sklejone. Zauważyłem, że pionowe OO w środku może zmienić własną parzystość, ale tylko poprzez zmianę położenia otworu (względem pionowego OO blokującego) w tym samym czasie. Kiedy OO znajduje się gdzieś na granicy (poziomej lub pionowej), wygląda na to, że para może mieć tylko jedną orientację.

Nieformalny dowód

Aby zamienić dwa O w miejscu, musimy przesunąć element jak skrzyżowanie T.

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

Należy jednak pamiętać, że pierwszy ruch wymaga dziury po lewej stronie, a trzeci wymaga otworu po prawej stronie. Dziura nie może poruszać się po pionowym elemencie bez uprzedniego przesunięcia pionowego elementu .

Załóżmy również, że pierwszy stan ma dziurę po lewej stronie. Niezależnie od tego, w jaki sposób przesuniesz dziury, przesunięcie obiektu zewnętrznego spowoduje jeden z następujących dwóch stanów:

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

a przeniesienie go z ostatniego stanu spowoduje jedno z następujących:

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

z których wszystkie orientują O2 w kierunku zgodnym z ruchem wskazówek zegara od O1. Nie ma możliwości odwrócenia orientacji OO na granicy.

Podsumowując wszystkie powyższe, biorąc pod uwagę położenie OO i dziury, orientacja OO jest stała. Oznacza to, że argument parzystości ma zastosowanie, mimo że obecne są dwa O, co oznacza, że ​​wszystkie stany nieparzystej parzystości są nieosiągalne.

Myślę, że udowodnienie, że wszystkie stany parzystości są osiągalne, jest łatwe: po prostu przejdź przez stan, w którym OO jest umieszczony pionowo po lewej stronie i swobodnie przesuń pozostałą część 2x3 planszy.

---

Teraz przejdźmy do właściwego zadania. Jeśli nie są dozwolone słowa,

Mogę otrzymać CRAOON w 16 krokach:

         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

Dla prawdziwego słowa,

Znowu dostaję CORONĘ w 19 ruchach (zaczynając od stanu po 15 ruchach):

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

Myślę, że przesłanie z tej układanki jest takie

CORONA jest wytrwała .

---

jafe zasugerował słowo (następnie potwierdzone przez OP)

SZOP

co okazało się możliwe, ale najwyraźniej zbyt daleko (nieco poprawione po edycji):

Zajęło 32 30 28 ruchów .

         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 ruchów:

         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 ruchy:

         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

Zgodnie z wynikami wyszukiwania anagramów na Qat , dwa już przedstawione słowa są jedynymi dostępnymi słowami.

CAROON ma nieprawidłową parzystość (ponieważ RACOON jest osiągalny, a CAROON jest RACOON z zamienionymi R i C), a ORACON rozerwałby dwa O.

Answer 2

Komentarz OP:

Możesz zobaczyć odpowiedź w przenoszeniu pliku gif. 28 ruchów.