12
$\begingroup$

Since almost two days I am obsessed with this puzzle: Puzzle Picture It is a sliding-block-puzzle, also known as Klotski. The red block has to be moved to where the three red dots are. It says that it is solvable in 187 moves but it shows no solution. I have tried to solve it with an online program but the program is not able to exceed the amount of 187 moves.

Does anyone know the solution to this puzzle or a better program? It has to be a program that offers all possible shapes. I have a program that is perfect but it only allows squares or rectangles. This puzzle has L-shapes though.

puzzle

Improve this question
$\endgroup$

2 Answers 2

Reset to default
13
$\begingroup$

I hacked together a little solver in Python. The puzzle has a rather large state space, with about 6 million positions. My solver doesn't find any solution shorter than 295 moves; here they are, with apologies for the not-very-elegant notation. Read each row from left to right. Blocks are assigned letters independently in different positions, and the assignment may change from one position to the next; I regret any confusion this may cause.

CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB
CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB
FFEDD FFEDD FFEDD FFEDD FFEDD FFEDD FFEDD FFEDD FFEDD FFEDD
HHJGG HHJGG HHJGG HHJGG HH.GG HH.GG GG... .GG.. ..GG. ...GG
KKJII KKJII KKJII KKJII JJKII IIK.. IIKHH IIKHH IIKHH IIKHH
M...L M..L. M.L.. ML... MLK.. MLKJJ MLKJJ MLKJJ MLKJJ MLKJJ

CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB
CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB
FFEDD FFEDD FFEDD FFEDD FFEDD FFEDD FFEDD FFEDD FFEDD FFEDD
..IGG ..IGG HHJGG HHJGG HHJGG HHJGG HHJGG HH.GG HH.GG GG...
JJIHH JJIHH ..JII .KJII .KJII LKJII LKJII KJLII JIL.. JILHH
ML.KK MLKK. MLKK. M.LL. MLL.. .MM.. MM... MML.. MMLKK MMLKK

CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB
CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB
FFEDD FFEDD ..EDD ..EDD ..EDD ..EDD ..EDD F.EDD F.EDD .FEDD
.GG.. ..GG. GGFF. GG.FF .GGFF HGGFF HGGFF .HHGG IHHGG IHHGG
JILHH JILHH JILHH JILHH JILHH .JLII J.LII J.LII ..LJJ ..LJJ
MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK

CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB
CCEBB CCEBB CCEBB CCEBB CC.BB CC.BB CC.BB CC.BB CC.BB CC.BB
GFEDD GFEDD GFEDD .FEDD .EGDD E.GDD EG.DD EG.DD EG.DD EHGDD
.IIHH II.HH ...HH H..GG H.GFF H.GFF HG.FF HGJFF HGJFF IHGFF
..LJJ ..LJJ JJLII JJLII JJLII JJLII JJLII KKJII KKJII KK.JJ
MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MM.LL .MMLL .MMLL

CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB
CC.BB CC.BB CC.BB CC.BB CC.BB CC.BB CCEBB CCEBB CCEBB CCEBB
EHGDD EHGDD EHGDD .GFDD .GFDD G.FDD G.EDD H.EDD H.EDD H.EDD
IHGFF .HGFF .HGFF HGFEE .GFEE G.FEE G..FF HGGFF HGGFF HGGFF
.KKJJ KJJII .JJII .JJII JIIHH JIIHH JIIHH J..II .J.II KJ.II
.MMLL .MMLL MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK .MMLL

CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB
CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB
H.EDD H.EDD ..EDD ..EDD ..EDD FFEDD FFEDD FFEDD FFEDD FFEDD
HGGFF HGGFF KGGFF .GGFF GG.FF ...GG K..GG K..GG K.HGG KH.GG
K.JII .KJII KJIHH MJIHH MJIHH MJIHH KJIHH KJIHH KJ.II KJ.II
.MMLL .MMLL .MMLL MLLKK MLLKK MLLKK .MMLL MM.LL MM.LL MM.LL

CAAAB CAAAB CAAAB CAAAB CAAAB DAAAB DAAAB DAAAB DAAAB DAAAB
CC.BB CC.BB CC.BB CC.BB CC.BB DDCBB DDCBB DDCBB DDCBB DDCBB
EEGDD EE.DD EE.DD EE.DD FFEDD FF.EE .FFEE HFFEE HFFEE H..EE
KHGFF KGIFF JG.FF J.GFF J..GG J..GG J..GG H..GG H..GG HGGFF
KJ.II KJIHH JILHH JILHH JILHH JILHH JILHH .JLII J.LII J.LII
MM.LL MM.LL MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK

DAAAB DAAAB CAAA. CAAA. C.AAA .CAAA .CAAA .CAAA DCAAA DCAAA
DDCBB DDCBB CCB.D CC.BD CC.BD .CCBD FCCBD FCCBD DCCBE DCCBE
H.EE. HEE.. HEEDD HEEDD HEEDD HEEDD FEEDD FEEDD .FFEE GFFEE
HGGFF HGGFF HGGFF HGGFF HGGFF HGGFF .HHGG IHHGG IHHGG .IIHH
J.LII J.LII J.LII J.LII J.LII J.LII J.LII ..LJJ ..LJJ ..LJJ
MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK

DCAAA DCAAA DCAAA DCAAA DCAAA DCAAA DCAAA .CAAA .CAAA C.AAA
DCCBE DCCBE DCCBE DCCBE DCCB. DCCB. DCCB. FCCB. .CCB. CC.B.
GFFEE GFFEE GFFEE GFFEE FEE.G F.EEG .FEEG FEDDG HEDDF HEDDF
II.HH ...HH ..HH. .HH.. .HHGG .HHGG .HHGG .HHGG HGGFF HGGFF
..LJJ JJLII JJLII JJLII JJLII JJLII JJLII JJLII JJLII JJLII
MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK

C.AAA D.AAA DAAA. DBBBA DBBBA DBBBA DBBBA DBBBA DBBBA DBBBA
CC..B DDCCB DDCCB DDCC. DDCCE DDCCE DDCCE DDCCE DDCCE DDCCE
HEDDF HE..F HE..F HE..F HF.EE HF.EE HF.EE HF.EE HF.EE IFHEE
HGGFF HGGFF HGGFF HGGFF HGG.. H.GG. H..GG H.JGG H.JGG I.HGG
JJLII JJLII JJLII JJLII JJLII JJLII JJLII KKJII KKJII KK.JJ
MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MM.LL .MMLL .MMLL

