Kênh Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
Wednesday, January 22, 2014



Quân Hậu trên bàn cờ Vua có thể ăn theo hàng, theo cột chứa nó hoặc theo đường chéo của hình vuông nhận nó làm đỉnh.
               a) Tìm một cách đặt N quân Hậu trên bàn cờ Vua kích thước N´ N ô sao cho không quân nào ăn được quân nào.
               b) Tìm mọi cách đặt N quân Hậu theo điều kiện trên. Ghi kết quả vào một tệp văn bản tên N_HAU.OUT.
Thuật toán
Trước hết ta đặt các quân Hậu ở mép ngoài bàn cờ. Hậu thứ i sẽ đứng ở đầu cột thứ i. Sau đó ta dịch dần các Hậu vào trong các dòng của bàn cờ và ghi nhận vị trí của chúng vào một mảng v. Phần tử v[i] của mảng v cho biết phải đặt Hậu thứ i, tức là Hậu chiếm cột i tại dòng v[i].
Thí dụ, với bàn cờ 4 ´ 4 ta có lời giải v = (2, 4, 1, 3) với ý nghĩa:
-          Đặt Hậu thứ nhất tại (cột 1) dòng 2, Hậu thứ 2 tại (cột 2) dòng 4, Hậu thứ 3 tại (cột 3) dòng 1 và Hậu thứ 4 tại (cột 4) dòng 3.
-          Mỗi khi đặt được Hậu thứ i ta chuyển qua Hậu tiếp theo i + 1. Điều kiện đặt được Hậu i trên dòng d của bàn cờ là nó không bị các Hậu đã đặt trước đó, tức là các Hậu j = 1..(i - 1) chiếu. Đây chính là tính chất P.
-          Hậu j < i chiếu (đụng độ) Hậu ikhi và chỉ khi v[j] = v[i] (cùng hàng) hoặc i - j = abs(v[i] - v[j]) (Hậu i và Hậu j nằm trên hai đỉnh đối diện của hình vuông, do đó hai cạnh liên tiếp của hình vuông này phải bằng nhau).
-          Tính chất Q khi đó sẽ là: đặt được đủ N Hậu.
Sơ đồ tìm một nghiệm XepHau1 như sau:
(*------------------------------------
   Tim 1 nghiem: xep M quan hau tren
    ban co M X M
------------------------------------*)
procedure XepHau1(M: byte);
var i: byte;
begin
if (M < 1) or (M > MN) then exit;
{MN = 20 la gioi han kich thuoc ban co}
n  :=   M;
  {Khởi trị: Đặt cỏc hậu 1..N ngoài bàn cờ.
      Hậu i Đặt tại đầu cột i, i=1..N.}
for i :=  1 to n do v[i] :=  0;
i :=  1; {Hậu đang xét}
repeat
if i > n then {co nghiem v[1..n]}
begin
    KetQua1(n); 
    exit;
end;
if i < 1 then {vo nghiem}
begin
    KetQua1(0);
    exit;
end;
if Tim(i) {co cach di }
  then inc(i) {Tien}
else  
begin {Lui}
v[i] :=  0;
dec(i);
end;
until false;
end;
Thủ tục có hai tình huống, KetQua1(n): hiển thị mảngv[1..n], trong đó v[i] là dòng đặt Hậu i, KetQua1(0): thông báo vô nghiệm.
Hàm Tim(i) thực hiện chức năng sau đây: xuất phát từ dòng Hậu i đang đứng là v[i] đẩy tiếp Hậu i xuống các dòng dưới để tìm được một dòng đặt nó sao cho không bị các Hậu đặt trước đó, tức là không bị các Hậu j = 1..(i – 1) ăn.
Tim(i)=true: tìm được một vị trí (dòng) đặt Hậu i, ngược lại Tim=false.
(*---------------------------------------
  Xuat phat tu dong v[i]+1, tim dong moi
          co the dat duoc Hau i
--------------------------------------*)
function Tim(i: byte): Boolean;
begin
Tim :=  true;
while v[i] < n do
begin
inc(v[i]);
if DatDuoc(i) then exit;
end;
Tim :=  false;
end;
Hàm Boolean DatDuoc(i) cho giá trị true nếu Hậu i không bị các Hậu
j = 1, 2,…, i – 1 đã đặt trước đó ăn. Ngược lại, nếu Hậu i bị một Hậu nào đó ăn thì hàm cho ra giá trị
false.
(*--------------------------------------
      Kiem tra xem co dat duoc Hau i
tai o (v[i],i) cua ban co khong ?
--------------------------------------*)
function DatDuoc(i: byte): Boolean;
var j: byte;
begin
DatDuoc :=  false;
for j :=  1 to i-1 do
    if (v[i] = v[j]) or (i-j = abs(v[i]-v[j]))
          {Hau j an duoc Hau i}
          then exit;
