perplexus.info :: General : Sliding Puzzle

Sliding Puzzle (Posted on 2004-06-10)

Here is one of the older sliding puzzles:

You have a sliding puzzle that looks like this:

AB
 C
DE

You may move a block with a letter on it to the blank space by sliding it there. How many moves does it take to put D where E is and E where D is at the same time? (The other pieces don't need to be in their original spots.)

See The Solution Submitted by Gamer

Rating: 2.6667 (6 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)

Two shortest--computer solution

| Comment 4 of 14 |

Two solutions were found in 17 moves:

decbadbcebdacdbed
ab ab ab ab a   a da da da da da  a a  ac ac ac ac ac 
 c dc dc d  db db  b b  bc bc  c dc dc d   d bd bd b  
de  e e  ec ec ec ec ec e   e be be be be be  e e  ed

decdabdceacdbcaed
ab ab ab ab ab  b b  bd bd bd bd bd b   b cb cb cb cb 
 c dc dc d   d ad ad a  ac ac  c c  cd cd  d ad ad a  
de  e e  ec ec ec ec ec e   e ae ae ae ae ae  e e  ed

by this program, which searched for solutions up to 20 steps:

DECLARE SUB move (lvl%)
CLEAR , , 16000
DEFINT A-Z
DIM SHARED box(21, 3, 2), hist(21), zeroRow, zeroCol, maxLvl
DATA 1,2,0,3,4,5
FOR row = 1 TO 3
FOR col = 1 TO 2
READ box(1, row, col)
NEXT
NEXT
maxLvl = 20
zeroRow = 2: zeroCol = 1

OPEN "slidpuz.txt" FOR OUTPUT AS #2

move 1

CLOSE
END

'
SUB move (lvl)
IF lvl > maxLvl THEN EXIT SUB
row = zeroRow - 1: col = zeroCol: GOSUB tryIt
row = zeroRow + 1: col = zeroCol: GOSUB tryIt
row = zeroRow: col = zeroCol + 1: GOSUB tryIt
row = zeroRow: col = zeroCol - 1: GOSUB tryIt
EXIT SUB

tryIt:
IF row > 0 AND row < 4 AND col > 0 AND col < 3 THEN
IF box(lvl - 1, zeroRow, zeroCol) <> box(lvl, row, col) THEN
   FOR r = 1 TO 3
    FOR c = 1 TO 2
     box(lvl + 1, r, c) = box(lvl, r, c)
    NEXT
   NEXT
   box(lvl + 1, zeroRow, zeroCol) = box(lvl, row, col)
   box(lvl + 1, row, col) = 0
   good = 1
   FOR l = lvl - 1 TO 1 STEP -1
     match = 1
     FOR r = 1 TO 3
      FOR c = 1 TO 2
       IF box(l, r, c) <> box(lvl + 1, r, c) THEN match = 0: EXIT FOR
      NEXT
      IF match = 0 THEN EXIT FOR
     NEXT
     IF match THEN good = 0: EXIT FOR
   NEXT l
   IF good THEN
     hist(lvl) = box(lvl + 1, zeroRow, zeroCol)
     IF box(lvl + 1, 3, 1) = 5 AND box(lvl + 1, 3, 2) = 4 THEN
       FOR l = 1 TO lvl
          PRINT #2, MID$(" abcde", hist(l) + 1, 1);
       NEXT
       PRINT #2,
       FOR r = 1 TO 3
        FOR l = 1 TO lvl + 1
          FOR c = 1 TO 2
            PRINT #2, MID$(" abcde", box(l, r, c) + 1, 1);
          NEXT c
          PRINT #2, " ";
        NEXT l
        PRINT #2,
       NEXT
       PRINT #2,
     END IF
     szc = zeroCol: szr = zeroRow
     zeroCol = col: zeroRow = row
     move lvl + 1
     zeroCol = szc: zeroRow = szr
   END IF
END IF
END IF
RETURN
END SUB

All the solutions with 20 or fewer steps are:

abcedabcebadbecaebde
ab  b b  bc bc bc bc  c c  ce ce ce ce ce c   c ac ac ac ac ac 
 c ac ac a  ae ae  e be be b   b ab ab a  ae ae  e e  eb eb  b 
de de de de d   d ad ad ad ad ad  d d  db db db db db d   d ed

abcedaecbeadcaebacde
ab  b b  bc bc bc bc bc b   b eb eb eb eb eb  b b  ba ba ba ba 
 c ac ac a  ae ae  e e  ec ec  c ac ac a   a ea ea e  ec ec  c 
de de de de d   d ad ad ad ad ad  d d  dc dc dc dc dc d   d ed

decbadbcebdacebdebde
ab ab ab ab a   a da da da da da  a a  ac ac ac ac ac ac ac ac 
 c dc dc d  db db  b b  bc bc  c dc dc d  de de  e e  eb eb  b 
de  e e  ec ec ec ec ec e   e be be be be b   b db db d   d ed

decbadbcebdacdbed
ab ab ab ab a   a da da da da da  a a  ac ac ac ac ac 
 c dc dc d  db db  b b  bc bc  c dc dc d   d bd bd b  
de  e e  ec ec ec ec ec e   e be be be be be  e e  ed

decbadbcebdacdbedc
ab ab ab ab a   a da da da da da  a a  ac ac ac ac ac a  
 c dc dc d  db db  b b  bc bc  c dc dc d   d bd bd b  bc 
de  e e  ec ec ec ec ec e   e be be be be be  e e  ed ed

decbadbcebdacdbedca
ab ab ab ab a   a da da da da da  a a  ac ac ac ac ac a   a 
 c dc dc d  db db  b b  bc bc  c dc dc d   d bd bd b  bc bc 
de  e e  ec ec ec ec ec e   e be be be be be  e e  ed ed ed

decbadbcebdacdbedcab
ab ab ab ab a   a da da da da da  a a  ac ac ac ac ac a   a ba 
 c dc dc d  db db  b b  bc bc  c dc dc d   d bd bd b  bc bc  c 
de  e e  ec ec ec ec ec e   e be be be be be  e e  ed ed ed ed

decbadbcebdacdbedb
ab ab ab ab a   a da da da da da  a a  ac ac ac ac ac ac 
 c dc dc d  db db  b b  bc bc  c dc dc d   d bd bd b   b 
de  e e  ec ec ec ec ec e   e be be be be be  e e  ed ed

decbadbcebdacdbedba
ab ab ab ab a   a da da da da da  a a  ac ac ac ac ac ac  c 
 c dc dc d  db db  b b  bc bc  c dc dc d   d bd bd b   b ab 
de  e e  ec ec ec ec ec e   e be be be be be  e e  ed ed ed

decbadbcebdacdbedbac
ab ab ab ab a   a da da da da da  a a  ac ac ac ac ac ac  c c  
 c dc dc d  db db  b b  bc bc  c dc dc d   d bd bd b   b ab ab 
de  e e  ec ec ec ec ec e   e be be be be be  e e  ed ed ed ed

decdabdceacdbcaed
ab ab ab ab ab  b b  bd bd bd bd bd b   b cb cb cb cb 
 c dc dc d   d ad ad a  ac ac  c c  cd cd  d ad ad a  
de  e e  ec ec ec ec ec e   e ae ae ae ae ae  e e  ed

decdabdceacdbcaedb
ab ab ab ab ab  b b  bd bd bd bd bd b   b cb cb cb cb c  
 c dc dc d   d ad ad a  ac ac  c c  cd cd  d ad ad a  ab 
de  e e  ec ec ec ec ec e   e ae ae ae ae ae  e e  ed ed

decdabdceacdbcaedbc
ab ab ab ab ab  b b  bd bd bd bd bd b   b cb cb cb cb c   c 
 c dc dc d   d ad ad a  ac ac  c c  cd cd  d ad ad a  ab ab 
de  e e  ec ec ec ec ec e   e ae ae ae ae ae  e e  ed ed ed

decdabdceacdbcaedbca
ab ab ab ab ab  b b  bd bd bd bd bd b   b cb cb cb cb c   c ac 
 c dc dc d   d ad ad a  ac ac  c c  cd cd  d ad ad a  ab ab  b 
de  e e  ec ec ec ec ec e   e ae ae ae ae ae  e e  ed ed ed ed

decdabdceacdbcaeda
ab ab ab ab ab  b b  bd bd bd bd bd b   b cb cb cb cb cb 
 c dc dc d   d ad ad a  ac ac  c c  cd cd  d ad ad a   a 
de  e e  ec ec ec ec ec e   e ae ae ae ae ae  e e  ed ed

decdabdceacdbcaedac
ab ab ab ab ab  b b  bd bd bd bd bd b   b cb cb cb cb cb  b 
 c dc dc d   d ad ad a  ac ac  c c  cd cd  d ad ad a   a ca 
de  e e  ec ec ec ec ec e   e ae ae ae ae ae  e e  ed ed ed

decdabdceacdbcaedacb
ab ab ab ab ab  b b  bd bd bd bd bd b   b cb cb cb cb cb  b b  
 c dc dc d   d ad ad a  ac ac  c c  cd cd  d ad ad a   a ca ca 
de  e e  ec ec ec ec ec e   e ae ae ae ae ae  e e  ed ed ed ed

decdecdbaecdbceacbde
ab ab ab ab ab ab ab ab a   a ea ea ea ea ea  a a  ac ac ac ac 
 c dc dc d   d ed ed e  eb eb  b cb cb c   c ec ec e  eb eb  b 
de  e e  ec ec  c c  cd cd cd cd  d d  db db db db db d   d ed

cedcabeacdaebceade
ab ab ab ab ab  b b  be be be be be b   b cb cb cb cb cb 
 c c  ce ce  e ae ae a   a ca ca c  ce ce  e e  ea ea  a 
de de d   d cd cd cd cd cd  d d  da da da da da d   d ed

cedcabeacdaebceadec
ab ab ab ab ab  b b  be be be be be b   b cb cb cb cb cb  b 
 c c  ce ce  e ae ae a   a ca ca c  ce ce  e e  ea ea  a ca 
de de d   d cd cd cd cd cd  d d  da da da da da d   d ed ed

cedcabeacdaebceadecb
ab ab ab ab ab  b b  be be be be be b   b cb cb cb cb cb  b b  
 c c  ce ce  e ae ae a   a ca ca c  ce ce  e e  ea ea  a ca ca 
de de d   d cd cd cd cd cd  d d  da da da da da d   d ed ed ed

cedcabeacdaebceadea
ab ab ab ab ab  b b  be be be be be b   b cb cb cb cb cb cb 
 c c  ce ce  e ae ae a   a ca ca c  ce ce  e e  ea ea  a a  
de de d   d cd cd cd cd cd  d d  da da da da da d   d ed ed

cedcabeacdaebceadeab
ab ab ab ab ab  b b  be be be be be b   b cb cb cb cb cb cb c  
 c c  ce ce  e ae ae a   a ca ca c  ce ce  e e  ea ea  a a  ab 
de de d   d cd cd cd cd cd  d d  da da da da da d   d ed ed ed

cedcebaecdbceacbde
ab ab ab ab ab ab a   a ea ea ea ea ea  a a  ac ac ac ac 
 c c  ce ce  e e  eb eb  b cb cb c   c ec ec e  eb eb  b 
de de d   d cd cd cd cd cd  d d  db db db db db d   d ed

cedcebaecdbceacbdea
ab ab ab ab ab ab a   a ea ea ea ea ea  a a  ac ac ac ac  c 
 c c  ce ce  e e  eb eb  b cb cb c   c ec ec e  eb eb  b ab 
de de d   d cd cd cd cd cd  d d  db db db db db d   d ed ed

cedcebaecdbceacbdeac
ab ab ab ab ab ab a   a ea ea ea ea ea  a a  ac ac ac ac  c c  
 c c  ce ce  e e  eb eb  b cb cb c   c ec ec e  eb eb  b ab ab 
de de d   d cd cd cd cd cd  d d  db db db db db d   d ed ed ed

cedcebaecdbceacbdeb
ab ab ab ab ab ab a   a ea ea ea ea ea  a a  ac ac ac ac ac 
 c c  ce ce  e e  eb eb  b cb cb c   c ec ec e  eb eb  b b  
de de d   d cd cd cd cd cd  d d  db db db db db d   d ed ed

cedcebaecdbceacbdebc
ab ab ab ab ab ab a   a ea ea ea ea ea  a a  ac ac ac ac ac a  
 c c  ce ce  e e  eb eb  b cb cb c   c ec ec e  eb eb  b b  bc 
de de d   d cd cd cd cd cd  d d  db db db db db d   d ed ed ed

Posted by Charlie on 2004-06-10 09:16:39

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info