DBBBA DBBBA DBBBA DBBBA .BBBA .BBBA BBB.A BBBA. BBBAC BBBAC
DDCCE DDCCE DDCCE DDCCE E.CCD ECC.D ECC.D ECC.D EDDCC FDDCC
IFHEE .FHEE .FHEE ..GEE EEGDD EEGDD EEGDD EEGDD EEG.. FFGEE
I.HGG K.HGG ..HGG .HGFF .HGFF .HGFF .HGFF .HGFF .HGFF .HG..
.KKJJ KJJII MJJII MJJII MJJII MJJII MJJII MJJII MJJII MJJII
.MMLL .MMLL MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK

BBBAC BBBAC BBBAC BBBAC BBBAC BBBAC BBBAC BBBAC BBBA. BBBA.
FDDCC FDDCC FDDCC FDDCC FDDCC .DDCC .DDCC .DDCC .CC.D CC..D
FFHEE FFHEE FFHEE FFHEE FF.EE G..EE G.EE. GEE.. GEEDD GEEDD
.IHGG .IHGG ..HGG ..HGG ..IGG GGIFF GGIFF GGIFF GGIFF GGIFF
MJJ.. M.JJ. MJII. MJ.II MJIHH MJIHH MJIHH MJIHH MJIHH MJIHH
MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK

AAA.. .AAA. ..AAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA
CC.BD CC.BD CC.BD ...CD .DDCE DD.CE DDC.E CC..D CC..D CC..D
GEEDD GEEDD GEEDD GEEDD G..EE G..EE G..EE G.EDD GE.DD HEGDD
GGIFF GGIFF GGIFF GGIFF GGIFF GGIFF GGIFF GGIFF GGIFF HHGFF
MJIHH MJIHH MJIHH MJIHH MJIHH MJIHH MJIHH MJIHH MJIHH MJ.II
MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK

BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA
CC..D CCE.D CCE.D CCE.D CCE.D CCE.D CCD.. CC.D. CC.D. .CCD.
HEGDD HFEDD IFEDD IFEDD IFEDD HFEDD HED.F HE.DF H.EDF H.EDF
HHGFF HH.GG IIHGG IIHGG IIHGG HHG.. HHGFF HHGFF HHGFF HHGFF
M.JII M.JII M..JJ M.JJ. MJJ.. MJJII MJJII MJJII MJJII MJJII
MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK

BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA
FCCD. FCCD. FCCD. FCCD. FCCD. FCCD. FCCD. FCCD. FCCD. FCC.D
FFEDG FFEDG FFEDG FFEDG FFEDG FFEDG FFED. FFED. FFED. FFE.D
..HGG .H.GG H..GG IHHGG IHHGG IHHGG HGG.I H.GGI .HGGI .HGGI
MJJII MJJII MJJII M..JJ M.JJ. MJJ.. MJJII MJJII MJJII MJJII
MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK

BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA
FCC.D FDDCE GDDCE GDDCE GDDCE GDDCE GDDCE GDDCE GDDCE GDDCE
FF.ED FF..E GGFFE GGFFE GGFFE GGFFE GGFFE GGFFE GGFFE GGFFE
.HGGI .HGGI .H..I ..H.I ...HI .IIHJ .IIHJ .IIHJ .IIHJ .IIH.
MJJII MJJII MJJII MJJII MJJII M..JJ MKKJJ MKKJJ MKKJJ MJJ.K
MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK M..LL M.LL. MLL.. MLLKK

BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA AA... .AA.. ..AA.
GDDCE GDDCE .DDCE .DDC. .DDC. .CC.. CC... CCBBB CCBBB CCBBB
GGFFE GGFFE H.FFE H.EEF HEE.F HEEDF HEEDF HEEDF HEEDF HEEDF
.HH.. ..HH. HHGG. HHGGF HHGGF HHGGF HHGGF HHGGF HHGGF HHGGF
MJJIK MJJIK MJJIK MJJIK MJJIK MJJIK MJJIK MJJIK MJJIK MJJIK
MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK

BBAA. BBAA. BBAA. BBAA. BBAA. BBAA. BBAAC BBAAC BBAAC BBAAC
..CCC .CCC. .CCCD .CCCD CCC.D DDDCE EEEDC EEEDC EEEDC EEEDC
HEEDF HEEDF HFFED HFFED HFFED HFF.E HFF.. HGGFF IGGFF IGGFF
HHGGF HHGGF HHGG. HH.GG HH.GG HH.GG HH.GG HH... II.H. IIH..
MJJIK MJJIK MJJIK MJJIK MJJIK MJJIK MJJIK MJJIK MJJ.K MJJ.K
MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK

BBAAC BBAAC BBAAC BBAAC BBAAC BBAAC BBAAC BBAA. BBAA. BBAA.
EEEDC EEEDC EEEDC EEEDC EEEDC EEEDC EEEDC DDDCE DDDC. DDD.C
IFF.. I.FF. I..FF I.GFF I.GFF IG.FF IGFF. IGFFE IFEEG IFEEG
IIHGG IIHGG IIHGG II.HH IIHH. IIHH. IIHH. IIHH. IIHHG IIHHG
MJJ.K MJJ.K MJJ.K MJJ.K MJJ.K MJJ.K MJJ.K MJJ.K MJJ.K MJJ.K
MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK

BBAA. CCBBA CCBBA CCBBA CCBBA CCBBA CCBBA CCBBA CCBBA CCBBA
.DDDC .DDD. ..DDD .EDDD GEDDD GEDDD GEDDD GEDDD GEDDD GEDDD
IFEEG IFEEG IFEEG I.FFG GGFFH GGFFH GGFFH GGFFH GGFF. GGFF.
IIHHG IIHHG IIHHG IIHHG ..IIH K.IIH K.IIH K.IIH K.HHI J.HH.
MJJ.K MJJ.K MJJ.K MJJ.K MJJ.K KJJ.L KJJ.L KJJL. KJJLI JIILK
MLLKK MLLKK MLLKK MLLKK MLLKK .MMLL MM.LL MMLL. MMLL. MMLLK

CCBBA CCBBA CCBBA CCBBA CCBBA CCBBA CCBBA BB..A .BB.A EBB.A
GEDDD GEDDD FEDDD FD... F.D.. F..D. F...D F.DDC F.DDC EEDDC
GGFF. GG.FF FF... FFEEE FFEEE FFEEE FFEEE FFEEE FFEEE ..FFF
JHH.. JHH.. JHHGG JHHGG JHHGG JHHGG JHHGG JHHGG JHHGG JHHGG
JIILK JIILK JIILK JIILK JIILK JIILK JIILK JIILK JIILK JIILK
MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK

EBB.A EBB.A EBB.A DBB.A DBB.A D.BBA .DBBA .DBBA .DBBA .DBBA
EEDDC EEDDC EEDDC DDCC. DD.CC DD.CC .DDCC GDDCC GDDCC GDDCC
I.FFF I.FFF IFFF. IFFFE IFFFE IFFFE IFFFE GFFFE GFFFE GFFFE
IHHGG IHHGG IHHGG IHHGG IHHGG IHHGG IHHGG .IIHH II.HH IIHH.
.JJLK JJ.LK JJ.LK JJ.LK JJ.LK JJ.LK JJ.LK JJ.LK JJ.LK JJ.LK
MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK

