You have a sliding puzzle that looks like this:
+---+---+---+
| A | B | C |
+---+---+---+
| | D | E |
+---+---+---+
| F | G | H |
+---+---+---+
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 H where F is and, F where H is at the same time.(In other words, changing the configuration in row-3 from FGH to HGF.)
Note: The other pieces don't need to be in their original spots.
clearvars,clc
global lvl hist limit blank nbors
board=['xxx';'.xx';'FGH'];
hist={board};
limit=18;
blank=[2,1];
nbors=[-1,0;1,0;0,1;0,-1];
lvl=0;
addon
function addon
global lvl hist limit blank nbors
lvl=lvl+1;
for i=1:4
saveBlank=blank;
saveHist=hist;
board=hist{end};
blank=find( ismember(board(:),'.') );
[blank1,blank2]= ind2sub([3,3],blank);
blank=[blank1,blank2];
newblank=blank+nbors(i,:);
newboard=hist{end};
if max(newblank)<=3 && min(newblank)>=1
newboard(blank(1),blank(2))=newboard(newblank(1),newblank(2));
newboard(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;
blank=newblank;
if isequal(newboard(3,:),'HGF')
disp(length(hist)-1)
for wh=1:length(hist)
disp(wh-1)
disp(hist{wh})
disp(' ')
end
else
if length(hist)<limit
addon
end
end
hist=hist(1:end-1);
end
blank=saveBlank;
hist=saveHist;
end
lvl=lvl-1;
end
has some unnecessary code, entered when misdiagnosing a bug, but it finds a 17-step solution.
The steps are labeled. Blocks whose identity is not important are marked with an x. The empty position is marked with a dot.
17 steps
0 step zero; initial state
xxx
.xx
FGH
1
xxx
Fxx
.GH
2
xxx
Fxx
G.H
3
xxx
Fxx
GH.
4
xxx
Fx.
GHx
5
xxx
F.x
GHx
6
xxx
.Fx
GHx
7
xxx
GFx
.Hx
8
xxx
GFx
H.x
9
xxx
G.x
HFx
10
xxx
.Gx
HFx
11
.xx
xGx
HFx
12
x.x
xGx
HFx
13
xx.
xGx
HFx
14
xxx
xG.
HFx
15
xxx
xGx
HF.
16
xxx
xGx
H.F
17
xxx
x.x
HGF
Addition of a shadow history, shown below with capital S suffix, with actual letters A, B, C, D, and E, allows following all the blocks:
clearvars,clc
global lvl hist limit blank nbors histS
board=['xxx';'.xx';'FGH'];
hist={board};
limit=18;
blank=[2,1];
nbors=[-1,0;1,0;0,1;0,-1];
lvl=0;
boardS=['ABC';'.DE';'FGH'];
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,3],blank);
blank=[blank1,blank2];
newblank=blank+nbors(i,:);
newboard=hist{end}; newboardS=histS{end};
if max(newblank)<=3 && 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,:),'HGF')
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
17
0
ABC
.DE
FGH
1
ABC
FDE
.GH
2
ABC
FDE
G.H
3
ABC
FDE
GH.
4
ABC
FD.
GHE
5
ABC
F.D
GHE
6
ABC
.FD
GHE
7
ABC
GFD
.HE
8
ABC
GFD
H.E
9
ABC
G.D
HFE
10
ABC
.GD
HFE
11
.BC
AGD
HFE
12
B.C
AGD
HFE
13
BC.
AGD
HFE
14
BCD
AG.
HFE
15
BCD
AGE
HF.
16
BCD
AGE
H.F
17
BCD
A.E
HGF
This identifies the full final state of the puzzle when the goal has been accomplished. The letters are in clockwise order around the edge, rather than the reading order it started with.
The lower case 'x' values for anonymous blocks are used to prevent differing irrelevant letters from being recognized as the same, and preventing serious pruning of the possibilities.
|
|
Posted by Charlie
on 2022-09-28 11:23:35 |
computer solution (spoiler)
