Bài toán 8 con Hậu ~ Dev trong sáng

Bài toán 8 con Hậu là bài toán nổi tiếng trong lĩnh vực toán học.

Trong lập trình bài toán này thường xuyên được nhắc đến khi có chủ đề liên quan đến đệ quy quay lui hoặc là trí tuệ nhân tạo.

1. Mô tả bài toán.

Trên bàn cờ có kích thước 8x8 ô, người chơi đặt các quân Hậu tại mỗi cột sao cho không có quân nào tấn công lẫn nhau, nghĩa là không có bất kỳ quân Hậu nào có chung hàng hoặc cùng chung một đường chéo với quân Hậu đã tồn tại trước đó.

Quân Hậu trên bàn cờ là quân có thể đi được 8 hướng xung quanh nó.

Như hình ví dụ trên không có bất kỳ quân Hậu nào nằm trên đường đỏ, đồng thời các con Hậu còn lại cũng chung quy luật này.

2. Thuật toán.

Trước hết, cần xác định điệu kiện như thế nào là có sự tấn công lẫn nhau giữa 2 quân Hậu trên ma trận 8x8, ma trận 8x8 là hình mẫu của bàn cờ.

Hai quân Hậu tấn công nhau khi
+ Chung hàng.
+ Chung đường chéo.
+ Tất nhiên là không chung cột vì mỗi cột chỉ được để một Hậu.

VD: Cho 2 quân Hậu tọa độ (x,y) , quân A đặt ở vị trí là (4,6), quân B đặt ở vị trí (6,4).

+ Xét điều kiện chung hàng
- Có y của A != y của B ( 6!=4).

+ Xét điều kiện chung đường chéo.
- Có | xA-xB| = |yA - yB| (vì |4-6| = |6-4|). Suy ra quân A và B đã tấn công lẫn nhau.

Dấu X tượng trương cho con Hậu A và B.

Tiếp theo, đệ quy quay lui diễn ra thế nào trong thuật toán.

VD: Ta lấy ô đầu tiên X ở vị trí (0,7) tại cột 0 hàng 7 thì có tới 7 con Hậu có thể đặt ở cột thứ 1 (các dấu X ở cột 1).

Nhưng (1,6) và (1,7) vi phạm
điều kiện vừa nêu bên trên nên chỉ còn 5 con Hậu là có thể đặt ở cột thứ 1.

Các con Hậu có tiềm năng còn lại là ở vị trí (1,0), (1,1), (1,2), (1,3), (1,4), (1,5).
Lấy thử con Hậu ở vị trí (1,1)

Vì đã chọn Hậu ở (1,1) và (0,7) [ các dấu X nghĩa là đã chọn, X nghĩa là tiềm năng để chọn]

nên các ô tiềm năng ở hàng 2 chỉ còn lại (2,3), (2,4) và (2,6).

Chọn Hậu ở (1,1) [ các dấu X nghĩa là các ô đã chọn]