Thuật toán quay lui – Back tracking – bài toán 8 quân hậu

Cho bàn cờ vua kích thước nxn (n cột và n hàng). Tìm cách đặt n quân hậu (của bàn cờ vua) lên bàn cờ sao cho không quân nào ăn được quân nào. Biết rằng quân hậu có thể ăn được các quân nằm cùng hàng, cột hoặc cùng đường chéo thuận và nghịch với nó.
Có thể tóm tắt phương pháp giả bài toán này như sau:
– Đầu tiên đặt quân hậu thứ 1 vào dòng thứ nhất của bàn cờ tại cột 1
– Sau đó, tiếp tục đặt quân hậu thứ 2 vào dòng thứ 2 của bàn cờ sao cho con hậu thứ 2 không bị con hậu trước ăn mất.
– Cứ tiếp tục quá trình cho đến khi:
*** Trường hợp 1: đạt đến dòng n và đặt thành công con hậu thứ n. => in ra kết quả
*** Trường hợp 2: đạt đến dòng thứ k nhưng không còn chỗ đặt con hậu thứ k:
+ quay lại dòng thứ k-1, tìm bên phải con hậu thứ k-1 một ô hợp lệ gần nhất, đặt con hậu k-1 vào đó
+ sau đó tiếp tục tìm kiếm ô hợp lệ để đặt cho con hậu thứ k ở dòng thứ k.
+ nếu không tìm thấy ô hợp lệ cho k-1, tiếp tục quay lui về con thứ k-2 và lặp lại tương tự.
Thuật toán trên gọi là thuật toán quay lui hay back tracking vì các bước giải thuật toán được lưu trữ lại để nếu cách hiện tại bế tắc thì có thể quay lại tại một bước nào đó để bắt đầu lại từ ngay đó mà không phải quay lại từ đầu.
Nhận xét:
– Mỗi hàng chỉ có thể có duy nhất 1 con hậu. Như vậy con hậu thứ i sẽ nằm ở hàng thứ i tương ứng. Như vậy, để lưu vị trí các quân hậu, ta chỉ cần 1 mảng 1 chiều gồm n phần tử. Mỗi phần tử tương ứng với giá trị cột của con hậu nằm ở hàng tương ứng.
Ví dụ: mảng m = [1, 4, 2, 3] gồm 4 quân hậu, quân hậu nằm ở hàng 1 nằm ở cột 1, quân hậu hàng 2 nằm ở cột 4, quân hậu hàng 3 nằm ở cột 2 và quân hậu hàng 4 nằm ở cột 3.
– Có 2 cách để lưu trạng thái bàn cờ. Ta có thể dùng một mảng 2 chiều nxn. Các ô có giá trị là 0 hoặc 1. Giá trị 0 nghĩa là chưa bị chiếm và 1 là đã bị chiếm. Hoặc một cách khác là dùng công thức để kiểm tra xem một ô ở tọa độ row, col có còn hợp lệ đối với k quân hậu đã đặt hay không.
Mình sẽ chọn cách 2 để tiết kiệm bộ nhớ một chút và tránh trường hợp phải cập nhật giá trị các ô mỗi khi thêm hoặc bớt các quân cờ.
– Để giải theo hướng back tracking, vị trí các quân hậu ở từng bước giải sẽ được lưu vào một stack.
Xin mời các bạn xem hình minh họa quá trình giải dùng stack cho trường hợp bàn cờ 6×6 và 6 quân hậu ở dưới đây:
Các bước cơ bản thuật toán

Toàn bộ mã nguồn:

 

No Comments

Post A Comment