.DBBA .DBBA EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA
FDDCC FDDCC EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC
FEEE. F.EEE ..FFF GGFFF GGFFF GGFFF GGFFF GGFFF GGFFF GGFFF
IIHHG IIHHG IIHHG ..IIH .II.H II..H II.H. IIH.. HH... .HH..
JJ.LK JJ.LK JJ.LK JJ.LK JJ.LK JJ.LK JJ.LK JJ.LK JJILK JJILK
MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK

EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA
EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC
GGFFF GGFFF GGFFF GGFFF GGFFF GGFFF GGFFF ..FFF ..FFF ..FFF
..HH. IIHH. IIHH. IIHH. II.HH .IIHH ...HH HH.GG .HHGG IHHGG
JJILK ..JLK .J.LK J..LK J..LK J..LK JIILK JIILK JIILK .JJLK
MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK

EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA
EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC
..FFF .FFF. FFF.. GGGFF GGGFF GGGFF GGGFF GGGFF GGGFF GGGFF
IHHGG IHHGG IHHGG IHH.. IHHJ. IHHJ. IHHJ. IHHJ. IHHKJ IHHKJ
JJ.LK JJ.LK JJ.LK JJ.LK KKJJL KKJJL KKJJL ..JJK ..KKJ ..KKJ
MMLLK MMLLK MMLLK MMLLK MM..L .MM.L ..MML MMLLK MMLL. MM.LL

EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA DCBBA
EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC DCC..
GGGFF GGGFF GGGFF GGGFF GGGFF ...FF ..FF. .FF.. FF... FF.EE
IHHKJ .HHJI .HHJI HH.JI ...IH GGGIH GGGIH GGGIH GGGIH GGGIH
..KKJ K.JJI ..JJI ..JJI JJIIH JJIIH JJIIH JJIIH JJIIH JJIIH
.MMLL .MMLL MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK

DCBBA DCBBA DCAA. DCAA. DCAA. DCAA. DCAA. EDAAB EDAAB EDAAB
DCC.. DCC.. DCC.B DCCB. DCCBE DCCBE DCCBE EDDCB EDDCB EDDCB
FFEE. FFEEG FFEEG FFEEG GGFFE GGFFE GGFFE GGFF. GGFFH GGFFH
GGGIH HHHIG HHHIG HHHIG HHHI. HHH.I HHH.I HHH.I IIIHH IIIHH
JJIIH JJII. JJII. JJII. JJII. JJ.II .JJII .JJII .JJ.. ..JJ.
MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK

EDAAB EDAAB EDAAB EDAAB EDAAB DCAA. DCAA. DCAA. DCAA. DCAA.
EDDCB EDDCB EDDCB EDDCB EDDCB DCCBE DCCB. DCCB. DCC.B DCCEB
GGFFH GGFFH ..FFG .FF.G .FFG. .FFGE .EEGF EE.GF EE.GF FFEEG
IIIHH ...HH HH.GG HH.GG HHGG. HHGG. HHGGF HHGGF HHGGF HH..G
...JJ JJJII JJJII JJJII JJJII JJJII JJJII JJJII JJJII JJJII
MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK

DCBBA DCBBA DCBBA DCBBA DCBBA DCBBA DCBBA DCBBA DCBBA DCBBA
DCCE. DCCFE DCCFE DCCFE DCCFE DCCFE DCCFE DCCFE DCCFE DCCFE
FFEEG GGFFE GGFFE GGFFE GGFFE GGFFE GGFFE GGFFE GGFFE GGFFE
HH..G HH... II.HH II.HH II.HH .IIHH JIIHH JIIHH JIIHH JIIHH
JJJII JJJII JJJ.. .JJJ. KJJJ. KJJJ. .KKK. KKK.. LLLKK LLLKK
MLLKK MLLKK MLLKK MLLKK .MMLL .MMLL .MMLL .MMLL .MM.. ..MM.

DCBBA DCBBA DCBBA DCBBA DCBBA DCBBA
DCCFE DCCFE DCCFE DCCFE DCCFE DCCFE
GGFFE GGFFE GGFFE GGFFE GGFFE GGFFE
JIIHH JIIHH JIIHH JIIHH JIIHH JIIHH
LLLKK ...KK ..KK. .KK.. .LLKK .LLKK
...MM MMMLL MMMLL MMMLL MMM.. .MMM.

Here's my code. It's neither very efficient nor very elegant. It takes a little while to run because it explores a lot of positions. It wouldn't be difficult to improve it, but I'm afraid I'm not going to bother :-).

# if p is a position then graph[p] is a list of positions you can move to from p
# a position is (occupied, pieces)
# occupied is a bitmap, pieces is a tuple of 12 bitmaps in ascending order
# bitmaps are laid out as follows
#   43210
#   98765
#   EDCBA
#   JIHGF
#   OMNLK
#   TSRQP

import collections

graph = {}

left   = 0b100001000010000100001000010000
right  = 0b000010000100001000010000100001
top    = 0b000000000000000000000000011111
bottom = 0b111110000000000000000000000000

def moves_from(p):
  occupied,pieces = p
  for i in range(len(p[1])):
    piece = pieces[i]
    o = occupied^piece
    # try moving left
    q = piece<<1
    if (piece & left) == 0 and (q & o) == 0:
      yield ((o|q), tuple(sorted(pieces[:i] + (q,) + pieces[i+1:])))
    # try moving right
    q = piece>>1
    if (piece & right) == 0 and (q & o) == 0:
      yield ((o|q), tuple(sorted(pieces[:i] + (q,) + pieces[i+1:])))
    # try moving up
    q = piece>>5
    if (piece & top) == 0 and (q & o) == 0:
      yield ((o|q), tuple(sorted(pieces[:i] + (q,) + pieces[i+1:])))
    # try moving down
    q = piece<<5
    if (piece & bottom) == 0 and (q & o) == 0:
      yield ((o|q), tuple(sorted(pieces[:i] + (q,) + pieces[i+1:])))

initial_position = (
  0b100011111111111111111111111111,
  (0b000000000000000000000000001110, # ---
   0b000000000000000000000001100001, # J
   0b000000000000000000001100010000, # L
   0b000000000000000000110000000000, # -- (right)
   0b000000000000000001000010000000, # I
   0b000000000000000110000000000000, # -- (left)
   0b000000000000011000000000000000, # -- (right)
   0b000000000011000000000000000000, # -- (left)
   0b000000001100000000000000000000, # -- (right)
   0b000000010000100000000000000000, # I
   0b000001100000000000000000000000, # -- (left)
   0b000010000000000000000000000000, # . (right)
   0b100000000000000000000000000000) # . (left)
)

