(45) Back-tracking algorithm: Xếp n quân hậu trên bàn cờ – Bùi Thế Tâm



Các tập hợp hữu hạn (Finite Set): Xếp n quân hậu trên bàn cờ . Bùi Thế Tâm – Hanoi, Vietnam
Bài toán đặt ra là liệt kê tất cả các cách xếp n quân hậu trên bàn cờ có n hàng n cột sao cho chúng không ăn được nhau.
Đánh số dòng và cột của bàn cờ từ 0 đến n-1, mỗi hàng chỉ xếp được đúng một quân hậu, nên chúng ta chỉ cần quan tâm đến quân hậu được xếp ở cột nào. Một sắp xếp được biểu diễn bằng bộ ( x(0), x(1), … , x(n-1) ), trong đó x(i) = j có nghĩa là quân hậu dòng i xếp vào cột j. Thành phần x(i) có thể nhận giá trị từ 0 đến n-1, giá trị j là chấp nhận được nếu ô (i, j) chưa bị các quân hậu trước chiếu đến. Ta cần ghi nhận trạng thái của bàn cờ trước cũng như sau khi xếp 1 quân hậu.
Việc kiểm soát theo chiều ngang là không cần thiết vì mỗi dòng chỉ xếp 1 quân hậu. Việc kiểm soát theo chiều dọc được ghi nhận nhờ mang a: quy ước a(j) = 1 nếu cột j còn trống.
Đối với 2 đường chéo ta có nhận xét rằng: đường chéo nghiêng sang phải có phương trình là i + j = const ( i+j nhận giá trị từ 0 đến 2n-2), đường chéo nghiêng sang trái có phương trình là i – j = const ( i – j nhận giá trị từ 1 – n đến n – 1). Do đó đường chéo thứ nhất được ghi nhận từ biến mảng b(j) với j nhận giá trị từ 0 đến 2n-2, đường chép thứ hai nhờ biến mảng c(j) với j nhận giá trị từ 1 – n đến n – 1 với quy ước các đường này còn trống nếu biến tương ứng có giá trị bằng 1.
Lúc đầu các biến trạng thái a(j), b(j), c(j) đều nhận giá trị = 1. Như vậy giá trị j được chấp nhận nếu cả 3 biến a(j), b(i+j),
c(i-j) cùng có giá trị = 1. các biến này cần gán lại = 0 khi xếp xong quân hậu thứ i và trả lại = 1 sau khi gọi Print() hay XepHau().
Mảng x và mảng a có n phần tử, mảng b và mảng c có 2n-1 phần tử. Đối với đường chéo thứ hai nếu ta lấy i – j + (n -1) thì nó sẽ nhận giá trị từ 0 đến 2n – 2.
HỌC TIN HỌC ONLINE MIỄN PHÍ
Bùi Thế Tâm là kênh đào tạo về lĩnh vực Công nghệ thông tin, Lập trình ngôn ngữ C, Tin học văn phòng, Các thuật toán toán tối ưu, Hướng dẫn sử dụng Microsoft office 2007, 2010, 2013, Hướng dẫn dùng Google Drive.
Kênh Bùi Thế Tâm hướng dẫn sử dụng word, excel, powerpoint, lập trình ngôn ngữ C cho người mới bắt đầu, sinh viên, sinh viên năm thứ nhất, sinh viên năm thứ hai, cho học sinh, giáo viên vùng sâu vùng xa, người cao tuổi muốn học tin học ở nhà, các bạn thi viên chức và người đi làm.
Với nhiều năm kinh nghiệm giảng dậy và viết sách nên các bài giảng ở đây rất dễ hiểu, đơn giản, chuẩn xác và đầy đủ. Trong bài giảng phần lý thuyết, bài tập xen kẽ nhau, với nhiều dạng bài tập từ dễ đến khó có hướng dẫn giải chi tiết cẩn thận giúp các bạn có thể nắm vững được kiến thức. Các thuật toán đều cho listing chương trình. Các chương trình đều có giải thích từng lệnh cụ thể trong bài giảng.
Bùi Thế Tâm là tác giả một số sách phổ biến về Tin học: “1. Ngôn ngữ C và lập trình hướng đối tượng – 2. Turbo Pascal 7.0 – 3. Giáo trình Tin học văn phòng – 4. Giáo trình Tin học đại cương – 5. Giáo trình Microsoft Access – 6. Cẩm nang lập trình FoxPro – 7. Cẩm nang sử dụng máy vi tính – 8. Các phương pháp tối ưu hóa.”
Kênh Yotube chính thức của Bùi Thế Tâm, Subscribe Youtube:
Facebook:
Twitter:
Blog:
Hãy like và chia sẻ cho bạn bè và những người bạn quen đang muốn học về Microsoft Office, Tin học văn phòng (hay còn gọi là tin học cơ sở, tin học đại cương, tin học căn bản, tin học phổ thông, tin học cho người mới bắt đầu), Ngôn ngữ lập trình C, Cấu trúc dữ liệu, Thuật toán, Tin học văn phòng online.
Mọi hình thức copy và sao chép đều vi phạm bản quyền của youtube nếu không được sự đồng ý của tác giả Bùi Thế Tâm
Đừng quên đăng ký kênh để học thêm các bài mới

Nguồn: https://themusicobserver.com/

Xem thêm bài viết khác: https://themusicobserver.com/giai-tri/

  • Phải coi 1 lần xong code lại để đọc code trước, rồi coi lại lần nữa mới hiểu được, cảm ơn thầy ạ. <3

    Cường Nguyễn Hồng July 15, 2020 8:33 am Reply
  • Thưa Thầy vì sao hàm Print ban đầu trong hàm Xephau Thầy viết Print(x) sau đó có thể viết gọn lại là Print()? Em thắc mắc vậy hàm Print tự động biết in ra mảng x ah ?

    manhtienfc July 15, 2020 8:33 am Reply
  • Thầy cho em hỏi chỗ XepHau(0), ở 1 số bài track back khác em thấy tham số int i truyền vào là 1 nhưng ở đây i lại là 0, thầy và các bạn có thể giải thích cho em được ko ạ? Em xin cảm ơn!

    trinh cuong July 15, 2020 8:33 am Reply
  • Tại sao đường chéo thứ hai lại chạy từ i-j+n-1= 0 đến 2n-2 ạ ???

    Uyen Pham July 15, 2020 8:33 am Reply
  • cảm ơn thầy. em mò mãi ms ra

    thinh Ngoc July 15, 2020 8:33 am Reply
  • đúng cái em cần cảm ơn thầy

    vu nguyen July 15, 2020 8:33 am Reply

Leave a Reply

Your email address will not be published. Required fields are marked *