Bài toán tám quân hậu kinh điển trên bàn cờ từ 4×4 đến 10×10. Mỗi hàng, cột và đường chéo chỉ một quân hậu, tìm đủ các lời giải.
Bài toán tám quân hậu là gì?
Bài toán tám quân hậu yêu cầu đặt tám quân hậu lên bàn cờ vua 8 x 8 sao cho không quân nào ăn được quân nào, tức là không có hai quân hậu nào chung một hàng ngang, một hàng dọc hay một đường chéo. Bài toán này áp dụng được cho mọi bàn cờ vuông: bàn N x N thì đặt N quân hậu.
Đây là bài toán kinh điển của cả cờ vua lẫn toán học. Bàn 8 x 8 có 92 cách giải, và chỉ tìm ra một cách bằng tay thôi cũng cần có phương pháp. Bản của chúng tôi cho chơi trên bàn từ 4 x 4 tới 10 x 10 và đếm từng lời giải khác nhau mà bạn tìm được.
Cách chơi bài toán 8 quân hậu
Chọn bàn: chọn cỡ bàn từ 4 x 4 tới 10 x 10. Số quân hậu cần đặt bằng cỡ bàn, nên bàn 4 x 4 cần 4 quân, bàn 10 x 10 cần 10 quân. Bàn cờ không nhận thêm quân nào vượt quá con số đó.
Đặt và nhấc quân: chạm ô trống để đặt quân hậu, chạm quân hậu để nhấc ra. Quân hậu ăn mọi ô trên hàng ngang, hàng dọc và hai đường chéo của nó, tới tận mép bàn.
Xung đột: quân hậu nào đang bị quân khác tấn công sẽ chuyển màu đỏ, nhìn là biết quân nào đang xung đột. Bật Đường tấn công để tô mọi ô mà các quân hậu trên bàn đang khống chế; những ô không bị tô là chỗ an toàn duy nhất.
Giải xong: bài toán được giải khi đủ N quân hậu trên bàn và không quân nào màu đỏ. Game sẽ cho biết đây là lời giải mới hay bạn đã tìm ra trước đó, và bạn đã tìm được bao nhiêu lời giải trong tổng số của cỡ bàn này. Nút Xóa dọn trống bàn và đặt lại đồng hồ.
Mẹo giải bài toán tám quân hậu
Mỗi hàng một quân, mỗi cột một quân. Với N quân trên bàn N x N và không hai quân nào chung hàng hay cột, mỗi hàng và mỗi cột có đúng một quân hậu. Vậy hãy đi theo từng hàng: ở mỗi hàng bạn chỉ phải chọn cột. Sau đó chỉ còn phải kiểm tra đường chéo.
Quay lui. Đặt một quân vào ô an toàn đầu tiên của hàng trên cùng, rồi ô an toàn đầu tiên của hàng tiếp theo, cứ thế tiếp. Khi một hàng không còn ô an toàn nào, quay lại hàng trước và dời quân ở đó sang ô an toàn kế tiếp. Cách này chậm nhưng luôn tới được lời giải, và khi bật Đường tấn công, bạn thấy ngay ô nào an toàn.
Xếp bậc thang. Một mẫu đơn giản giải được nhiều cỡ bàn: đi từng hàng, đặt mỗi quân lệch hai cột sang phải so với quân ở hàng trên, hết cột thì quay về phía trái. Ghi cột của mỗi quân theo từng hàng: bàn 5 x 5 là 1, 3, 5, 2, 4. Bàn 7 x 7 là 1, 3, 5, 7, 2, 4, 6. Bàn 6 x 6 và 10 x 10 thì bắt đầu từ cột 2: 2, 4, 6, 1, 3, 5 và 2, 4, 6, 8, 10, 1, 3, 5, 7, 9.
Sửa cho các cỡ khó. Mẫu đơn giản đó không dùng được cho bàn 8 x 8 và 9 x 9, nhưng chỉnh một chút là được. Bàn 8 x 8: 2, 4, 6, 8, 3, 1, 7, 5. Bàn 9 x 9: 4, 6, 8, 2, 5, 7, 9, 1, 3. Bàn 4 x 4 có một trong hai lời giải là 2, 4, 1, 3.
Xoay và lật. Mỗi lời giải cho bạn thêm những lời giải khác: xoay bàn một phần tư vòng, nửa vòng hay ba phần tư vòng, hoặc lật gương, bạn được một cách xếp hợp lệ khác. Game tính chúng là những lời giải khác nhau, nên một đáp án có thể dẫn tới tối đa tám đáp án. Trên bàn 8 x 8, 92 lời giải đến từ 12 dạng cơ bản: mười một dạng cho tám lời giải mỗi dạng, một dạng đối xứng chỉ cho bốn.
Sưu tầm đủ bộ. Muốn tìm hết lời giải của một bàn, quay về cách quay lui và tiếp tục sau mỗi lần giải được, mỗi lần lại dời quân cuối cùng sang ô an toàn kế tiếp.
Các cỡ bàn và số lời giải
Bài toán tám quân hậu của chúng tôi có bảy cỡ bàn. Số lời giải khác nhau của từng cỡ là: 4 x 4 có 2; 5 x 5 có 10; 6 x 6 có 4; 7 x 7 có 40; 8 x 8 có 92; 9 x 9 có 352; 10 x 10 có 724. Bàn 6 x 6 là trường hợp lạ, ít lời giải hơn cả bàn 5 x 5, nên là một thử thách nhỏ thú vị. Bàn 2 x 2 và 3 x 3 không có lời giải nào, vì vậy game bắt đầu từ cỡ 4.
Còn có những dạng khác của bài toán, ví dụ dùng quân cờ khác như đặt nhiều quân mã hoặc quân xe nhất mà không quân nào ăn nhau, hoặc tìm số quân hậu ít nhất để khống chế mọi ô trên bàn.
Lịch sử bài toán tám quân hậu
Bài toán được nhà soạn thế cờ Max Bezzel công bố năm 1848. Năm 1850, Franz Nauck công bố các lời giải và mở rộng câu hỏi cho bàn cờ cỡ bất kỳ, chính là bài toán N quân hậu bạn chơi ở đây. Nhiều nhà toán học, trong đó có Carl Friedrich Gauss, đã quan tâm tới nó.
Trong tin học, đây là ví dụ chuẩn cho thuật toán quay lui. Edsger Dijkstra dùng nó năm 1972 để minh hoạ cách xây dựng một thuật toán tìm kiếm như vậy từng bước, và tới nay bài toán 8 quân hậu vẫn là bài tập quen thuộc trong các khoá học lập trình ở Việt Nam và nhiều nơi khác.
Chơi bài toán tám quân hậu trên Hevagames
Bài toán tám quân hậu của Hevagames chạy ngay trên trình duyệt, chơi được trên điện thoại, máy tính bảng và máy tính, không cần tải về. Chạm vào ô để đặt hoặc nhấc quân hậu. Trên bàn phím, phím mũi tên chuyển giữa các ô, Enter hoặc Space để đặt hoặc nhấc quân ở ô đang chọn.
Không có giới hạn thời gian. Đồng hồ chạy từ quân hậu đầu tiên để bạn thử phá kỷ lục của mình ở từng cỡ bàn. Giải xong, bạn có thể giữ bàn cờ lại để xem, hoặc bắt đầu ván mới. Bàn cờ đang xếp, thời gian tốt nhất và danh sách lời giải bạn đã tìm trên từng cỡ bàn được lưu trong trình duyệt.
Cách chơi
- 1Chọn cỡ bàn từ 4×4 đến 10×10. Bàn N×N thì đặt N quân hậu.
- 2Chạm ô trống để đặt quân hậu, chạm quân hậu để nhấc ra.
- 3Quân hậu đang bị quân khác tấn công sẽ chuyển màu đỏ. Hậu ăn theo hàng ngang, hàng dọc và hai đường chéo.
- 4Giải xong khi đủ N quân hậu trên bàn và không quân nào màu đỏ.
Điều khiển
Mẹo
- Đi lần lượt từng hàng: mỗi hàng và mỗi cột phải có đúng một quân hậu.
- Bật đường tấn công để thấy ô nào còn trống an toàn.
- Bàn 6×6 chỉ có 4 lời giải, 8×8 có 92, 10×10 có 724. Game đếm số lời giải khác nhau bạn đã tìm.