pending = collections.deque([initial_position])

last_size = 0

while pending:
  p = pending.popleft()
  if p not in graph: graph[p] = []
  for q in moves_from(p):
    if q not in graph:
      graph[q] = []
      pending.append(q)
    if q not in graph[p]:
      graph[p].append(q)
  if len(graph) > 2*last_size+1:
    print(f"Now have {len(graph)} positions in graph.")
    last_size = len(graph)

print("Graph complete, {len(graph)} positions.")

last_size = 0

# shortest distances from starting position
distances = {}
pending = collections.deque([(initial_position,0)])
while pending:
  (p,d) = pending.popleft()
  if d < distances.get(p, 999999):
    distances[p] = d
    for q in graph[p]: pending.append((q,d+1))
  if len(distances) > 2*last_size+1:
    print(f"Now have {len(distances)} distances.")
    last_size = len(distances)

print("Distances complete, {len(distances)} found.")

def find_path_to(p):
  result = []
  while p != initial_position:
    result.append(p)
    d = distances[p]
    p = [q for q in graph[p] if distances[q]==d-1][0]
  result.append(initial_position)
  return result[::-1]

def rectangularize(p):
  result = [5*[0] for i in range(6)]
  for i in range(len(p[1])):
    q = p[1][i]
    for row in range(6):
      for col in range(5):
        if (q & (1<<(5*row+(4-col)))) != 0: result[row][col] = i+1
  return result

def show_seq(positions):
  # show 10 per row
  pending = 6*['']
  for p in positions:
    if len(pending[0]) > 55:
      for row in pending: print(row)
      print()
      pending = 6*['']
    r = rectangularize(p)
    for i in range(6):
      pending[i] += (' ' if pending[i] else '') + ''.join((chr(ord('A')-1+c) if c>0 else '.') for c in r[i])
  if pending[0]:
    for row in pending: print(row)
    print()

target = min((distances[p],p) for p in distances if 0b011100000000000000000000000000 in p[1])

show_seq(find_path_to(target[1]))

If we adopt the convention that any single straight-line move of a piece counts as one move, rather than moving one square at a time, I get 222 moves instead of 295. Here's the relevant change to the code:

def moves_from(p):
  occupied,pieces = p
  for i in range(len(p[1])):
    piece = pieces[i]
    o = occupied^piece
    # try moving left
    q = piece
    for j in range(3):
      q1 = q<<1
      if (q & left) == 0 and (q1 & o) == 0:
        yield ((o|q1), tuple(sorted(pieces[:i] + (q1,) + pieces[i+1:])))
        q = q1
      else: break
    # try moving right
    q = piece
    for j in range(3):
      q1 = q>>1
      if (q & right) == 0 and (q1 & o) == 0:
        yield ((o|q1), tuple(sorted(pieces[:i] + (q1,) + pieces[i+1:])))
        q = q1
      else: break
    # try moving up
    q = piece
    for j in range(3):
      q1 = q>>5
      if (q & top) == 0 and (q1 & o) == 0:
        yield ((o|q1), tuple(sorted(pieces[:i] + (q1,) + pieces[i+1:])))
        q = q1
      else: break
    # try moving down
    q = piece
    for j in range(3):
      q1 = q<<5
      if (q & bottom) == 0 and (q1 & o) == 0:
        yield ((o|q1), tuple(sorted(pieces[:i] + (q1,) + pieces[i+1:])))
        q = q1
      else: break

and the resulting solution:

CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB
CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB
FFEDD FFEDD FFEDD FFEDD FFEDD FFEDD FFEDD FFEDD FFEDD FFEDD
HHJGG HHJGG HH.GG HH.GG GG... ...GG HH.GG HH.GG HH.GG HHJGG
KKJII KKJII JJKII IIK.. IIKHH IIKHH ..KII J.LII KJMII LKJII
M...L ML... MLK.. MLKJJ MLKJJ MLKJJ MLKJJ .MLKK ..MLL ...MM

CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB
CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB
FFEDD FFEDD FFEDD FFEDD FFEDD ..EDD ..EDD F.EDD F.EDD .FEDD
HHJGG HH.GG HH.GG GG... ...GG GG.FF .GGFF .HHGG .HHGG .HHGG
LKJII KJLII JIL.. JILHH JILHH JILHH JILHH .JLII J.LII J.LII
MM... MML.. MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK

CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB
CCEBB CCEBB CCEBB CCEBB CC.BB CC.BB CC.BB CCEBB CCEBB CCEBB
GFEDD GFEDD GFEDD .FEDD .EGDD E.GDD EG.DD FHEDD FHEDD FHEDD
.IIHH II.HH ...HH H..GG H.GFF H.GFF HG.FF IH.GG IH.GG IH.GG
..LJJ ..LJJ JJLII JJLII JJLII JJLII JJLII KK.JJ KK.JJ .KKJJ
MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MM.LL .MMLL .MMLL

CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB
CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB CCEBB
FHEDD .GEDD G.EDD H.EDD H.EDD H.EDD H.EDD ..EDD ..EDD FFEDD
.H.GG .G.FF G..FF HGGFF HGGFF HGGFF HGGFF .GGFF GG.FF ...GG
.JJII JIIHH JIIHH J..II ..JII K.JII .KJII MJIHH MJIHH MJIHH
MLLKK MLLKK MLLKK MLLKK MLLKK .MMLL .MMLL MLLKK MLLKK MLLKK

CAAAB CAAAB CAAAB CAAAB CAAAB CAAAB DAAAB DAAAB DAAAB DAAAB
CCEBB CCEBB CCEBB CCEBB CC.BB CC.BB DDCBB DDCBB DDCBB DDCBB
FFEDD FFEDD FFEDD FFEDD EE.DD EE.DD FF.EE FF.EE EE... .EE..
K..GG K..GG K.HGG KH.GG JG.FF J.GFF J..GG JGG.. JGGFF JGGFF
KJIHH KJIHH KJ.II KJ.II JILHH JILHH JILHH JILHH JILHH JILHH
.MMLL MM.LL MM.LL MM.LL MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK

CAAA. CAAA. C.AAA .CAAA DCAAA DCAAA DCAAA DCAAA DCAAA DCAAA
CCB.D CC.BD CC.BD .CCBD DCCBE DCCBE DCCBE DCCBE DCCBE DCCBE
.EEDD .EEDD .EEDD .EEDD .FFEE .FFEE GFFEE GFFEE GFFEE GFFEE
JGGFF JGGFF JGGFF JGGFF .HHGG .HHGG .IIHH II.HH ...HH .HH..
JILHH JILHH JILHH JILHH .JLII J.LII ..LJJ ..LJJ JJLII JJLII
MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK

