Thuật toán hiệu quả giải bài toán Mã đi tuần
Nguyễn Văn Trung
Hẳn các bạn học lập trình pascal đã biết đến bài toán ″Mã đi tuần″:
Cho bàn cờ tổng quát nxn và một quân mã. Hãy chỉ ra một hành trình của Mã xuất phât từ
ô (x,y), đi qua tất cả các ô còn lại của bàn cờ, mỗi ô đúng một lần (luật đi của mã như luật
cờ vua).
Và hẳn bạn đã biết thuật giải củabài toán này. Đó là dùng kỹ thuật duyệt quay lui xét các ô
con. Mã có thể đi tới để tìm ra một hành trình. Tuy nhiên, việc duyệt như vậy là hết sức
chậm bởi phải xét quá nhiều trường hợp. Và với thuật toán như vậy, khi kích thước bàn cờ
vượt quá 8(n>8) thì có thể nói bạn sẽ phải ngồi chờ đợi máy tính cho đến khi mất hết kiên
nhẫn. Vì vậy mục đích của bài toán này là nêu ra một thuật giải hiệu quả hơn cho bài toán
Mã đi tuần.
Ta coi bàn cờ nxn như một đồ thị vô hướng và thừa nhận ô (i,j) của bàn cờ là đỉnh (i-
1xn+j) của đồ thị.
Ví dụ: ô (1,n) là đỉnh thứ (1-1)xn+n=n của đồ thị
ô (2,3) của bàn cờ 3x3 là đỉnh thứ (2-1)x3+3 = 6 của đồ thị.
Như vậy việc tìm hành trình để con mã đi hết các ô của bàn cờ ↔ Tìm ra một hành trình đi
hết các đỉnh của đồ thị, mỗi đỉnh chỉ đi qua một lần.
+) Việc kiểm tra xem từ đỉnh u có thể tới đỉnh v hay không ta có thể thấy như sau:
Giả sử ô(x
1
,y
1
) có đỉnh ở đồ thì là u → (x
1
-1)xn +y
1
=u
Dễ thấy nếu (u mod n =0) thì x
1
= u div n; y

qua hay chưa.
Toàn bộ văn bản chương trình như sau:
Program Ma_di_tuan;
Const max =50;
Var b:array[1..max*max] of integer;
N,x,y,count:integer;
Function kt(u,v:integer):boolean;
Var x1,x2,y2,y1:integer;
Begin x1:=(u-1)div n +1;
If u mod n =0 then y1:=n
Else y1:=u mod n;
X2:=(v-1) div n+1;
If v mod n =0 then y2:=n
Else y2:=u mod n;
Kt:= (abs (x1-x2)*abs(y1=y2)=2);
End;
Function Dembac(u:integer):integer; {dem so dinh co the den tu u ma chua di qua}
Var tg,v:integer;
Begin tg:=0;
For v:=1 to n*n do {Duyet mo dinh}
If (b[v]=0) and kt(u,v) then inc(tg);
Dembac:=tg;
End;
Function Bacnhonhat(u:integer):integer;
Var v,tg:integer
Begin tg:=10;
For v:=1 to n*n do
If (b[v]=0) and kt(u,v) and (tg>Dembac(v)) then
Tg:=dembac(v);
Bacnhonhat:=tg;

đó là nếu không có hành trình, do phải duyệt hết các trường hợp nên chạy không hơn
chương trình duyệt bình thường, các bạn thử tìm cách giải xem? Nếu các bạn có thăc mắc
xin liên hệ với tác giả qua mail: ngtrung882003@yahoo.