DatDuoc :=  true;
end;
Thao tác Tiến đơn giản là chuyển qua xét Hậu kế tiếp, Hậu i + 1.
Tien: Chuyển qua Hậu tiếp theo
      inc(i);
Thao tác Lùi đưa Hậu ra ngoài bàn cờ, chuyển qua xét Hậu trước đó, Hậu i – 1.
Lui: Đưa Hậu ra ngoài bàn cờ, chuyển qua Hậu trước đó
      v[i ]:= 0; dec(i);
Ta viết thủ tục XepHau để tìm mọi nghiệm của bài toán. Với bàn cờ 8 ´ 8 ta thu được 92 nghiệm. Với bàn cờ 10 ´ 10 ta thu được 724 nghiệm.
(*---------------------------------------
Tim moi cach dat M Hau tren ban co
                              M X M
--------------------------------------*)
procedure XepHau(M: byte);
var
      i: byte;
      d: integer; {dem so nghiem}
begin
if (M < 1) or (M > MN) then exit;
n :=  m;
for i :=  1 to n do v[i] :=  0;
assign(g,gn);
rewrite(g);
i :=  1; {Hau dang xet}
d :=  0; {dem so nghiem}
repeat
if i > n then {Tim duoc 1 nghiem}
begin
    inc(d);
    KetQua(d); {v[1..n] la nghiem thu d}
    i :=  n; {gia sai}
end;
if i < 1 then {Tim het cac nghiem}
begin
    writeln(g,'Tong cong ',d,' nghiem ');
    close(g);
    writeln('Xem ket qua trong file ',gn);
    readln;
    exit;
end;
if Tim(i) then inc(i)
else   begin
v[i] :=  0;
dec(i);
end;
until false;
end;
(*  Pascal  *)
(*============================
             N Hau
==============================*)
{$B-}
uses crt;
const
MN = 20;
gn = 'N_HAU.OUT';
BL = #32; {dau cach}
var
v: array[0..MN] of byte;
n: byte; {so quan hau, kich thuoc ban co}
g: text; {tep ket qua}
function DatDuoc(i: byte): Boolean; tự viết
function Tim(i: byte): Boolean; tự viết
(*---------------------------------------
      Hien thi nghiem tren man hinh
      Cho bai toan tim 1 nghiem
            k=0: vo nghiem
            k=n: co nghiem v[1..n]
--------------------------------------*)
procedure KetQua1(k: byte);
var i: byte;
begin
writeln;
if k = 0 then write('Vo nghiem')
    else
          for i :=  1 to k do write(v[i]:3);
writeln;
end;
(*------------------------------------
Tim 1 nghiem: xep M quan hau tren
                  ban co M X M
------------------------------------*)
procedure XepHau1(M: byte); tự viết
(*---------------------------------------
Ghi nghiem thu d vao tep g 'N_Hau.out'
            Bai toan tim moi nghiem
--------------------------------------*)
procedure KetQua(d: integer);
var i: byte;
begin
write(g,'Nghiem thu ',d,': ');
for i :=  1 to n do write(g,v[i],BL);
writeln(g);
end;
(*---------------------------------------
Tim moi cach dat M Hau tren ban co M X M
--------------------------------------*)
procedure XepHau(M: byte); tự viết
BEGIN
   XepHau1(8); {tim 1 nghiem}
