Các quân Hậu

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 i khi 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ảng v[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 i nà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.