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

Home > General
Sliding Puzzle III (Posted on 2022-10-12) Difficulty: 3 of 5
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.)
Solution 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        0
ABCD     ABCD      ABCD      ABCD     ABCD
.EFG     .EFG      .EFG      .EFG     .EFG
HIJK     HIJK      HIJK      HIJK     HIJK
                                       
     1        1         1         1        1
ABCD     ABCD      ABCD      ABCD     ABCD
HEFG     E.FG      E.FG      E.FG     E.FG
.IJK     HIJK      HIJK      HIJK     HIJK
                                       
     2        2         2         2        2
ABCD     ABCD      ABCD      ABCD     ABCD
HEFG     EIFG      EIFG      EIFG     EIFG
I.JK     H.JK      H.JK      H.JK     H.JK
                                       
     3        3         3         3        3
ABCD     ABCD      ABCD      ABCD     ABCD
H.FG     EIFG      EIFG      EIFG     EIFG
IEJK     HJ.K      HJ.K      HJ.K     .HJK
                                       
     4        4         4         4        4
ABCD     ABCD      ABCD      ABCD     ABCD
.HFG     EIFG      EIFG      EIFG     .IFG
IEJK     HJK.      HJK.      HJK.     EHJK
                                       
     5        5         5         5        5
ABCD     ABCD      ABCD      ABCD     ABCD
IHFG     EIF.      EIF.      EIF.     I.FG
.EJK     HJKG      HJKG      HJKG     EHJK
                                       
     6        6         6         6        6
ABCD     ABCD      ABCD      ABCD     ABCD
IHFG     EI.F      EI.F      EI.F     IHFG
E.JK     HJKG      HJKG      HJKG     E.JK
                                       
     7        7         7         7        7
ABCD     ABCD      ABCD      ABCD     ABCD
IHFG     EIKF      E.IF      E.IF     IHFG
EJ.K     HJ.G      HJKG      HJKG     EJ.K
                                       
     8        8         8         8        8
ABCD     ABCD      ABCD      ABCD     ABCD
IHFG     EIKF      EJIF      EJIF     IHFG
EJK.     H.JG      H.KG      H.KG     EJK.
                                       
     9        9         9         9        9
ABCD     ABCD      ABCD      ABCD     ABCD
IHF.     EIKF      EJIF      EJIF     IHF.
EJKG     .HJG      .HKG      .HKG     EJKG
                                       
    10       10        10        10       10
ABCD     ABCD      ABCD      ABCD     ABCD
IH.F     .IKF      .JIF      .JIF     IH.F
EJKG     EHJG      EHKG      EHKG     EJKG
                                       
    11       11        11        11       11
ABCD     ABCD      ABCD      ABCD     ABCD
I.HF     I.KF      J.IF      J.IF     I.HF
EJKG     EHJG      EHKG      EHKG     EJKG
                                       
    12       12        12        12       12
ABCD     ABCD      ABCD      ABCD     ABCD
IJHF     IK.F      JHIF      JI.F     IJHF
E.KG     EHJG      E.KG      EHKG     E.KG
                                       
    13       13        13        13       13
ABCD     ABCD      ABCD      ABCD     ABCD
IJHF     IKJF      JHIF      JIKF     IJHF
EK.G     EH.G      EK.G      EH.G     EK.G
                                       
    14       14        14        14       14
ABCD     ABCD      ABCD      ABCD     ABCD
IJ.F     IKJF      JH.F      JIKF     IJ.F
EKHG     E.HG      EKIG      E.HG     EKHG
                                       
    15       15        15        15       15
ABCD     ABCD      ABCD      ABCD     ABCD
I.JF     I.JF      J.HF      J.KF     I.JF
EKHG     EKHG      EKIG      EIHG     EKHG
                                       
    16       16        16        16       16
ABCD     ABCD      ABCD      ABCD     ABCD
.IJF     .IJF      .JHF      JK.F     .IJF
EKHG     EKHG      EKIG      EIHG     EKHG
                                       
    17       17        17        17       17
ABCD     ABCD      ABCD      ABCD     ABCD
EIJF     EIJF      EJHF      JKF.     EIJF
.KHG     .KHG      .KIG      EIHG     .KHG
                                       
    18       18        18        18       18
ABCD     ABCD      ABCD      ABCD     ABCD
EIJF     EIJF      EJHF      JKFG     EIJF
K.HG     K.HG      K.IG      EIH.     K.HG
                                       
    19       19        19        19       19
ABCD     ABCD      ABCD      ABCD     ABCD
E.JF     E.JF      EJHF      JKFG     E.JF
KIHG     KIHG      KI.G      EI.H     KIHG
                                       
    20       20        20        20       20
ABCD     ABCD      ABCD      ABCD     ABCD
EJ.F     EJ.F      EJ.F      JKFG     EJ.F
KIHG     KIHG      KIHG      E.IH     KIHG
                                       
    21       21        21        21       21
ABCD     ABCD      ABCD      ABCD     ABCD
EJF.     EJF.      EJF.      J.FG     EJF.
KIHG     KIHG      KIHG      EKIH     KIHG
                                       
    22       22        22        22       22
ABCD     ABCD      ABCD      ABCD     ABCD
EJFG     EJFG      EJFG      .JFG     EJFG
KIH.     KIH.      KIH.      EKIH     KIH.
                                       
    23       23        23        23       23
ABCD     ABCD      ABCD      ABCD     ABCD
EJFG     EJFG      EJFG      EJFG     EJFG
KI.H     KI.H      KI.H      .KIH     KI.H
                                       
    24       24        24        24       24
ABCD     ABCD      ABCD      ABCD     ABCD
EJFG     EJFG      EJFG      EJFG     EJFG
K.IH     K.IH      K.IH      K.IH     K.IH
                                       
    25       25        25        25       25
ABCD     ABCD      ABCD      ABCD     ABCD
E.FG     E.FG      E.FG      E.FG     E.FG
KJIH     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};
addon

function addon

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

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