tailieunhanh - Algorithms Programming - Thuật Toán Số phần 2

Phân tích Rõ ràng 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. | Bài toán liệt kê 19 Hình 2 xếp 8 quân hậu trên bàn cờ 8x8 . Phân tích Rõ ràng 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. Nếu ta định hướng Đông Phải Tây Trái Nam Dưới Bắc Trên thì ta nhận thấy rằng Một đường chéo theo hướng Đông Bắc - Tây Nam ĐB-TN bất kỳ sẽ đi qua một số ô các ô đó có tính chất Hàng Cột C Const . 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 Một đường chéo theo hướng Đông Nam - Tây Bắc ĐN-TB bất kỳ sẽ đi qua một số ô các ô đó có tính chất Hàng - Cột C Const . 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. 1 2 3 4 5 6 7 8 1 2 3 4 E 5 6 7 8 Hình 3 Đường chéo ĐB-TN mang chỉ số 10 và đường chéo ĐN-TB mang chỉ số 0 Cài đặt Lê Minh Hoàng 20 Chuyên đề Ta có 3 mảng logic để đánh dấu Mảng a . ai TRUE nếu như cột i còn tự do ai FALSE nếu như cột i đã bị một quân hậu khống chế Mảng b . bi TRUE nếu như đường chéo ĐB-TN thứ i còn tự do bi FALSE nếu như đường chéo đó đã bị một quân hậu khống chế. Mảng c 1 - - 1 . ci TRUE nếu như đường chéo ĐN-TB thứ i còn tự do ci FALSE nếu như đường chéo đó đã bị một quân hậu khống chế. Ban đầu cả 3 mảng đánh dấu đều mang giá trị TRUE. Các cột và đường chéo đều tự do Thuật toán quay lui 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 đến 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