Home » Quay lui » Bài toán xếp hậu (Backtracking)

Bài toán xếp hậu (Backtracking)

Bài toán xếp hậu:

Xét bàn cờ tổng quát kích thước nxn. Một quân hậu trên bàn cờ có thể ăn được các quân khác nằm tại các ô cùng hàng, cùng cột, hoặc cùng đường chéo. Hãy tìm cách xếp n quân hậu trên bàn cờ sao cho không quân nào ăn quân nào.

Ví dụ cách xếp 8 quân hậu trên bàn cờ 8×8

Untitled

Phân tích Bài toán xếp hậu:

N quân hậu sẽ được đặt mỗi con một hàng vì hậu ăn được ngang, ta gọi quân hậu sẽ đặt ở hàng 1 là quân hâu 1, quân hậu ở hàng 2 là quân hậu 2…quân hậu ở hàng n là quân hậu n. Vậy một nghiệm của bài toán sẽ được biết khi ta tìm ra được vị trí cột của những quân hậu.

  • 1 đường chéo theo hướng ĐB-TN bất kì sẽ đi qua một số ô, các ô đó có tính chất: Hàng +Cột=C (Hằng số). Với mỗi đường chéo ĐB-TN ta có 1 hằng số C và với một hằng số C: 2<= C <=2n xác định duy nhất 1 đường chéo ĐB-TN  vì vậy ta có thể đánh chỉ số cho các đường chéo ĐB-TN từ 2 đến 2n.
  • 1 đường chéo theo hướng ĐN-TB bất kì sẽ đi qua một số ô, các ô đó có tính chất: Hàng -Cột=C (Hằng số). Với mỗi đường chéo ĐN-TB ta có 1 hằng số C và với một hằng số C: 1-n<= C <= n-1 xác định duy nhất 1 đường chéo ĐN-TB  vì vậy ta có thể đánh chỉ số cho các đường chéo ĐN-TB từ 1-n đến n-1

Cài đặt:

 

Ta có 3 mảng logic để đánh dấu:

 

  • Mảng a[1..n] a[i] = 1 nếu như cột i còn tự do, a[i]=0 nếu như cột i đã đi bị một quân hậu khống chế.
  • Mảng b[2..2n] b[i]=1 nếu như đường chéo ĐB-TN thứ i còn tự do, b[i]=0 nếu như đường chéo đó đã bị 1 quân hậu khống chế.
  • Mảng c[1-n…n-1] tương tự như trên đối với đường chéo ĐN-TB.

Ban đầu cả 3 mảng đánh dấu đều mang giá trị 1 (Các cột và đường chéo đều tự do)

 

Thuật toán quay lui Bài toán xếp hậu:

 

  • Xét tất cả các cột, thử đặt quân hậu 1 vào một cột, với mỗi cách đặt như vậy, xét tất cả các cách đặt quân hậu 2 không bị quân hậu 1 ăn, lại thử 1 cách đặt và xét tiếp các cách đặt quân hậu 3…Mỗi cách đặt được quân hậu n cho ta 1 nghiệm.
  • Khi chọn vị trí cột j cho quân hậu thứ I, thì ta phải chọn ô(i,j) không bị các quân hậu đặt trước đó ăn, tức là phải chọn cột j còn tự do, đường chéo ĐB-TN(i+j) còn tự do, đường chéo ĐN-TB(i-j) còn tự do.
  • Nếu (i=n) thì được 1 nghiệm, ngược lại thì gọi đệ quy với quân hậu tiếp i+1

Xem lại trong các bài Chương trình liệt kê chỉnh hợp không lặp và hoán vị về kĩ thuật đánh dấu. Ở đây chỉ khác liệt kê hoán vị là: Liệt kê hoán vị chỉ cần một mảng đánh dấu, thì ở đây phải sử dụng 3 mảng đánh dấu: cột, đường chéo ĐB-TN, đường chéo ĐN-TB.

 

 

Share
  • GTO

    I like it ! Thank you .

  • Thảo Nguyễn Minh Phương

    anh cho em hoi? bai nay` viet = ngon ngu~ c++ dung ko anh?

    • Tung Nguyen

      Đúng rồi bạn

Share
Free WordPress Themes - Download High-quality Templates