DCAAA DCAAA DCAAA .CAAA C.AAA C.AAA D.AAA DAAA. DBBBA DBBBA
DCCB. DCCB. DCCB. .CCB. CC.B. CC..B DDCCB DDCCB DDCC. DDCCE
FEE.G F.EEG .FEEG HEDDF HEDDF HEDDF HE..F HE..F HE..F HF.EE
.HHGG .HHGG .HHGG HGGFF HGGFF HGGFF HGGFF HGGFF HGGFF HGG..
JJLII JJLII JJLII JJLII JJLII JJLII JJLII JJLII JJLII JJLII
MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK MMLKK

DBBBA DBBBA DBBBA DBBBA DBBBA DBBBA .BBBA .BBBA BBB.A BBBA.
DDCCE DDCCE DDCCE DDCCE DDCCE DDCCE E.CCD ECC.D ECC.D ECC.D
HF.EE IFHEE IFHEE IFHEE .FHEE ..GEE EEGDD EEGDD EEGDD EEGDD
H..GG I.HGG I.HGG I.HGG ..HGG .HGFF .HGFF .HGFF .HGFF .HGFF
JJLII KK.JJ KK.JJ .KKJJ MJJII MJJII MJJII MJJII MJJII MJJII
MMLKK MM.LL .MMLL .MMLL MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK

BBBAC BBBAC BBBAC BBBAC BBBAC BBBAC BBBAC BBBAC BBBA. BBBA.
EDDCC FDDCC FDDCC FDDCC FDDCC FDDCC .DDCC .DDCC .CC.D CC..D
EEG.. FFGEE FFHEE FFHEE FFHEE FF.EE G..EE GEE.. GEEDD GEEDD
.HGFF .HG.. .IHGG .IHGG ..HGG ..IGG GGIFF GGIFF GGIFF GGIFF
MJJII MJJII MJJ.. M..JJ MJ.II MJIHH MJIHH MJIHH MJIHH MJIHH
MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK

AAA.. ..AAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA
CC.BD CC.BD ...CD .DDCE DD.CE DDC.E CC..D CC..D CCE.D CCE.D
GEEDD GEEDD GEEDD G..EE G..EE G..EE G.EDD GE.DD HFEDD HFEDD
GGIFF GGIFF GGIFF GGIFF GGIFF GGIFF GGIFF GGIFF HH.GG HH.GG
MJIHH MJIHH MJIHH MJIHH MJIHH MJIHH MJIHH MJIHH MJ.II M.JII
MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK

BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA
CCE.D CCE.D CCE.D CCD.. CC.D. CC.D. .CCD. FCCD. FCCD. FCCD.
IFEDD IFEDD HFEDD HED.F HE.DF H.EDF H.EDF FFEDG FFEDG FFEDG
IIHGG IIHGG HHG.. HHGFF HHGFF HHGFF HHGFF ..HGG H..GG IHHGG
M..JJ MJJ.. MJJII MJJII MJJII MJJII MJJII MJJII MJJII M..JJ
MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK

BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA
FCCD. FCCD. FCCD. FCC.D FCC.D FDDCE GDDCE GDDCE GDDCE GDDCE
FFEDG FFED. FFED. FFE.D FF.ED FF..E GGFFE GGFFE GGFFE GGFFE
IHHGG HGG.I H.GGI H.GGI H.GGI H.GGI H...I ...HI .IIHJ .IIHJ
MJJ.. MJJII MJJII MJJII MJJII MJJII MJJII MJJII M..JJ MKKJJ
MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK M..LL

BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA BBAAA AA...
GDDCE GDDCE GDDCE GDDCE .DDCE .DDC. .DDC. .CC.. CC... CCBBB
GGFFE GGFFE GGFFE GGFFE H.FFE H.EEF HEE.F HEEDF HEEDF HEEDF
.IIHJ .IIH. .HH.. ..HH. HHGG. HHGGF HHGGF HHGGF HHGGF HHGGF
MKKJJ MJJ.K MJJIK MJJIK MJJIK MJJIK MJJIK MJJIK MJJIK MJJIK
MLL.. MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK

..AA. BBAA. BBAA. BBAAC BBAAC BBAAC BBAAC BBAAC BBAAC BBAAC
CCBBB ..CCC CCC.. DDD.C DDD.C EEEDC EEEDC EEEDC EEEDC EEEDC
HEEDF HEEDF HEEDF HFFE. HFFE. HFF.. HGGFF IGGFF IGGFF IFF..
HHGGF HHGGF HHGGF HHGG. HH.GG HH.GG HH... II.H. IIH.. IIHGG
MJJIK MJJIK MJJIK MJJIK MJJIK MJJIK MJJIK MJJ.K MJJ.K MJJ.K
MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK

BBAAC BBAAC BBAAC BBAAC BBAAC BBAA. BBAA. CCBBA CCBBA CCBBA
EEEDC EEEDC EEEDC EEEDC EEEDC DDDC. DDD.C DDD.. ..DDD .EDDD
I..FF I.GFF I.GFF IG.FF IGFF. IFEEG IFEEG IFEEG IFEEG I.FFG
IIHGG II.HH IIHH. IIHH. IIHH. IIHHG IIHHG IIHHG IIHHG IIHHG
MJJ.K MJJ.K MJJ.K MJJ.K MJJ.K MJJ.K MJJ.K MJJ.K MJJ.K MJJ.K
MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK

CCBBA CCBBA CCBBA CCBBA CCBBA CCBBA CCBBA CCBBA CCBBA CCBBA
GEDDD GEDDD GEDDD GEDDD GEDDD GEDDD GEDDD FEDDD FD... F...D
GGFFH GGFFH GGFFH GGFFH GGFF. GGFF. GG.FF FF... FFEEE FFEEE
..IIH K.IIH K.IIH K.IIH J.HH. JHH.. JHH.. JHHGG JHHGG JHHGG
MJJ.K KJJ.L KJJ.L KJJL. JIILK JIILK JIILK JIILK JIILK JIILK
MLLKK .MMLL MM.LL MMLL. MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK

BB..A ..BBA E.BBA E.BBA D.BBA D.BBA .DBBA EDBBA EDBBA EDBBA
F.DDC F.DDC EEDDC EEDDC DDCC. DD.CC .DDCC EDDCC EDDCC EDDCC
FFEEE FFEEE ..FFF .FFF. .FFFE .FFFE .FFFE .GGGF .GGGF .GGGF
JHHGG JHHGG JHHGG JHHGG JHHGG JHHGG JHHGG .IIHH .IIHH II.HH
JIILK JIILK JIILK JIILK JIILK JIILK JIILK .JJLK JJ.LK JJ.LK
MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK

EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA
EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC
.GGGF .FFF. ..FFF GGFFF GGFFF GGFFF GGFFF GGFFF ..FFF FFF..
IIHH. IIHHG IIHHG ..IIH II..H IIH.. HH... ...HH HH.GG HH.GG
JJ.LK JJ.LK JJ.LK JJ.LK JJ.LK JJ.LK JJILK JJILK JJILK JJILK
MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK MMLLK

EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA EDBBA
EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC EDDCC
GGGFF GGGFF GGGFF GGGFF GGGFF GGGFF GGGFF GGGFF GGGFF GGGFF
HH... ...HH ..IHH I..HH IHH.. IHHJ. IHHKJ IHHKJ IHHKJ IHHKJ
JJILK JJILK JJ.LK JJ.LK JJ.LK KKJJL LLKKJ LLKKJ ..KKJ ..KKJ
MMLLK MMLLK MMLLK MMLLK MMLLK MM..L MM... ...MM MM.LL .MMLL

EDBBA EDBBA EDBBA EDBBA EDBBA DCBBA DCBBA DCAA. DCAA. EDAAB
EDDCC EDDCC EDDCC EDDCC EDDCC DCC.. DCC.. DCC.B DCCB. EDDCB
GGGFF GGGFF GGGFF ...FF FF... FF.EE FFEE. FFEE. FFEE. GGFF.
.HHJI HH.JI ...IH GGGIH GGGIH GGGIH GGGIH GGGIH GGGIH HHHI.
..JJI ..JJI JJIIH JJIIH JJIIH JJIIH JJIIH JJIIH JJIIH JJII.
MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK

EDAAB EDAAB EDAAB EDAAB EDAAB EDAAB EDAAB DCAA. DCAA. DCAA.
EDDCB EDDCB EDDCB EDDCB EDDCB EDDCB EDDCB DCCB. DCC.B DCCEB
GGFF. GGFFH GGFFH GGFFH ..FFG FF..G FF.G. EE.GF EE.GF FFEEG
HHH.I IIIHH IIIHH ...HH HH.GG HH.GG HHGG. HHGGF HHGGF HH..G
JJ.II JJ... ...JJ JJJII JJJII JJJII JJJII JJJII JJJII JJJII
MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK MLLKK

DCBBA DCBBA DCBBA DCBBA DCBBA DCBBA DCBBA DCBBA DCBBA DCBBA
DCCE. DCCFE DCCFE DCCFE DCCFE DCCFE DCCFE DCCFE DCCFE DCCFE
FFEEG GGFFE GGFFE GGFFE GGFFE GGFFE GGFFE GGFFE GGFFE GGFFE
HH..G HH... II.HH II.HH .IIHH JIIHH JIIHH JIIHH JIIHH JIIHH
JJJII JJJII JJJ.. .JJJ. .JJJ. .KKK. KKK.. LLLKK LLLKK ...KK
MLLKK MLLKK MLLKK MLLKK MLLKK .MMLL .MMLL .MM.. ...MM MMMLL

DCBBA DCBBA DCBBA
DCCFE DCCFE DCCFE
GGFFE GGFFE GGFFE
JIIHH JIIHH JIIHH
.KK.. .LLKK .LLKK
MMMLL MMM.. .MMM.

Perhaps the figure of 187 moves is what you get if you allow any sequence of moves by a single piece to count as a single move, even if not in a straight line? I'm afraid I'm too lazy to implement that variant right now.

Improve this answer
$\endgroup$
16
  • $\begingroup$ Sliding a single piece any distance in one direction counts as one move. Your first three moves to put the L next to the M are actually only one move. $\endgroup$
    – Daniel Mathias
    Mar 18, 2020 at 23:16
  • $\begingroup$ Ah, OK, I guessed the wrong convention there. $\endgroup$
    – Gareth McCaughan ♦
    Mar 18, 2020 at 23:51
  • $\begingroup$ With that change made, I get 222 moves from the initial position to the nearest one with the 3-square piece at bottom centre. $\endgroup$
    – Gareth McCaughan ♦
    Mar 19, 2020 at 0:17
  • 1
    $\begingroup$ If I'd been writing the code with clarity in mind, yup. (A lot of other things might be different too.) As it happens, I was writing it with my own convenience in mind :-). $\endgroup$
    – Gareth McCaughan ♦
    Jun 16, 2021 at 11:03
  • 1
    $\begingroup$ @Wolf Yes, my state count treats blocks of the same shape and orientation as equivalent, so interchanging them does not yield a different state. $\endgroup$
    – RobPratt
    Jun 16, 2021 at 21:06
4
$\begingroup$

I made my own independent implementation in C#.

This does a breadth-first search of all legally reachable states, where a "move" is defined as moving a single piece any distance.

I would imagine that other possible definitions of "move" may exist, for example:

  • the same piece may be moved multiple times e.g. "around a corner" as a single move.
  • a piece that is not immediately adjacent to a gap may be "moved" by pushing the pieces between it and the gap.

It is not clear what definition of "move" the original puzzle setter intended.

My code confirms 222 as the minimum number of moves (of a single piece any distance in a single direction) to reach the solved state.

When I redefined a "move" to allow any number of pieces to be moved simultaneously by the same amount in the same direction, it found a solution in 146 moves. This included some "mega moves" like this:

After move 120: piece(s) at 32,39,37 by 1 Left to cover 36:
##################
╔═╗╔════╗╔═╗╔═╗###
║ ║╚════╝╚═╝║ ║###
║ ║╔════╗╔══╝ ║###
╚═╝╚════╝╚════╝###
╔════╗╔═══════╗###
╚════╝╚═══════╝###
╔═╗╔═╗   ╔════╗###
║ ║║ ║   ╚════╝###
║ ║║ ╚══╗   ╔═╗###
╚═╝╚════╝   ╚═╝###
╔════╗╔════╗   ###
╚════╝╚════╝   ###
##################

After move 121: piece(s) at 15,20,27,34 by 1 Down to cover 40:
##################
╔═╗╔════╗╔═╗   ###
║ ║╚════╝╚═╝   ###
║ ║╔════╗   ╔═╗###
╚═╝╚════╝   ║ ║###
╔════╗   ╔══╝ ║###
╚════╝   ╚════╝###
╔═╗╔═╗╔═══════╗###
║ ║║ ║╚═══════╝###
║ ║║ ╚══╗╔════╗###
╚═╝╚════╝╚════╝###
╔════╗╔════╗╔═╗###
╚════╝╚════╝╚═╝###
##################

