All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 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 13 |

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 (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2019 by Animus Pactum Consulting. All rights reserved. Privacy Information