Từ bàn cờ sang dãy số
![Hai bàn cờ 4×4 ứng với các dãy [1,3,0,2] và [2,0,3,1]; hàng tăng từ trên xuống, cột từ trái sang.](/static/runtime/learning/informatics/g11-cs-hau-bon.e86ecfe7f2f8.svg)
Trên bàn cờ vuông n×n, cần đặt n quân Hậu sao cho không hai quân nào cùng hàng, cùng cột hoặc cùng đường chéo. Vì có n quân và n cột, mỗi cột phải có đúng một quân.
Mô hình dùng chỉ số 0…n−1: hàng tăng từ trên xuống, cột tăng từ trái sang. A[k] là **hàng** của quân Hậu ở **cột k**. Vì mỗi cột đã có một vị trí trong dãy, không cần thêm phép kiểm trùng cột.
Đọc một phương án
Với A=[1,3,0,2], vị trí các quân là:
| Cột k | Hàng A[k] |
|---|---|
| 0 | 1 |
| 1 | 3 |
| 2 | 0 |
| 3 | 2 |
Dãy có bốn phần tử nên đặt đủ bốn quân. Các hàng khác nhau mới chỉ bảo đảm không cùng hàng; vẫn phải kiểm đường chéo. Chẳng hạn [0,1,2,3] có các hàng khác nhau nhưng cả bốn quân nằm trên một đường chéo.
Bài luyện
Trong A=[1,3,0,2], quân ở cột 2 nằm tại hàng nào?
2 là chỉ số cột đang hỏi.
3 là A[1].
1 là A[0].
Đọc A[2]=0 theo chỉ số bắt đầu từ 0.
Lời giải
A[k] là hàng của quân tại cột k. Với k=2, phần tử thứ ba của dãy là 0, nên quân ở cột 2 nằm tại hàng 0.
Bài luyện
Vì sao mô hình dãy này không cần kiểm hai quân trùng cột?
Trùng cột đã được loại nhờ cách biểu diễn.
Quân Hậu có thể đi dọc.
Cần các hàng khác nhau, không giống nhau.
Đường chéo vẫn cần kiểm thêm.
Lời giải
Dãy có đúng một phần tử cho từng cột. Gán A[k] chỉ xác định hàng của quân duy nhất ở cột đó; các quân tại chỉ số khác nằm ở cột khác.
Bài luyện
Dãy [0,1,2,3] trên bàn cờ 4×4 có hợp lệ không?
Mô hình dùng chỉ số 0…3.
Khoảng cách hàng bằng khoảng cách cột.
Đây chỉ là một phần điều kiện.
Đủ quân chưa bảo đảm không khống chế nhau.
Lời giải
Các vị trí là (cột 0,hàng 0),(cột 1,hàng 1),(cột 2,hàng 2),(cột 3,hàng 3). Mỗi bước tăng cột 1 cũng tăng hàng 1, nên các quân cùng đường chéo và phương án không hợp lệ.
Đang học