After move 122: piece(s) at 19,12,8,9,14 by 1 Right to cover 15:
##################
   ╔═╗╔════╗╔═╗###
   ║ ║╚════╝╚═╝###
   ║ ║╔════╗╔═╗###
   ╚═╝╚════╝║ ║###
   ╔════╗╔══╝ ║###
   ╚════╝╚════╝###
╔═╗╔═╗╔═══════╗###
║ ║║ ║╚═══════╝###
║ ║║ ╚══╗╔════╗###
╚═╝╚════╝╚════╝###
╔════╗╔════╗╔═╗###
╚════╝╚════╝╚═╝###
##################

When I instead redefined a move to allow a single piece to be moved in multiple directions, it found a solution in 191 moves.

It is thus unclear what exact rule set must be used to have the solution "in 187 moves" as stated in the question, but my first modification allows this with some margin. Perhaps if the rules of which pieces can move "together" are tightened somewhat (e.g. perhaps the first and last "mega moves" would need to be split as they can't be done by pushing a single piece and having that piece push the others) we'd get something closer to the 187 move target, but as I considered how to implement that, it started to get a bit "complicated".

Returning to the "original" definition of a move, when I remove the termination condition, it also confirms 6288084 (mentioned in the comments of Graham's answer) as the number of unique states that can be reached with legal moves. Of those, there are 12 states that can be reached only after 436 moves! (printed as 11 by the program which doesn't count the state currently being processed)

See links to source code and program output including the first solution found after 222 moves (looks better if pasted into something that doesn't put gaps between the lines), and to the source code modified to allow moves to be combined (with the two merge types as described above, controlled by AllowableMergeType), and its output for a 146 move solution.

A summary of the 222-step solution found based on a tidied up copy of the program output (as there are fewer empty squares than pieces, I used the empty squares to track the moves rather than the pieces, so each move is described by the number of an empty square that is covered, and the direction that a piece is moved in order to cover it - e.g. "Down to 39" means that the piece directly above empty square 39 is moved down just far enough to cover square 39):

Starting state with square numbers labelled:
##################
╔═╗╔═══════╗╔═╗### <== squares 6 to 10
║ ║╚═══════╝║ ║###
║ ╚══╗╔═╗╔══╝ ║### <== squares 12 to 16
╚════╝║ ║╚════╝###
╔════╗║ ║╔════╗### <== squares 18 to 22
╚════╝╚═╝╚════╝###
╔════╗╔═╗╔════╗### <== squares 24 to 28
╚════╝║ ║╚════╝###
╔════╗║ ║╔════╗### <== squares 30 to 34
╚════╝╚═╝╚════╝###
╔═╗ 3  3  3 ╔═╗### <== squares 36 to 40
╚═╝ 7  8  9 ╚═╝###
##################

Move 1: Left to 37
Move 2: Down to 38
Move 3: Down to 39
Move 4: Down to 33
Move 5: Right to 28
Move 6: Up to 24
Move 7: Up to 30
Move 8: Up to 31
Move 9: Up to 26
Move 10: Left to 36
Move 11: Down to 39
Move 12: Down to 33
Move 13: Down to 38
Move 14: Right to 28
Move 15: Down to 24
Move 16: Right to 26
Move 17: Up to 18
Move 18: Left to 30
Move 19: Right to 19
Move 20: Up to 18
Move 21: Left to 24
Move 22: Down to 26
Move 23: Down to 30
Move 24: Down to 24
Move 25: Left to 18
Move 26: Left to 25
Move 27: Up to 14
Move 28: Right to 32
Move 29: Right to 38
Move 30: Down to 36
Move 31: Down to 30
Move 32: Left to 24
Move 33: Up to 25
Move 34: Right to 32
Move 35: Up to 30
Move 36: Right to 31
Move 37: Down to 36
Move 38: Left to 24
Move 39: Up to 26
Move 40: Up to 18
Move 41: Up to 24
Move 42: Left to 36
Move 43: Left to 25
Move 44: Down to 38
Move 45: Right to 26
Move 46: Up to 14
Move 47: Left to 25
Move 48: Down to 27
Move 49: Down to 21
Move 50: Right to 15
Move 51: Right to 10
Move 52: Right to 14
Move 53: Right to 20
Move 54: Up to 6
Move 55: Left to 30
Move 56: Up to 18
Move 57: Left to 24
Move 58: Down to 30
Move 59: Left to 25
Move 60: Down to 27
Move 61: Right to 21
Move 62: Right to 19
Move 63: Right to 16
Move 64: Down to 24
Move 65: Left to 12
Move 66: Up to 14
Move 67: Left to 7
Move 68: Up to 10
Move 69: Up to 16
Move 70: Right to 28
Move 71: Down to 25
Move 72: Up to 20
Move 73: Right to 32
Move 74: Right to 38
Move 75: Down to 36
Move 76: Down to 18
Move 77: Left to 13
Move 78: Left to 6
Move 79: Left to 9
Move 80: Up to 10
Move 81: Up to 21
Move 82: Up to 27
Move 83: Right to 34
Move 84: Down to 32
Move 85: Down to 31
Move 86: Down to 24
Move 87: Left to 19
Move 88: Down to 21
Move 89: Down to 15
Move 90: Right to 10
Move 91: Left to 12
Move 92: Up to 6
Move 93: Up to 13
Move 94: Left to 12
Move 95: Left to 14
Move 96: Down to 20
Move 97: Left to 19
Move 98: Up to 14
Move 99: Right to 32
Move 100: Up to 26
Move 101: Left to 31
Move 102: Down to 33
Move 103: Down to 27
Move 104: Right to 21
Move 105: Right to 20
Move 106: Right to 14
Move 107: Up to 12
Move 108: Left to 24
Move 109: Up to 25
Move 110: Left to 31
Move 111: Down to 33
Move 112: Right to 27
Move 113: Right to 22
Move 114: Right to 21
Move 115: Up to 15
Move 116: Up to 20
Move 117: Right to 27
Move 118: Up to 25
Move 119: Up to 31
Move 120: Left to 37
Move 121: Down to 39
Move 122: Down to 33
Move 123: Right to 27
Move 124: Down to 28
Move 125: Down to 24
Move 126: Left to 19
Move 127: Down to 21
Move 128: Left to 12
Move 129: Down to 14
Move 130: Right to 9
Move 131: Up to 6
Move 132: Left to 12
Move 133: Up to 15
Move 134: Up to 10
Move 135: Right to 28
Move 136: Up to 21
Move 137: Up to 27
Move 138: Left to 26
Move 139: Down to 27
Move 140: Right to 22
Move 141: Up to 20
Move 142: Left to 26
Move 143: Left to 19
Move 144: Left to 20
Move 145: Down to 28
Move 146: Right to 16
Move 147: Up to 10
Move 148: Right to 16
Move 149: Up to 13
Move 150: Up to 12
Move 151: Up to 24
Move 152: Left to 36
Move 153: Left to 38
Move 154: Down to 40
Move 155: Right to 22
Move 156: Left to 25
Move 157: Down to 27
Move 158: Down to 20
Move 159: Right to 16
Move 160: Down to 14
Move 161: Right to 9
Move 162: Up to 6
Move 163: Left to 19
Move 164: Down to 22
Move 165: Right to 16
Move 166: Right to 14
Move 167: Up to 6
Move 168: Left to 24
Move 169: Left to 26
Move 170: Down to 28
Move 171: Right to 22
Move 172: Left to 30
Move 173: Up to 18
Move 174: Left to 24
Move 175: Left to 26
Move 176: Down to 32
Move 177: Right to 28
Move 178: Down to 24
Move 179: Left to 18
Move 180: Up to 21
Move 181: Right to 28
Move 182: Up to 26
Move 183: Left to 24
Move 184: Left to 25
Move 185: Up to 27
Move 186: Up to 28
Move 187: Right to 40
Move 188: Down to 36
Move 189: Right to 38
Move 190: Down to 36
Move 191: Left to 24
Move 192: Down to 30
Move 193: Down to 24
Move 194: Left to 18
Move 195: Down to 21
Move 196: Down to 16
Move 197: Left to 15
Move 198: Left to 20
Move 199: Up to 10
Move 200: Right to 34
Move 201: Up to 27
Move 202: Right to 34
Move 203: Down to 30
Move 204: Down to 24
Move 205: Left to 18
Move 206: Left to 26
Move 207: Down to 28
Move 208: Right to 16
Move 209: Up to 15
Move 210: Right to 26
Move 211: Up to 10
Move 212: Up to 16
Move 213: Up to 27
Move 214: Right to 33
Move 215: Up to 24
Move 216: Left to 30
Move 217: Up to 33
Move 218: Right to 40
Move 219: Down to 36
Move 220: Left to 30
Move 221: Up to 33
Move 222: Right to 39

After move 222: Right to 39:
##################
╔═╗╔═╗╔════╗╔═╗###
║ ║║ ║╚════╝╚═╝###
║ ║║ ╚══╗╔═╗╔═╗###
╚═╝╚════╝║ ║║ ║###
╔════╗╔══╝ ║║ ║###
╚════╝╚════╝╚═╝###
╔═╗╔════╗╔════╗###
╚═╝╚════╝╚════╝###
╔════╗   ╔════╗###
╚════╝   ╚════╝###
   ╔═══════╗   ###
   ╚═══════╝   ###
##################

In this implementation I didn't specifically model the pieces - merely the connections to adjacent cells in the position that each piece is currently resting, so all pieces of the same shape are inherently indistinguishable.

I later thought to print out the 12 "most complicated" states, which take 436 of this type of move to reach. There were the following (together with the mirror images of each):

##################
╔════╗   ╔═╗╔═╗###
╚════╝   ║ ║╚═╝###
╔═╗╔════╗║ ╚══╗###
╚═╝╚════╝╚════╝###
╔═╗╔═══════╗   ###
║ ║╚═══════╝   ###
║ ║╔═╗╔════╗   ###
╚═╝║ ║╚════╝   ###
╔══╝ ║╔═╗╔════╗###
╚════╝║ ║╚════╝###
╔════╗║ ║╔════╗###
╚════╝╚═╝╚════╝###
##################

##################
╔════╗╔═╗╔════╗###
╚════╝╚═╝╚════╝###
╔═╗   ╔═╗╔════╗###
╚═╝   ║ ║╚════╝###
╔═╗╔══╝ ║╔════╗###
║ ║╚════╝╚════╝###
║ ║╔═══════╗   ###
╚═╝╚═══════╝   ###
╔════╗╔═╗╔═╗   ###
╚════╝║ ║║ ║   ###
╔════╗║ ║║ ╚══╗###
╚════╝╚═╝╚════╝###
##################

##################
╔════╗╔═╗╔════╗###
╚════╝╚═╝╚════╝###
╔═╗╔═╗╔═╗╔════╗###
║ ║╚═╝║ ║╚════╝###
║ ║╔══╝ ║╔════╗###
╚═╝╚════╝╚════╝###
╔════╗╔═══════╗###
╚════╝╚═══════╝###
╔════╗╔═╗╔═╗   ###
╚════╝║ ║║ ║   ###
      ║ ║║ ╚══╗###
      ╚═╝╚════╝###
##################

##################
╔════╗╔═╗╔════╗###
╚════╝╚═╝╚════╝###
╔═╗   ╔═╗╔════╗###
╚═╝   ║ ║╚════╝###
╔═╗╔══╝ ║╔════╗###
║ ║╚════╝╚════╝###
║ ║   ╔═══════╗###
╚═╝   ╚═══════╝###
╔════╗╔═╗╔═╗   ###
╚════╝║ ║║ ║   ###
╔════╗║ ║║ ╚══╗###
╚════╝╚═╝╚════╝###
##################

##################
╔════╗╔════╗   ###
╚════╝╚════╝   ###
╔═╗╔═╗╔═╗╔════╗###
╚═╝╚═╝║ ║╚════╝###
╔═╗╔══╝ ║╔════╗###
║ ║╚════╝╚════╝###
║ ║╔═══════╗   ###
╚═╝╚═══════╝   ###
╔════╗╔═╗╔═╗   ###
╚════╝║ ║║ ║   ###
╔════╗║ ║║ ╚══╗###
╚════╝╚═╝╚════╝###
##################

##################
╔════╗╔════╗   ###
╚════╝╚════╝   ###
╔═╗╔═╗╔═╗╔════╗###
╚═╝╚═╝║ ║╚════╝###
╔═╗╔══╝ ║╔════╗###
║ ║╚════╝╚════╝###
║ ║   ╔═══════╗###
╚═╝   ╚═══════╝###
╔════╗╔═╗╔═╗   ###
╚════╝║ ║║ ║   ###
╔════╗║ ║║ ╚══╗###
╚════╝╚═╝╚════╝###
##################
Improve this answer
$\endgroup$
3
  • $\begingroup$ If you count (Down, Left) for the same piece as a single move, does that account for the 4-move gap? $\endgroup$
    – Spitemaster
    Jul 16, 2020 at 15:39
  • $\begingroup$ @Spitemaster Counting (e.g.) down,left for the same piece as a single move reduced it from 222 to 191. The 4 move gap to 187 is AFTER making that change. Sorry if that wasn't clear. $\endgroup$
    – Steve
    Jul 16, 2020 at 15:46
  • $\begingroup$ No, my bad, I missed that. My reading comprehension today is poor, apparently. $\endgroup$
    – Spitemaster
    Jul 16, 2020 at 15:48

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.