Hai điều kiện với mọi cột trước
Đang thử hàng i tại cột j; các cột k<j đã đặt xong. Để không cùng hàng, cần i khác A[k]. Để không cùng đường chéo, cần:
$$|A[k]-i|\ne|j-k|.$$
Trên lưới vuông, đi chéo làm hàng và cột thay đổi cùng số ô, nên hai độ chênh tuyệt đối bằng nhau chính là trường hợp bị loại. Phải thỏa với **mọi quân đã đặt**, không chỉ quân ngay bên trái.
Chỉ đọc tiền tố đã đặt
```python
def check(A, i, j):
for k in range(j):
if A[k] == i:
return False
if abs(A[k] - i) == abs(j - k):
return False
return True
```
Hàm trả False ngay khi thấy một quân khống chế vị trí đang thử. Chỉ khi hết range(j) mà không xung đột mới trả True. Những phần tử từ A[j] trở đi chưa được dùng làm quân đã đặt, dù dãy tạo sẵn đang chứa 0 hoặc giá trị của nhánh trước.
Xét từng hàng trong một cột
Bàn cờ 5×5 đã có A[0]=1, A[1]=4. Thử đặt tại cột 2:
| Hàng thử i | Kết quả | Căn cứ |
|---|---|---|
| 0 | Được | Không trùng hàng; các độ chênh hàng khác độ chênh cột |
| 1 | Loại | Trùng hàng với cột 0 |
| 2 | Được | Không trùng hàng hoặc đường chéo |
| 3 | Loại | Với cột 1: chênh hàng 1, chênh cột 1 |
| 4 | Loại | Trùng hàng với cột 1 |
Vậy có thể thử A[2]=0 hoặc 2. Được đặt ở bước này chưa bảo đảm nhánh ấy sẽ xếp đủ cả năm quân; việc tìm tiếp vẫn phải diễn ra.
Bài luyện
Đã đặt quân tại cột 0,hàng 1. Thử cột 2,hàng 3 bị loại vì sao?
Hàng đang thử là 3.
Tính hợp lệ phụ thuộc các quân đã đặt.
Hai độ chênh tuyệt đối đều bằng2.
Vị trí đang thử thuộc cột 2.
Lời giải
Khoảng cách hàng là |3−1|=2, khoảng cách cột là |2−0|=2. Hai độ chênh bằng nhau nên cùng đường chéo, dù hàng và cột khác nhau.
Bài luyện
Với bàn cờ 5×5 và tiền tố [1,4], những hàng nào hợp lệ cho cột 2?
Cả hai đều là hàng đã có quân.
Hàng 3 chéo với quân tại cột 1,hàng 4.
Ba hàng còn lại có xung đột.
Đây là hai hàng không trùng hàng hoặc đường chéo với cả hai quân.
Lời giải
Hàng 1 và 4 trùng hàng đã đặt. Hàng 3 chéo với cột 1 vì chênh hàng và cột đều 1. Hàng 0 và 2 không xung đột với cột 0 hoặc 1, nên được thử tiếp.
Bài luyện
Vì sao check chỉ xét range(j)?
Phần còn lại chưa đại diện cho quân đã đặt.
Cần xét đủ các quân đã đặt.
Bài toán không có tường.
Hàm vẫn kiểm đường chéo với các cột trước.
Lời giải
Trước khi chọn A[j], tiền tố A[0]…A[j−1] là trạng thái hợp lệ đã thiết lập. Các giá trị phía sau có thể còn từ khởi tạo hoặc nhánh cũ, nên không được xem là quân cản vị trí mới.
Đang học