XepHau(8); {tim du 92 nghiem}

END.
Phương án cải tiến
Ta xét một phương án cải tiến tập trung vào việc nâng cao tốc độ tính toán khi kiểm tra hai hậu đụng độ nhau. Mỗi khi tìm vị trí đặt hậu thứ i trên bàn cờ ta cần kiểm tra xem hậu i đó có đụng độ với tất cả (i-1) hậu đặt trước đó không.  Thời gian chi phí tập trung ở chính điểm này.
Để cải tiến, ta sẽ sử dụng thêm 3 mảng đánh dấu các dòng và các đường chéo của các hậu đã đặt trên bàn cờ với ý nghĩa là sau đây:
-          Mảng dd[1..n]  dùng để đánh dấu dòng. Nếu dd[i] = 0 tức là chưa có hậu nào chiếm dòng i, do đó có thể chọn dòng inày để đặt một hậu khác. Ngược lại, nếu dd[i] = 1 có nghĩa là đã có hậu nào đó được đặt trên dòng i. Các hậu khác không được phép chiếm dòng i đó nữa.
-           Mảng c1[-(n-1)..(n-1)] kiểm sóat các đường chéo theo hướng Tây Bắc - Đ”ng Nam. Ta tạm gọi là các đường chéo chính. Có cả thảy 2n-1 đường chéo trong bàn cờ vuông cạnh n. Nếu hậu i đặt trên dòng j thì sẽ kiểm soát đường chéo chính i-j. Như vậy khi c1[i-j] = 1 có nghĩa là đã có hậu kiểm soát đường chéo này. Ngược lại, khi c1[i-j] = 0 thì đường chéo này rỗi và ta có thể đặt một quân hậu vào “ (x,y) của bàn cờ, nếu y-x = i-j, trong đó, x, i là các tọa độ dòng và y, j là các tọa độ cột.
-          Mảng c2[2..2n] kiểm sóat các đường chéo theo hướng Đông Bắc - Tây Nam. Ta tạm gọi là các đường chéo phụ. Nếu hậu iđặt trên dòng j thì sẽ kiểm soát đường chéo phụ i+j. Như vậy khi c1[i+j] = 1 có nghĩa là đã có hậu kiểm soát đường chéo này. Ngược lại, khi c1[i+j] = 0 thì đường chéo này rỗi và ta có thể đặt một quân hậu vào “ (x,y) của bàn cờ, nếu y+x = i+j, trong đó, x, i là các tọa độ dòng và y, j là các tọa độ cột.
 Điều kiện để hậu i có thể đặt trên dòng j khi đó sẽ là:
 (dd[j] = 0) and (c1[i-j] = 0) and (c2[i+j] = 0), hay
 (dd[j] + c1[i-j] + c2[i+j] = 0)
 (*   Pascal   *)
(*============================
              N Hau
==============================*)
{$B-}
uses crt;
const
  MN = 20;
  gn = 'N_HAU.OUT';
  BL = #32; {dau cach} nl = #13#10; { Chuyen dong }
type    mi1 = array[0..MN] of integer;
var
  v:  mi1; { vi tri dat hau }
 c1: array[-mn..mn] of integer; { cheo 1 }
 c2: array[0..2*mn] of integer; { cheo 2 }
 dd: mi1;    { dong }
  n: integer; { so quan hau, kich thuoc ban co }
  g: text; { file ket qua }

(*--------------------------
   Nhac Hau i khoi ban co
     --------------------------*)
procedure NhacHau(i: integer);
begin
 if v[i] = 0 then exit;
 c1[i-v[i]]  :=  0; c2[i+v[i]]  :=  0;
 dd[v[i]]  :=  0;
end;
(*--------------------------
   Dat Hau i vao dong j
 --------------------------*)
procedure DatHau(i,j: integer);
begin
 c1[i-j]  :=  1; c2[i+j]  :=  1;
 dd[j]  :=  1;
end;
(*---------------------------------------
  Xuat phat tu dong v[i]+1,
  tim dong j co the dat duoc Hau i
--------------------------------------*)
function Tim(i: integer): integer;
 var j: integer;
begin
  Tim  :=  0;
  for j  :=  v[i] + 1 to n do
    if ( c1[i-j] + c2[i+j] + dd[j] = 0 ) then
     begin
       Tim  :=  j;
       exit;
     end;
end;
(*---------------------------------------
    Hien thi nghiem tren man hinh
    Cho bai toan tim 1 nghiem
    k = 0: vo nghiem
    k = n: co nghiem v[1..n]
--------------------------------------*)
procedure Ket1(k: integer);
  var i: integer;
begin
  writeln;
  if k = 0 then write('Vo nghiem')
   else for i :=  1 to k do write(v[i]:3);
  writeln;
end;
(*--------------------------------------
     Tim 1 nghiem: xep M quan hau tren
              ban co M X M
--------------------------------------*)
procedure XepHau1(M: integer);
  var i,j: integer;
begin

  if (M < 1) or (M > MN) then exit;
  fillchar(c1,sizeof(c1),0);
  fillchar(c2,sizeof(c2),0);
  fillchar(dd,sizeof(dd),0);
  fillchar(v,sizeof(v),0);
  n  :=  M; i  :=  1; { Dang xet Hau i }
  repeat
   if i > n then
     begin
         Ket1(n); { co nghiem v[1..n] }
         exit;
     end;
   if i < 1 then
     begin
        Ket1(0); {vo nghiem}
        exit;
     end;
   NhacHau(i); j  :=  Tim(i);
   if j > 0 then
        begin  { Tien: Dat Hau i tai dong j  }
          DatHau(i,j);
          v[i]  :=  j; inc(i); { Xet Hau i+1 }
        end
    else
        begin { Lui: Dat Hau i ra ngoai ban co }
          v[i]  :=  0; dec(i);  { Xet Hau i-1 }
        end;
  until false;
end;
(*---------------------------------------
  Ghi nghiem thu d vao tep g 'N_Hau.out'
  Bai toan tim moi nghiem
--------------------------------------*)
procedure Ket(d: integer);
  var i: integer;
begin
  write(g,'Nghiem thu ',d,': ');
  for i :=  1 to n do write(g,v[i],BL);
  writeln(g);
end;
(*---------------------------------------
   Tim moi cach dat M Hau
     tren ban co M X M
--------------------------------------*)
procedure XepHau(M: integer);
  var  i,j: integer;
      d: integer; { dem so nghiem }
begin
  if (M < 1) or (M > MN) then exit;
  n  :=  m;
  fillchar(v,sizeof(v),0);
  fillchar(c1,sizeof(c1),0);
  fillchar(c2,sizeof(c2),0);
  fillchar(dd,sizeof(dd),0);
  assign(g,gn); rewrite(g);
  i  :=  1; {Hau dang xet}
  d  :=  0; {dem so nghiem}
  repeat
   if i > n then
           begin
             inc(d);
             Ket(d); { v[1..n] la nghiem thu d }
             i :=  n;
           end;
if i < 1 then
           begin
             writeln(g,'Tong cong ',d,' nghiem ');
             close(g);
             writeln('Xem ket qua trong file ',gn);
             exit;
           end;
          NhacHau(i); j  :=  Tim(i);
         if j > 0 then
          begin  { Tien }
            DatHau(i,j); v[i]  :=  j; inc(i);
          end
         else
          begin { Lui }
            v[i] :=  0; dec(i);
          end;
   until false;
end;
procedure Test;
begin
  XepHau1(8); { tim 1 nghiem }
  XepHau(8);  { tim du 92 nghiem }
  readln;
end;
BEGIN
  Test;
END.

0 comments:

Post a Comment

Popular Posts