Trang bìa
Trang bìa
Ảnh
CHUYÊN ĐỀ 3: THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT DUYỆT
BÀI 5: THỰC HÀNH KĨ THUẬT QUAY LUI GIẢI BÀI TOÁN XẾP HẬU
Bài toán xếp hậu
Bài toán
Hình vẽ
Cần đặt n quân hậy lên bàn cờ vua kích thước n x n, sao cho không có hai quân hậu nào tấn công nhau
Ví dụ
Ảnh
Ví dụ 1: Trên bàn cờ 4 x 4 có tất cả hai cách đặt 4 quân hậu thỏa mãn các ô được tô màu là vị trí đặt quân hậu
Ví dụ 2: Có tất cả 92 cách đặt 8 quân hậu lên bàn cờ vua kích thước 8 x 8. Hình 2 là một cách đặt thỏa mãn
Gợi ý
Bước 1: Thiết kế thuật toán theo kĩ thuật quay lui
Ảnh
Nêu ý tưởng
Ảnh
Các em nhìn hình và nêu ý tưởng cách làm của bước 1
Gợi ý
Bước 2: Xây dựng chương trình giải bài toán bằng kĩ thuật quay lui
Ảnh
Bài toán xếp hậu mở rộng
Bài toán
Hình vẽ
Trên bàn cơ vua kích thước n x n có một ô (u,v) bị cấm, cần đặt n quân hậu lên bàn cơ sao cho không có hai quân nào tấn công nhau và không có quân nào đặt vào ô (u,v) bị cấm
Kết thúc
Tam biệt
Ảnh