Số hàng khác số quân cần đặt
Với bàn cờ m hàng, n cột và m>n, yêu cầu đặt **n quân Hậu**, không phải m quân. Mỗi cột có một quân, A có n phần tử; A[k] chọn một hàng trong 0…m−1. Các hàng được chọn phải khác nhau và không có hai quân cùng đường chéo.
Điều kiện xung đột vẫn dùng độ chênh hàng và cột như bài bàn cờ vuông. Ba chỗ cần phân biệt:
| Phần chương trình | Kích thước dùng |
|---|---|
| Độ dài A, điểm dừng k==n | Số cột n |
| Miền thử hàng range(m) | Số hàng m |
| In bàn cờ | m dòng, mỗi dòng n ô |
Thử đủ các hàng của cột hiện tại
```python
def trynext(k):
global solutionCount
if k == n:
solutionCount += 1
if show_results:
print('Phương án', solutionCount, ':', A)
showQueen(A)
else:
for i in range(m):
if isOK(i, k):
A[k] = i
trynext(k + 1)
```
isOK kiểm với các quân trong tiền tố như bài trước; showQueen trong tệp tải in m hàng, n cột. solutionCount tăng tại lá và được đặt 0 trước mỗi lượt. Không đổi điểm dừng thành m, vì chỉ cần xếp n quân ở n cột.
Ví dụ4 hàng 2 cột
Chạy:
```text
python3 g11-cs-hau-chu-nhat.py 4 2
```
Cần nhận sáu dãy [0,2],[0,3],[1,3],[2,0],[3,0],[3,1]. Mỗi ma trận có 4 hàng 2 cột và đúng hai quân. Các cặp hàng không bằng nhau, không chênh 1 vì hai cột kề nhau.
Bản thực hành nhận 1<=n<m<=10 và n<=8; với m>7 hoặc n>5 dùng --chi-dem để giảm đầu ra. Đây là giới hạn tệp chạy thử, không thay điều kiện bài toán tổng quát.
Bài luyện
Bàn cờ 6 hàng 4 cột theo bài này cần đặt bao nhiêu quân?
Một quân cho mỗi cột.
m là số hàng để chọn vị trí.
Đây là số ô, không phải số quân.
Cần đủ n cột.
Lời giải
Yêu cầu đặt n quân, mỗi cột đúng một quân. Với n=4, A dài 4 và cần đặt 4 quân; sáu hàng chỉ mở rộng miền chọn hàng.
Bài luyện
Miền thử hàng và điểm dừng đúng là gì?
Bỏ các hàng có chỉ số từ n đến m−1.
Hàng có m lựa chọn, cột cần hoàn thành là n.
Đã đảo số hàng và số cột.
Sẽ cố đặt quá số phần tử của A.
Lời giải
Mỗi cột được phép chọn một trong m hàng. Sau n lần chọn, các cột 0…n−1 đã đủ, nên điều kiện kết thúc vẫn là k==n.
Bài luyện
Với 4 hàng 2 cột, dãy nào bị loại?
Chênh hàng 3 khác chênh cột 1.
Chênh hàng 2 khác chênh cột 1.
Chênh hàng 1 bằng chênh cột 1 nên cùng đường chéo.
Chênh hàng 2 khác chênh cột 1.
Lời giải
Hai cột có chỉ số 0 và 1, cách nhau 1. Dãy [1,2] cũng có độ chênh hàng 1 nên hai quân cùng đường chéo. Các dãy còn lại khác hàng và chênh hàng lớn hơn 1.
Đang học