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.
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 |
computer solution based on previous Sliding Puzzle program
