Em hãy đưa ra điều kiện để kiểm tra hai quân hậu đặt ở hai ô (u1,v1) và (u2,v2) tấn công

Hoạt động 2 trang 66 Chuyên đề Tin học 11: Em hãy đưa ra điều kiện để kiểm tra hai quân hậu đặt ở hai ô (u₁,v₁) và (u₂,v₂) tấn công nhau.

Trả lời

Dãy X = (x₀,x₁,...,x_n-1) là 1 hoán vị của dãy (0,1,...,n-1) biểu diễn một cách đặt thỏa mãn nếu với mọi i khác j thì 2 điều kiện sau thỏa mãn: i-x_i khác j -x_j và i+x_i khác j+x_j.

Với cách mô tả lời giải bài toán bằng 1 dãy X = (x₀,x_1,...,x_n-1) là hoán vị của dãy (0,1,...n-1), trong đó xi là chỉ số cột của quấn hậu trên hàng thứ i (0 ≤ i ≤ n-1), ta có thể giải quyết bài toán bằng cách sử dụng kĩ thuật quay lui để liệt kê tất cả các hoán vị của dãy (0,1,...,n-1). Với mỗi hoán vị đó, tiến hành kiểm tra để chọn nghiệm.