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

 Sliding Puzzle III (Posted on 2022-10-12)
You have a sliding puzzle that looks like this:
```+---+---+---+---+
| A | B | C | D |
+---+---+---+---+
|   | E | F | G |
+---+---+---+---+
| H | I | J | K |
+---+---+---+---+```
You may move a block with a letter on it to the blank space by sliding it there.

Determine the minimum number of moves it takes to put K where H is, J where I is, I where J is, and H where K is at the same time. (In other words, changing the configuration in row-3 from HIJK to KJIH.)

Note: The other pieces don't need to be in their original spots.

 See The Solution Submitted by K Sengupta Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer solution based on previous Sliding Puzzle program | Comment 1 of 5
The least number of steps is 25. There are five variations. I've placed the five variations next to one another. The program involved is a variation of the one for Sliding Puzzle II.

Read each of the five variations vertically.

```    25       25        25        25       25
0        0         0         0        0ABCD     ABCD      ABCD      ABCD     ABCD.EFG     .EFG      .EFG      .EFG     .EFGHIJK     HIJK      HIJK      HIJK     HIJK                                            1        1         1         1        1ABCD     ABCD      ABCD      ABCD     ABCDHEFG     E.FG      E.FG      E.FG     E.FG.IJK     HIJK      HIJK      HIJK     HIJK                                            2        2         2         2        2ABCD     ABCD      ABCD      ABCD     ABCDHEFG     EIFG      EIFG      EIFG     EIFGI.JK     H.JK      H.JK      H.JK     H.JK                                            3        3         3         3        3ABCD     ABCD      ABCD      ABCD     ABCDH.FG     EIFG      EIFG      EIFG     EIFGIEJK     HJ.K      HJ.K      HJ.K     .HJK                                            4        4         4         4        4ABCD     ABCD      ABCD      ABCD     ABCD.HFG     EIFG      EIFG      EIFG     .IFGIEJK     HJK.      HJK.      HJK.     EHJK                                            5        5         5         5        5ABCD     ABCD      ABCD      ABCD     ABCDIHFG     EIF.      EIF.      EIF.     I.FG.EJK     HJKG      HJKG      HJKG     EHJK                                            6        6         6         6        6ABCD     ABCD      ABCD      ABCD     ABCDIHFG     EI.F      EI.F      EI.F     IHFGE.JK     HJKG      HJKG      HJKG     E.JK                                            7        7         7         7        7ABCD     ABCD      ABCD      ABCD     ABCDIHFG     EIKF      E.IF      E.IF     IHFGEJ.K     HJ.G      HJKG      HJKG     EJ.K                                            8        8         8         8        8ABCD     ABCD      ABCD      ABCD     ABCDIHFG     EIKF      EJIF      EJIF     IHFGEJK.     H.JG      H.KG      H.KG     EJK.                                            9        9         9         9        9ABCD     ABCD      ABCD      ABCD     ABCDIHF.     EIKF      EJIF      EJIF     IHF.EJKG     .HJG      .HKG      .HKG     EJKG                                           10       10        10        10       10ABCD     ABCD      ABCD      ABCD     ABCDIH.F     .IKF      .JIF      .JIF     IH.FEJKG     EHJG      EHKG      EHKG     EJKG                                           11       11        11        11       11ABCD     ABCD      ABCD      ABCD     ABCDI.HF     I.KF      J.IF      J.IF     I.HFEJKG     EHJG      EHKG      EHKG     EJKG                                           12       12        12        12       12ABCD     ABCD      ABCD      ABCD     ABCDIJHF     IK.F      JHIF      JI.F     IJHFE.KG     EHJG      E.KG      EHKG     E.KG                                           13       13        13        13       13ABCD     ABCD      ABCD      ABCD     ABCDIJHF     IKJF      JHIF      JIKF     IJHFEK.G     EH.G      EK.G      EH.G     EK.G                                           14       14        14        14       14ABCD     ABCD      ABCD      ABCD     ABCDIJ.F     IKJF      JH.F      JIKF     IJ.FEKHG     E.HG      EKIG      E.HG     EKHG                                           15       15        15        15       15ABCD     ABCD      ABCD      ABCD     ABCDI.JF     I.JF      J.HF      J.KF     I.JFEKHG     EKHG      EKIG      EIHG     EKHG                                           16       16        16        16       16ABCD     ABCD      ABCD      ABCD     ABCD.IJF     .IJF      .JHF      JK.F     .IJFEKHG     EKHG      EKIG      EIHG     EKHG                                           17       17        17        17       17ABCD     ABCD      ABCD      ABCD     ABCDEIJF     EIJF      EJHF      JKF.     EIJF.KHG     .KHG      .KIG      EIHG     .KHG                                           18       18        18        18       18ABCD     ABCD      ABCD      ABCD     ABCDEIJF     EIJF      EJHF      JKFG     EIJFK.HG     K.HG      K.IG      EIH.     K.HG                                           19       19        19        19       19ABCD     ABCD      ABCD      ABCD     ABCDE.JF     E.JF      EJHF      JKFG     E.JFKIHG     KIHG      KI.G      EI.H     KIHG                                           20       20        20        20       20ABCD     ABCD      ABCD      ABCD     ABCDEJ.F     EJ.F      EJ.F      JKFG     EJ.FKIHG     KIHG      KIHG      E.IH     KIHG                                           21       21        21        21       21ABCD     ABCD      ABCD      ABCD     ABCDEJF.     EJF.      EJF.      J.FG     EJF.KIHG     KIHG      KIHG      EKIH     KIHG                                           22       22        22        22       22ABCD     ABCD      ABCD      ABCD     ABCDEJFG     EJFG      EJFG      .JFG     EJFGKIH.     KIH.      KIH.      EKIH     KIH.                                           23       23        23        23       23ABCD     ABCD      ABCD      ABCD     ABCDEJFG     EJFG      EJFG      EJFG     EJFGKI.H     KI.H      KI.H      .KIH     KI.H                                           24       24        24        24       24ABCD     ABCD      ABCD      ABCD     ABCDEJFG     EJFG      EJFG      EJFG     EJFGK.IH     K.IH      K.IH      K.IH     K.IH                                           25       25        25        25       25ABCD     ABCD      ABCD      ABCD     ABCDE.FG     E.FG      E.FG      E.FG     E.FGKJIH     KJIH      KJIH      KJIH     KJIH```

