Tài liệu hướng dẫn thực hành
1
BÀI TOÁN MÃ ĐI TUẦN
Văn Chí Nam – Nguyễn Đức Hoàng Hạ
Lu Boun Vinh – Nguyễn Anh Tuấn
Khoa Công nghệ Thông tin, trường Đại học Khoa học Tự nhiên Tp.HCM
Phiên bản cập nhật ngày 18/05/2004
1. Mô tả
Cho trước một bàn cờ vua có n x n ô (xét n = 8) và một vị trí đặt con Mã
trên bàn cờ đó. Tìm cách cho con Mã nhảy qua tất cả các ô của bàn cờ (n x n ô),
mỗi ô chỉ nhảy qua duy nhất một lần và phải nhảy đúng theo luật của cờ Vua.
2. Nước đi của Mã
Theo luật cờ Vua, tại một vị trí bất kỳ con mã có thể đi tiếp tối đa 8 vị trí,
như hình vẽ dưới đây :
1 2
8 3
X
7 4
6 5
3. Heuristic để giải bài toán
Đây là một bài toán không có thuật toán (algorithm) nhưng có thể tìm được
lời giải thông qua phương pháp vét cạn. Dưới đây mô tả hai heuristic được dùng
để tìm cách đi của Mã
Tài liệu hướng dẫn thực hành
2
Cách 1 (Heuristic 1) :
Heuristic 1 được mô tả như dưới đây có thể nói đạt hiệu quả tốt trong việc
tìm đường đi cho con Mã. Trong quá trình cài đặt và chạy thử, Heuristic này đảm
bảo tìm thấy đường đi cho hầu hết các vị trí đặt Mã ban đầu trên bàn cờ 8x8.
Giả sử sau bước nhảy thứ k, Mã có n vị trí V1 ,V2 , ..., Vn có thể đi tới ở bước
k+1, làm sao để chọn một trong các vị trí trên để đặt Mã. Heuritic 1 miêu tả như
sau:
+ Tính f(Vi) = số vị trí con Mã có thể nhảy tới từ vị trí Vi.
+ So sánh cácgiá trị f(Vi) lấy giá trị nhỏ nhất. Tức là chọn M = Vk
miễn là Vk nhỏ nhất làm vị trí nhảy tiếp theo.
Cách 2 (Heuristic 2) :
So với Heuristic 1, heuristic này có vẻ đơn giản hơn nhưng thực tế hiệu quả
không cao.
Vị trí (i,j) được chọn khi h(i,j) = min(8 – i, i –1) + min(j – 1, 8 –j) là nhỏ
nhất.
4. Cấu trúc dữ liệu đề nghị
int DeltaX[DONG] = {-2,-1,1,2,-2,-1,1,2};
int DeltaY[COT] = {1,2,2,1,-1,-2,-2,-1};
typedef struct
{
int X;
int Y;
}TOADO;
int BanCo[DONG][COT];
Diễn giải :
• DeltaX, DeltaY : mảng hằng số dùng để phát sinh vị trí đi nước đi
của Mã tại một vị trí bất kỳ.
Tài liệu hướng dẫn thực hành
3
• TOADO : cấu trúc mô tả vị trí của Mã.
• BanCo : mảng hai chiều ghi nhận các nước đi của Mã.
• BanCo[i][j] = 0. Mã chưa nhảy đến ô có toạ độ (i,j).
• BanCo[i][j] = m (m
≠
0). Mã đã nhảy đến ô có toạ độ (i,j) ở
bước thứ m.
5. Cách chọn vị trí đi tiếp
Bước 1 : Phát sinh các vị trí có thể đi được từ vị trí hiện hành.
Bước 2 : Tính heuristic (heuristic 1, heuristic 2) cho từng vị trí.
Bước 3 : Chọn vị trí có heuristic là nhỏ nhất để đi ở bước kế tiếp
Bước 4 : Cập nhật lại bàn cờ
Bước 5 : Quay lại bước 1.
6. Các hàm thực hiện
Hàm Phát sinh nước đi của Mã
void PhatSinhNDMa(int BanCo[][COT], TOADO P, TOADO
DiTiep[], int &n)
BanCo : mảng 2 chiều mô tả trạng thái hiện hành của bàn cờ.
P : điểm hiện tại của Mã cần được phát sinh các nước đi kế tiếp.
DiTiep : các vị trí đi tiếp của Mã ở nước đi kế tiếp.
n : số vị trí phát sinh được.
void PhatSinhNDMa(int BanCo[][COT], TOADO P, TOADO
DiTiep[], int &n)
{
n = 0;
for (i = 0; i < DONG; i++)
{
Tài liệu hướng dẫn thực hành
4
X = P.X + DeltaX[i]; Y = P.Y + DeltaY[i];
if (X >=0 && ....&& BanCo[X][Y] == 0)
{
.. .
n++;
}
}
}
Hàm thực hiện
void main()
{
//Đọc vị trí bắt đầu
//Khởi tạo ma trận BanCo
Buoc = 0;
while (Chưa kết thúc)
{
PhatSinhNDMa(BanCo,P,DiTiep,n);
if (n == 0&& Buoc<DONG*COT)
{
//Kết thúc không thành công
//Thoát
}
for (i = 0; i < n;i++)
{
h = Heuristic(BanCo, DiTiep[i]);
if (h < gtmin)
{
//Ghi nhận lại vị trí Tmp
Tài liệu hướng dẫn thực hành
5
}
}
//Cập nhật lại mảng BanCo
//P = Tmp, thực hiện tiếp
Buoc++;
//kết thúc khi Buoc >= DONG*COT
}
//Xuất mảng BanCo
}