Howdy, Stranger!

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

Categories

15 puzzle game

viv.viv. 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?


Comments

  • viv.viv. Member Posts: 72
  • Johnny13Johnny13 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'+
    'bSmbEmBbabDcBbFcBbDcDbaDmbCdcRmcFmacdNcBbCcDbaDmbdb'+
    'SmdEmaBdPcbeBcEbaDmcSmbdbCmacdRcbeBcEbaCmbQmbcCdcba'+
    'cBdRcBbecEbeaVmbdbBmaEdLcdDcBbeFbaWmdBmacQdBcbBcCbe'+
    'FbaVmcBmadDcIdGcbBcCbeEbaYmaUcbBcCbeEbeaWmaVcBbcDbe';_b:string=
    'DbeaWmaVcBbcDbeDbBeaLmKaMcbDcbCcBbcDbeEbeCacBaFmaDf'+
    'bcebcbaDcbcbGceEcbcHbaDbBeaCdfaEmaEfedcBeaCcBbcbEcb'+
    'ceEcecbeFbaEbeafdBfaEmaFfceBfaCcBbcbEcececbDecbeFba'+
    'EbBeacBfaEmaFfdcefabBcBecBbDcecCecBbecbeFbaEbBeaCfa'+
    'EmaeCfbcBbceabBcDebDcebebcCbeBbeBbeCbaFbeaCfaBmbBma';_c:string=
    'ceBfdeBfbcfaBcBebcebCcCeEbebBeBbeCbaFbBeaBfaBmcBmab'+
    'defdCfbebaBcbBecebBcbebeBbBeCbBeBbeCbebcEbeaBfaBmdB'+
    'mabedBcefbefbfacbaBebeCbebebDabegeBbeBbeBbcEbBeafaB'+
    'mdbmaBedefcBebcefaBbaheaheBbBehFaBheBbeBbaBbcEbBeaf'+
    'acCdcafecBfBbecfcbfabahCahBeBhaBdDaghebeCbabBcFbeaf';_d:string=
    'aBmdbmadcbfebcefcbeBfabBaiBaCiBhdBgBahghebeBbaBbCcE'+
    'beafaBmdBmacfcebfecbBeDfbaigBahEidagaiBhebebeaBbCcE'+
    'bBeBaBmcBmabcdbeBfbeEfbabaigagHidihebeBbaebDcFbeBaB'+
    'mbBmafebeCfebGfBaCigGidBihebebabebDcFbeBaEmafebeDfb'+
    'eGfaBigJiBhBebabeBbDcDbeBbBaEmafebFfBeBfceBfagihgIi';_e:string=
    'hebaebBebEcEbebeaEmaBfbDfbcdbCfbCfaBihDihCiBheahebe'+
    'BbDcFbeBbaEmaBfbCfcBfcBeEfacaBighCgCihehgebBebEcFbB'+
    'ebaEmaBfbBfbCfbfeEfaBcaBiBhEiBhghebeBbEcFbBebaEmaBf'+
    'bBfcBfbCfeCfacGgBahiBhgBhebeBbEcGbebaEmaBfbBfbBcDfe'+
    'CfagBjgDjgjaFgbeBbFcGbBeaEmaBfbJfefagDjgDjgjaDhabeB';_f:string=
    'bEcHbBeaEmaBfeGfDafGjgDjlkaBlaCbcbEcHbBeaEmaBfeFfaB'+
    'ljklHjgCjkakBlaCbcbEcIbeaEmaBfeCfCalBklJjgBjBkaBlab'+
    'cbcbFcIbeaEmaBfeBfaBljklBkljlHjlCklCabcbcbEcJbeaEma'+
    'BfeBfaBklBjlBkljlFjklBkBlBabcbBcbdDcbcHbeaEmaBfeBfa'+
    'CklBjlBkjklBjDklkClBabcbdbcdDcbcHbeaEmaBfefaBlCklBj';_g:string=
    'lBkjaFklaClabcbcdbdCcdBbcCbcEbaEmafCakBjlCkljklajla'+
    'CkClaClaBcbdcbdCcdBbcCbcEbaEmaFjkBjlBkljBlaklaElaBl'+
    'abcbcdbcdBcdcbBcCbcEbaEmaFjBkjlBkalklaBlaElalBacBbd'+
    'cbBdcBdcbBcCbcEbaEmaFjklBkaklaklaBlaElCacdbcdcbEdBb'+
    'BcHbcaEmaFjkBlkaBlaClalaDlBaladcbcdbcCdcdBbBcGbCcEm';_h:string=
    'aEjBkDlalaClalEaBlacdcbBdbcBdBcdBbBcHbcaEmaCjCkElaB'+
    'lBalalalagaBladcBbBdbCdBcdBbCcHbaEmajCkGlaBlBalBala'+
    'BgalacdcBbdcbBdCcdBbCcHbaEmaBkIlaBlDaBlagaBlacdbBcd'+
    'cbBdDcBbCcHbaEmaIlBalalaDlaBgalabBcbBcdcbBdDcBbCcHb'+
    'aEmaGlBaDlBaClaBgalacbBcbcdBcbdCcdcBbCcEbcBbaEmBaDl';_i:string=
    'BafaHlaBgaBlabBcbBcdBcbdCcdBcbCcDbcdcbaCmcmalDalaBf'+
    'BaDlBaBgaBlacbBcbBcdBcbdBcCdcbCcEbcBbaBmcdcaElBaDfD'+
    'aBgBaClacbBcbEcbDcdBcbCcHbaCmcmaDlalaDfaCgBaDlaBcbB'+
    '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];-)
Sign In or Register to comment.