Giới thiệu bài toán: Quân hậu trên bàn cờ Vua có thể ăn theo hàng, cột, đường chéo chứa nó. Tìm cách đặt 8 quân hậu trên bàn cờ sao cho không quân nào ăn được của quân nào | Bài toán xếp 8 quân hậu Bài toán xếp 8 quân hậu thiệu bài toán: Quân hậu trên bàn cờ Vua có thể ăn theo hàng, cột, đường chéo chứa nó. Tìm cách đặt 8 quân hậu trên bàn cờ sao cho không quân nào ăn được của quân nào tưởng thuật toán: Một con hậu xếp ở một vị trí bất kỳ trên bàn cờ thì để tìm được vị trí của con hậu tiếp theo ta phải xét theo 3 hướng như hình sau: 1 Mô hình bài toán Các con hậu tiếp theo phải được chọn ở các vị trí không nằm trên các đường dọc, đường ngang và đường chéo của con các con hậu trước. 2 Các bước giải quyết bài toán • Ta tìm vị trí để đặt cho con hậu thứ i, với con hậu thứ i thì ta phải xét xem trên các hướng của nó sau đó tìm tiếp vị trí cho con hậu thứ i + 1. • Nếu ở bước thứ i không tìm thấy vị trí đặt của con hậu thì chúng ta phải quay lại xét đến vị trí khác của con hậu thứ i – 1. • Trường hợp suy biến của bài toán là khi chúng ta đã đặt cho con hậu thứ 8 có nghĩa là cả 8 con hậu đã được xếp trên bàn cờ và thoả mãn điều kiện là các con hậu không thể ăn được nhau. 3 Bài toán tìm đường đi bằng chu trình Hamilton Giới thiệu bài toán: Một người khách du lịch muốn đi thăm n thành phố được đánh số từ 1 đến n. Mạng lưới giao thông giữa n thành phố này là 2 chiều và được cho bởi ma trận A[i,j] trong đó A[i,j] = 1 nếu có đường đi giữa thành phố i và thành phố j, A[i,j] = 0 trong trường hợp ngược lại. Thiết lập đường đi cho người khách thông báo tồn tại đường đi hoặc không tồn tại đường đi. 4 Mô hình bài toán •Chúng ta có file có n + 1 dòng như sau: – Dòng 1: Ghi số nguyên dương là n thành phố – Dòng i + 1: (1≤i≤n): ghi n số nguyên không âm A[i,1] A[i,2] A[i,n] cho biết có đường đi hay không giữa hai thành phố i và j (1≤j≤n). •Kết quả tồn tại hay không tồn tại đường đi. 5 Kết quả: 0 0 1 1 1 0 0 1 1 1
