Giải SGK Chuyên đề Tin học 11 Bài 15. Bài toán xếp Hậu

Em có thể xếp như sau

Trong quá trình quay lui, ta sử dụng một mảng để lưu vị trí của các quân hậu đã đặt. Mỗi lần thêm một quân hậu mới, ta kiểm tra xem nó có đặt được ở vị trí đó không bằng cách kiểm tra xem quân hậu mới đó có trùng hàng, cột hay đường chéo với bất kỳ quân hậu nào đã đặt trước đó không.

Nếu quân hậu mới đó không thể đặt được ở vị trí đó, ta quay lại đặt lại quân hậu trước đó tại một vị trí khác và tiếp tục thử các vị trí khác cho đến khi tìm được vị trí thích hợp.

Với phương pháp này, ta sẽ 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.

A[k] cần thỏa mãn điều kiện sau:

$\begin{matrix}A[k]\ne A[j]\ voi\ \forall j<k \\ |A[k]-A[j]|\ \ne \ |k-j|voi\ \forall j<k\end{matrix}$

Do đó A[2] ≠ 0, 2 và | A[2]-2 | ≠2 và | A[2]-0 | ≠1 nên A[2] = 3

Do đó A[3] = 1

A[k] cần thỏa mãn điều kiện sau:

$\begin{matrix}A[k]\ne A[j]\ voi\ \forall j<k \\ |A[k]-A[j]|\ \ne \ |k-j|voi\ \forall j<k\end{matrix}$

Do đó A[2] ≠ 0, 3 và | A[2]-2 | ≠2 và | A[2]-3 | ≠1 nên A[2] = 1

* Thuật toán: Sử dụng kĩ thuật duyệt quay lui và in ra tất cả phương án nghiệm

* Thiết lập chương trình hoàn chỉnh giải bài toán.

Với n = 3, bài toán có nghiệm:

Hai phương án như sau:

Nếu chúng ta mô phỏng lưới ô vuông đánh chỉ số các hàng từ dưới lên thì chương trình trên không còn đúng.

Nếu phải thay đổi thì cần sửa ở chỗ dòng số 5, 13, 15

Sửa i thành n - 1 - i

Chương trình viết như sau

Thu được kết quả là:

Tương tự, thay đổi giá trị của n ta thu được kết quả sau: