拉斯维加斯算法有个特点，一旦发现算不下去了，便会全部推倒重来。也许，没必要全部推倒重来。如果象“回溯”一样退回几步重算，可能答案就出来了。 下面是我自己改进的拉斯维加斯算法，在算100皇后或者更多皇后的问题上，比原来的算法效率要高出很多。我称这样方法为“伪回溯”。 (*     One Answer Of N Queens Problem.     Arithmetic Of j.t.Chang's LV. *) program LV_Queens; const      N=100; var     x:array[1..N] of integer;     i:integer; procedure PrintResult; var     i,j: integer;     t1,t2:longint;     f:text;     ch: char; begin     for i:=1 to N do write(x[i]:5);     Readln; end; function place(k,a:integer):boolean; var     i:integer; begin    for i:=1 to k-1 do       if (k-i)=abs(a-x[i])  then         begin             place:=false;             exit;         end;    place:=true; end; procedure  queensLV; var     i,j,k,c,t,stop: integer; begin    for i:=1 to N do x[i]:=i;    k:=1; c:=1;  stop:=1;    randomize;    while  (k<=N)  do      begin          c:=0;          for j:=k to N do            if place(k,x[j]) then              begin                  c:=c+1;                  if random(c)=0 then t:=j;              end;          if c>0 then            begin                if(t<>k) then                  begin                      x[k]:=x[k] xor x[t];                      x[t]:=x[t] xor x[k];                      x[k]:=x[k] xor x[t];                  end;                k:=k+1;            end              else                begin                   k:=k-stop;                   stop:=stop+1;                   if k<1 then                     begin                         k:=1;                         stop:=1;                     end;                end;      end; end; begin      writeln('N Queens Problem.');      writeln('Programmed by j.t.Chang.');      writeln('Finding one answer of ',N,' queens problem.');      writeln('Please wait...');      for  i:=1 to N do x[i]:=0;      queensLV;      PrintResult; end.  

评论