Made by slight changes to the program for Sliding Puzzle II:

(The limit was initially 28, as a guess, then lowered to 26, when a 25-step solution was found, so as to speed up the search. The limit is one higher than the number of steps as it includes the initial position and the end position.)

clearvars,clc
global lvl hist limit blank nbors histS
board=['xxxx';'.xxx';'HIJK'];
hist={board};
limit=26;
blank=[2,1];
nbors=[-1,0;1,0;0,1;0,-1];
lvl=0;
boardS=['ABCD';'.EFG';'HIJK'];
histS={boardS};

global lvl hist limit blank nbors histS
lvl=lvl+1;
for i=1:4
saveBlank=blank;
saveHist=hist; saveHistS=histS;
board=hist{end}; boardS=histS(end);
blank=find( ismember(board(:),'.') );
[blank1,blank2]=  ind2sub([3,4],blank);
blank=[blank1,blank2];
newblank=blank+nbors(i,:);
newboard=hist{end};newboardS=histS{end};
if  newblank(1)<=3 &&  newblank(2)<=4 && min(newblank)>=1
newboard(blank(1),blank(2))=newboard(newblank(1),newblank(2));
newboard(newblank(1),newblank(2))='.';
newboardS(blank(1),blank(2))=newboardS(newblank(1),newblank(2));
newboardS(newblank(1),newblank(2))='.';

if length(hist)>1
if isequal(hist{end-1},newboard)
continue
end
end
good=true;
for j=1:length(hist)-2
if isequal(hist(j),newboard)
good=false;
break
end
end
if good==false
blank=saveBlank;
hist=saveHist;
continue
end
hist{end+1}=newboard; histS{end+1}=newboardS;
blank=newblank;

if isequal(newboard(3,:),'KJIH')
disp(length(histS)-1)
for wh=1:length(histS)
disp(wh-1)
disp(histS{wh})
disp(' ')
end
else
if length(hist)<limit
end
end
hist=hist(1:end-1);histS=histS(1:end-1);
end
blank=saveBlank;
hist=saveHist; histS=saveHistS;
end
lvl=lvl-1;
end

 Posted by Charlie on 2022-10-12 11:11:43

 Search: Search body:
Forums (0)