Về bài toán tám quân hậu | Quay lui và bài toán n quân hậu

Một câu đố cờ vua từ năm 1848

Max Bezzel, một nhà sáng tác bài toán cờ người Đức, đã nêu câu đố này trên một tạp chí cờ vua ở Berlin vào năm 1848. Franz Nauck công bố đủ 92 lời giải vào năm 1850 và đặt cùng câu hỏi đó cho những bàn cờ lớn hơn. Carl Friedrich Gauss theo dõi câu đố với sự quan tâm và bàn về nó trong các bức thư của mình.

Mỗi hàng và mỗi cột một quân hậu

Tám quân hậu không tấn công nhau phải đứng ở tám hàng khác nhau và tám cột khác nhau. Vì vậy, một lời giải là một cách xáo trộn các số từ 1 đến 8, tức là một hoán vị, kèm thêm một luật: không có hai quân hậu nào được nằm trên cùng một đường chéo. Trong 40.320 hoán vị, chỉ có 92 hoán vị đạt yêu cầu.

Quay lui

Thuật toán quay lui xây dựng lời giải từng phần một và lùi lại ngay khi gặp ngõ cụt. Với các quân hậu: đặt một quân hậu vào ô an toàn đầu tiên của hàng tiếp theo, và khi một hàng không có ô an toàn nào, hãy quay về hàng trên và dời quân hậu ở đó đi tiếp. Năm 1972, Edsger Dijkstra đã dùng bài toán này để giải thích lập trình có cấu trúc bằng đúng phép tìm kiếm này.

Đối xứng

Xoay bàn cờ một phần tư vòng, hoặc lấy đối xứng nó, thì một lời giải vẫn là lời giải. Như vậy mỗi lời giải có tới tám phiên bản. 92 lời giải chia thành 12 họ như thế: mười một họ có 8 thành viên, và một họ chỉ có 4, vì lời giải đó trông vẫn y như cũ sau khi xoay nửa vòng.

Bài toán n quân hậu

Trên bàn cờ n×n, câu hỏi vẫn vậy với n quân hậu. Có lời giải cho mọi n từ 4 trở lên, và số lời giải tăng rất nhanh: 2 với 4×4, 92 với 8×8 và 14.200 với 12×12. Chưa ai biết công thức tính số này; các giá trị kỷ lục đến từ những đợt tìm kiếm lớn bằng máy tính.

Thử trong PictorX

Mở Tám quân hậu và bấm vào một ô để đặt quân hậu; bấm lại để bỏ nó đi. Khi bật Hiện ô bị tấn công, các ô mà quân hậu của bạn tấn công được đánh dấu chấm, và các quân hậu màu đỏ đang tấn công nhau. Giải chạy phép tìm kiếm quay lui từng bước một và giữ lại các quân hậu bạn đã đặt. Lời giải tiếp theo đi qua mọi lời giải theo thứ tự, và Kích thước đổi bàn cờ từ 4×4 đến 12×12.

Hỏi thường xuyên

Ai đã phát minh ra bài toán tám quân hậu?

Max Bezzel, một nhà sáng tác bài toán cờ người Đức, vào năm 1848. Franz Nauck công bố bộ lời giải đầy đủ đầu tiên vào năm 1850.

Có bao nhiêu lời giải?

92 trên bàn cờ tiêu chuẩn. Nếu tính các phép quay và phản chiếu là một, thì có 12.

Vì sao bàn cờ 6×6 có ít lời giải như vậy?

Nó chỉ có 4, tất cả đều thuộc một họ duy nhất. Bàn cờ 5×5 nhỏ hơn có 10. Các bàn cờ lớn hơn có ngày càng nhiều: 40 trên 7×7 và 92 trên 8×8.

PictorX có tải gì lên không?

Không. Bàn cờ được vẽ trên canvas trong trình duyệt. Lưu sẽ tải xuống một PNG, và Chỉnh sửa mở ảnh đó trong trình chỉnh sửa PictorX.

Công cụ liên quan

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt của bạn — không cài đặt, không cần thiết thẻ tín dụng để khởi động.

Thử Tám quân hậu