#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

# 15 puzzle game

Member Posts: 72
hi.
the 15 puzzle game is the game with the sliding tiles which u must slide adround until you reform the picture. there is 1 empty square which allows you to slide the other tiles, to make the picture. it is
4 X 4 frame, so there are 15 tiles.
if we have this game and the tiles re numbere 1,2,3,...15, it is the 15 puzzle. i need to create an algorithm which given the position of the tiles, i must give the users the ways of moving the empty space in order to get to the final position in the least posible moves.
the final position is when each tile is in its proper position.
eg.
from the following position,
1 3 6 7
2 5 4 0
8 10 12 14
9 11 13 15
we must get to
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0
where 0 represents the empty space.

btw. why doesn't it have a algorithms messageboard?

• Member Posts: 72
• Member Posts: 128
[code]uses graph; const vtx:array[0..153]of word=(
02,12,05,13,06,16,09,13,13,13,09,18,13,22,10,23,06,20,06,24,03,23,
02,12,16,13,18,14,19,19,23,20,23,13,25,13,25,22,17,23,16,13,28,13,
31,13,30,21,37,20,36,24,28,23,28,13,45,13,47,13,49,23,47,23,46,21,
43,21,41,23,39,23,45,13,45,16,46,19,43,19,45,16,51,17,56,17,56,19,
51,19,51,17,59,12,66,13,66,19,62,19,61,23,59,24,59,12,61,15,64,15,
64,17,61,17,61,15,69,13,71,14,72,19,76,20,76,13,78,13,78,22,70,23,
69,13,82,13,89,13,90,14,85,21,90,21,89,24,81,23,84,16,81,16,82,13);
vc:array[0..48]of byte=(12,9,7,9,4,5,7,5,9,10,0,0,0,
20,40,52,40,56,60,60,60,60,4,20,40,0,4,24,36,12,0,
56,32,12,60,52,44,56,8,36,24,0,4,40,0,20,63,31,33);J13:string=
'VmOaKmbZmBbCmBaBcbIcCbBaImcYmcBdcBaCbBcFbEcCbBaFmbd'+
'cBdRcBbecEbeaVmbdbBmaEdLcdDcBbeFbaWmdBmacQdBcbBcCbe'+
'ceEcecbeFbaEbeafdBfaEmaFfceBfaCcBbcbEcececbDecbeFba'+
'EbBeacBfaEmaFfdcefabBcBecBbDcecCecBbecbeFbaEbBeaCfa'+
'EmaeCfbcBbceabBcDebDcebebcCbeBbeBbeCbaFbeaCfaBmbBma';_c:string=
'ceBfdeBfbcfaBcBebcebCcCeEbebBeBbeCbaFbBeaBfaBmcBmab'+
'defdCfbebaBcbBecebBcbebeBbBeCbBeBbeCbebcEbeaBfaBmdB'+
'mabedBcefbefbfacbaBebeCbebebDabegeBbeBbeBbcEbBeafaB'+
'mdbmaBedefcBebcefaBbaheaheBbBehFaBheBbeBbaBbcEbBeaf'+
'acCdcafecBfBbecfcbfabahCahBeBhaBdDaghebeCbabBcFbeaf';_d:string=
'beafaBmdBmacfcebfecbBeDfbaigBahEidagaiBhebebeaBbCcE'+
'bBeBaBmcBmabcdbeBfbeEfbabaigagHidihebeBbaebDcFbeBaB'+
'mbBmafebeCfebGfBaCigGidBihebebabebDcFbeBaEmafebeDfb'+
'eGfaBigJiBhBebabeBbDcDbeBbBaEmafebFfBeBfceBfagihgIi';_e:string=
'hebaebBebEcEbebeaEmaBfbDfbcdbCfbCfaBihDihCiBheahebe'+
'BbDcFbeBbaEmaBfbCfcBfcBeEfacaBighCgCihehgebBebEcFbB'+
'ebaEmaBfbBfbCfbfeEfaBcaBiBhEiBhghebeBbEcFbBebaEmaBf'+
'bBfcBfbCfeCfacGgBahiBhgBhebeBbEcGbebaEmaBfbBfbBcDfe'+
'bEcHbBeaEmaBfeGfDafGjgDjlkaBlaCbcbEcHbBeaEmaBfeFfaB'+
'ljklHjgCjkakBlaCbcbEcIbeaEmaBfeCfCalBklJjgBjBkaBlab'+
'cbcbFcIbeaEmaBfeBfaBljklBkljlHjlCklCabcbcbEcJbeaEma'+
'BfeBfaBklBjlBkljlFjklBkBlBabcbBcbdDcbcHbeaEmaBfeBfa'+
'CklBjlBkjklBjDklkClBabcbdbcdDcbcHbeaEmaBfefaBlCklBj';_g:string=
'lBkjaFklaClabcbcdbdCcdBbcCbcEbaEmafCakBjlCkljklajla'+
'CkClaClaBcbdcbdCcdBbcCbcEbaEmaFjkBjlBkljBlaklaElaBl'+
'abcbcdbcdBcdcbBcCbcEbaEmaFjBkjlBkalklaBlaElalBacBbd'+
'cbBdcBdcbBcCbcEbaEmaFjklBkaklaklaBlaElCacdbcdcbEdBb'+
'aEjBkDlalaClalEaBlacdcbBdbcBdBcdBbBcHbcaEmaCjCkElaB'+
'BgalacdcBbdcbBdCcdBbCcHbaEmaBkIlaBlDaBlagaBlacdbBcd'+
'BafaHlaBgaBlabBcbBcdBcbdCcdBcbCcDbcdcbaCmcmalDalaBf'+
'cbEcbDcdBcBbCcGbaFm_aVaFm'; var buf:array[0..4095]of byte;buf1,buf2:pointer;
Blk:array[0..15]of pointer;_:array[0..3,0..3]of byte;GD,GM,x,y,u,v,c:integer;
k,W:byte; procedure setpal(var pal;cnt:word);assembler;asm lds si,pal
mov dx,968; mov al,0; out dx,al; inc dx; mov cx,cnt; rep outsb end;
label Cht; procedure dec0de(var buf1;var buf2);assembler;label L0,L1,L2;asm
lds si,buf1; les di,buf2; mov ax,60; stosw; stosw; xor dx,dx; L0:mov cx,1;
L1:lodsb; cmp al,0; jl L1; cmp al,96; ja L2; sub al,64; mov cx,ax; jmp L1;
L2:sub al,97; mov bx,cx; rep stosb; add dx,bx; cmp dx,3600; jb L0 end;
procedure swp(a,b:byte);begin c:=_[v,u]; _[v,u]:=_[b,a]; _[b,a]:=c end;
function kb:byte;inline(\$b4/0/\$cd/22/\$86/\$e0); procedure m0ve(a,b,c:integer);
begin if(k=a)then begin swp(u+b,v+c); u:=u+b; v:=v+c end end;
procedure VGA13;external;{\$L VGA13.OBJ} procedure FNT;external;{\$L LITT.OBJ}
begin GD:=InstallUserDriver('VGA256',nil); RegisterBGIdriver(@VGA13);
InitGraph(GD,GM,''); buf1:=@J13; buf2:=@buf; for c:=0 to 13 do begin
SetColor(c+18); SetFillStyle(1,c+18); PieSlice(159,95,0,360,180-(c*13)) end;
SetColor(60);x:=0;for c:=0 to 9 do begin DrawPoly(vc[c],vtx[x]);x:=x+vc[c]*2
end; Randomize; SetColor(32); OutTextXY(0,0,GetModeName(0)); SetColor(15);
SetTextStyle(RegisterBGIfont(@FNT),0,0); OutTextXY(234,186,'Johnny13 2004');
for c:=0 to 3 do begin SetColor(c+52); Rectangle(95-c,35-c,224+c,164+c) end;
setpal(vc[10],39); dec0de(buf1^,buf2^); for y:=0 to 59 do for x:=0 to 59 do
begin SetFillStyle(1,buf[4+y*60+x]); Bar(100+x*2,40+y*2,100+x*2+1,40+y*2+1);
end; c:=0; for y:=0 to 3 do for x:=0 to 3 do begin GetMem(Blk[c],999);
GetImage(100+x*30,40+y*30,129+x*30,69+y*30,Blk[c]^); inc(c); end;
SetFillStyle(1,80); Bar(96,36,223,163); repeat FillChar(_,16,19); inc(k);
for c:=0 to 15 do begin repeat u:=Random(4); v:=Random(4); until _[v,u]=19;
_[v,u]:=c;PutImage(97+u*32,37+v*32,Blk[c]^,0);end;until(k=133); _[v,u]:=19;
repeat k:=kb; if(k=59)then for y:=0 to 3 do for x:=0 to 3 do begin
if(_[y,x]=v*4+u)then begin swp(x,y);u:=x;v:=y;goto Cht;end;end;Cht:if(k=61)
then for y:=0 to 15 do for x:=0 to 15 do begin SetFillStyle(1,y*16+x);
Bar(250+x*4,32+y*4,250+x*4+2,32+y*4+2); end; SetFillStyle(1,80);
if(v>0)then m0ve(72,0,-1); if(v<3)then m0ve(80,0,1);
if(u>0)then m0ve(75,-1,0); if(u<3)then m0ve(77,1,0);
W:=0; for y:=0 to 3 do for x:=0 to 3 do begin if(_[y,x]=y*4+x)then inc(W);
if(_[y,x]<19)then PutImage(97+x*32,37+y*32,Blk[_[y,x]]^,0) else
Bar(97+x*32,37+y*32,97+x*32+29,37+y*32+29) end until(k=1)or(W=15);
if(W=15)then begin Bar(96,36,223,163); for y:=0 to 3 do for x:=0 to 3 do
PutImage(99+x*30,40+y*30,Blk[y*4+x]^,0); kb end; CloseGraph end.[/code];-)