Schuifpuzzel

Hallo,

Ik zou graag het minimaal aantal zetten van een 2*5 schuifpuzzel willen bepalen. Heeft iemand een idee of er een algoritme ofzo voor bestaat?

De puzzel zou er zo moeten uitzien
1 2 3 4 5
6 7 8 9 x

En je moet vertrekken van dit
x 6 1 2 5
7 3 8 4 9

Wat ik wil weten is het minimale aantal zetten. Kan iemand mij helpen?

Alvast bedankt
M

Martin
Student universiteit België - dinsdag 19 november 2013

Antwoord

Laat een computerprogramma zoals Pascal het gewoon een aantal malen proberen.

Bij zo'n poging heb je op elk moment twee of drie mogelijke zetten. Je probeert er een op goed geluk.

Laat 0 het lege vakje representeren.

De kern van het programma zou bijvoorbeeld als volgt kunnen zijn:

begin
rij1(1):=0; rij1(2):=6; ... (etc);
rij2(1):=7; rij2(2):=3; ... (etc);
while not (rij1(1)=1 and rij1(2)=2 and ... and rij2(4)=9) do
begin
t:=0 {het aantal zetten tot nu toe};
legeplaatsrij:=1; legeplaatskolom:=1;
repeat
i:=legeplaatsrij; j:=legeplaatskolom; doezet
until legeplaatsrij=2 and legeplaatskolom=5
end;
writeln(t)
end.

procedure doezet;
begin
t:=t+1;
if i=1 and j=1 then if random$>$0.5 then
begin legeplaatskolom:=2; rij1(1):=rij1(2); rij1(2):=0 end
else begin legeplaatsrij:=2; rij1(1):=rij2(1); rij2(1):=0 end;
if i=2 and j=1 then ...;
if i=1 and j=5 then ...;
if i=2 and j=5 then ...;
if not (j=1 or j=5) then
begin r:=random; if r$<$1/3 then ... else if r$>$2/3 then ... else ...
end;

Je kunt dit programma dan zo vaak runnen als je wilt.
Iedere keer krijg je een nieuw aantal zetten.
Hou zelf het minimum aantal zetten bij.

Nou ja, dit is een begin. We moeten er wel wat beleid aan toevoegen, anders wordt het geschuifel eindeloos ...

woensdag 20 november 2013

©2001-2024 WisFaq