Giáo án điện tử chuyên đề Khoa học máy tính 11 kết nối Bài 15: Bài toán xếp Hậu

CHÀO MỪNG CÁC EM ĐẾN VỚI BUỔI HỌC NGÀY HÔM NAY!

KHỞI ĐỘNG

Trên bàn cờ vua chúng ta đều biết Hậu là quân cờ mạnh nhất vì nó có thể di chuyển theo tất cả các hướng ngang, dọc và chéo. Một bài toán vui rất nổi tiếng là tìm cách sắp xếp 8 quân Hậu trên bàn cờ sao cho không quân Hậu nào khống chế con nào. Em hãy thử tìm một cách xếp quân Hậu khác với cách xếp như hình sau:

Bài toán tìm tất cả các cách xếp 8 quân Hậu trên bàn cờ vua sao cho các quân Hậu không khống chế lẫn nhau được gọi là bài toán xếp Hậu (n-Queen Problem). Bài toán này được nhà bác học Đức Carl Friedrich Gauss nghiên cứu từ những năm 1850. Bài toán đã được mở rộng trên bàn cờ kích thước bất kì và vẫn đang được tiếp tục phát triển cho đến ngày nay.

BÀI 15

BÀI TOÁN XẾP HẬU

NỘI DUNG BÀI HỌC

Mô tả bài toán xếp Hậu trên bàn cờ vua

01

Thiết lập lời giải bài toán xếp Hậu tổng quát

02

01

MÔ TẢ BÀI TOÁN XẾP HẬU

TRÊN BÀN CỜ VUA

Hoạt động 1

Tìm hiểu mô hình bài toán xếp Hậu trên bàn cờ vua tổng quát

Đọc, quan sát, trao đổi và thảo luận về bài toán xếp Hậu tổng quát và cách tiếp cận quay lui để giải bài toán.

Sử dụng một mảng để lưu vị trí của các quân hậu đã đặt.

Kiểm tra quân hậu mới được thêm vào có bị trùng với quân cũ không

Kiểm tra hàng, cột, đường chéo.

Quá trình chạy quay lui

Quân hậu mới đó không thể đặt được ở vị trí đó.

IF

Đặt lại quân hậu trước đó tại một vị trí khác

Thử lại cho đến khi tìm được vị trí thích hợp

Duyệt qua tất cả các trường hợp có thể có và đưa ra được kết quả đúng của bài toán

• Điều kiện xếp được quân Hậu tiếp theo tại cột k sau khi đã xếp xong tại các cột bên trái.
• Mệnh đề mô tả điều kiện của quân cờ tại cột k chính là điều kiện tính S_k của sơ đồ thuật toán quay lui tổng quát đã học trong bài 13.

Ý tưởng tiếp cận duyệt quay lui giải bài toán xếp Hậu tổng quát là tìm kiếm trên tất cả các dãy dạng A[0] , A[1], …, A[n-1], trong đó A[k] là chỉ số hàng của quân Hậu tại cột thứ k.

KẾT LUẬN

Đọc thông tin và trả lời các câu hỏi sau đây:

Câu 1: Giả sử n = 4, A[0] = 2, A[1] = 0. Hãy tìm A[2].

Hướng dẫn trả lời:

Với n = 4 A[0] = 2 A[1] = 0 thì A[2] = 3 (chỉ có 1 giá trị duy nhất).

Đọc thông tin và trả lời các câu hỏi sau đây:

Câu 2: Nếu n = 5, A[0] = 0, A[1] = 3. Tìm các khả năng của A[2].

Hướng dẫn trả lời:

Với n = 5 A[0] = 0 A[1] = 3 thì A[2] = 1 (chỉ có 1 giá trị duy nhất).

02

THIẾT LẬP LỜI GIẢI BÀI TOÁN XẾP HẬU TỔNG QUÁT

Hoạt động 2

Tìm hiểu thuật toán và cách giải bài toán xếp Hậu trên bàn cờ vua

Đọc, quan sát, trao đổi và thảo luận về thuật toán và thiết lập chương trình hoàn chỉnh giải bài toán.

• Số tự nhiên n được cố định trước, tập các nghiệm sẽ được tìm từ các dãy độ dài n như sau:
• Mảng A được thiết lập trước có n phần tử và bao gồm các số 0.

• Thuật toán chính là trynext(k) sẽ tìm ra vị trí đầu tiên để gán cho A[k] tại thời điểm coi như đã biết vị trí k – 1 quân Hậu trước đó tại A[0], A[1],..., A[k-1].
• Chương trình tổng quát:

Giải thích

• Dòng 3 sẽ thông báo nghiệm nếu k = n, tức là đã tìm được đủ n vị trí A[0], A[1], ..., A[n - 1].
• Hàm showQueen(A) sẽ thể hiện trên màn hình phương án sắp xếp các quân Hậu theo bộ dữ liệu của A.
• Các hàng sẽ đánh chỉ số từ trên xuống, các cột đánh chỉ số từ trái sang.

Giải thích

--------------- Còn tiếp ---------------