mnogo dama, a samo jedna tabla

mnogo dama, a samo jedna tabla 19.04.2005. u 21:13 · pre 261 meseci #1

Da li neko moze da mi pomogne oko sledeceg zadatka: Napisati program (u Paskalu) koji ce 8 dama (ili kraljica, kako hocete) rasporediti po sahovskoj tabli tako da ni jedna od njih ne moze da napadne drugu.
Ne trazim gotov kod, vec samo da me uputite u kom pravcu da razmisljam. Pokusao sam preko kvadratne matrice 8*8, ali nisam uspio i zaista nemam ideju kako da rjesim taj zadatak.
Hvala!

vektorska grafika 19.04.2005. u 22:08 · pre 261 meseci #2

Probaj sa knjigom "Algoritmi u programskom jeziku C "(ili tako nekako) u izdanju Mikroknjige
pa prevedi to na Paskal :"

Potpis

Tape loading error

Re: mnogo dama, a samo jedna tabla 19.04.2005. u 22:53 · pre 261 meseci #3

Koristeci backtrack mozes generisati sve moguce takve kombinacije. I niz je dovoljan za rad. Posto u svakom redu(ili koloni) moze stajati samo jedna kraljica dovoljno ti je da pamtis ovako nesto tabla[1]:=5 sto bi znacilo da se u provom redu kraljica nalazi na 5-om mestu.

Potpis

Don’t do drugs, sleep deprivation is better.

Re: mnogo dama, a samo jedna tabla 19.04.2005. u 23:08 · pre 261 meseci #4

Evo ti prepričano iz navedene knjige:

Imaš par različitih rešenja… Jedno je da isprobaš sve moguće kombinacije, kojih ima samo 4.426.165.368

A ako primeniš da dve kraljice ne mogu stojati u istoj vrsti i/ili istoj koloni, onda se broj kombinacja drastično smanjuje na 40320. A možeš i da uradiš sledeće:

Imaš n kraljica.

1) Postaviš kraljicu negde na prvu kolonu
2) Rešavaš problem: postaviti n-1 kraljica u n-1 preostalih kolona tako da se međusobno ne napadaju i da se ne napadaju sa n-tom.

Korak dva se razbija na:

1) Postaviš kraljicu na drugu kolonu tako da se ne napada sa prvom.
2) Postaviš n-2 kraljica tako da se ne napadju međusobno i sa prethodne dve.

U principu problem može da se reši sa n ugnježdenih for petlji, ali ako ti n nije poznato, onda rekurzivno.

Re: mnogo dama, a samo jedna tabla 20.04.2005. u 01:00 · pre 261 meseci #5

Napravi se gore pomenuti niz a=[1,2,3,4,5,6,7,8]
prodju se sve pernutacije niza a (ima ih kao sto je rekao Alef - 40320)
Za svaku permutaciju se proveri da li a[ i ] (i=1..8) tuce nekog na dole-desno ili na gore desno.
Ova procedura NextPermute samo daje sledecu permutaciju niza a.
Mislim da nisam koristio ni jednu naredbu koju obican paskal ne podrzava.

Code:

const
  N=8;
type
  niz=array[1..n] of integer;

function NextPermute(var x:niz): Boolean;
procedure swap(i:integer; j:integer);
var
   temp : byte;
begin
     temp := x[i];
     x[i] := x[j];
     x[j] := temp;
end;
var
   k,j,r,s : integer;
begin
     k := n-1;
     while (k>0) and (x[k] > x[k+1]) do
           k:=k-1;
     if k<1 then
        result:=false
     else
        begin
          j := n;
          while x[k] > x[j] do
                j:=j-1;
          swap(j,k);
          r:=n;
          s:=k+1;
          while r>s do
                begin
                     swap(r,s);
                     r:=r-1;
                     s:=s+1;
                end;
          result:=true;
        end;
end;

var
  i,j, svi: integer;
  bije:boolean;
  a: niz;
begin
   svi :=0;
   for i := 1 to n do
    a[i]:=i;
   repeat
    bije := false;
    for i := 1 to 8 do
      begin
        for j := 1 to a[i]-1 do
          bije := bije or (a[i+j]=(a[i]-j));
        for j := 1 to n-a[i]  do
          bije := bije or (a[i+j]=(a[i]+j));
      end;
    if not bije then
      begin
        for i := 1 to 8 do
          write(chr(ord('A')+i-1)+chr(ord('0')+a[i])+' ');
        writeln;
        inc(svi);
      end;
   until not nextpermute(a);
   writeln('Ukupno ', svi,' resenja');
   readln;
end.

Re: mnogo dama, a samo jedna tabla 20.04.2005. u 03:50 · pre 261 meseci #6

Ovo je školski primer za backtracking algoritam. Uprkos tome što je ovakav algoritam teoretski očajno neoptimalan (ima složenost $O(n^n)$ ) često se primenjuje baš na ovakvim problemima, jer se rešenje pronalazi u praksi obično mnogo ranije nego što mu to gornji limit nalaže. Naravno, preporučuje se za male $n$ , kompjuteri jesu sve brži, ali sve ima svoje granice :)

Re: mnogo dama, a samo jedna tabla 20.04.2005. u 08:30 · pre 261 meseci #7

Da, ali onda primenis neku heuristiku za biranje kolone, a ne pocinjes

uvek od prve. Na primer ako pocnes pretragu od sredine i naizmenicno

pretrazujes s obe strane pre ces doci do resenja. Ima jos boljih

heuristika, verovatno ih ima i na internetu.

Re: mnogo dama, a samo jedna tabla 20.04.2005. u 10:44 · pre 261 meseci #8

Ok mislim da je peromalosutra shvatio kako se radi. Covek trazio samo nagovestaj a mi opalili diskusiju a evo Toyo je i skoro citav kod bacio.

Sta ti je ES...covek trazi prst a dobije citavu saku :)

Potpis

Don’t do drugs, sleep deprivation is better.

Re: mnogo dama, a samo jedna tabla 20.04.2005. u 10:52 · pre 261 meseci #9

Hvala vam puno svima, narocito Toyo-i! Mislim da sam shvatio sustinu, ali cu morati jos malo "mozgati" nad ovim!

Srodne teme