Thuật toán hiệu quả giải bài toán Mã đi tuần

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ử ô(x1,y1) có đỉnh ở đồ thì là u → (x1 -1)xn +y1 =u

Dễ thấy nếu (u mod n =0) thì x1 = u div n; y1 =n

Còn nếu (u mod n <>0) thì x1 = u div n -1, y1 =u mod n. (Bạn có thể thấy nếu vẽ hình ra)

Có hai cách để chúng ta tìm ra xem hai đỉnh u và v có thể đi đến từ nhau hay không:

- Dùng mảng để lưu lại (mảng logic), như vậy nhanh hơn nhưng do không gian nhớ hạn

chế của Pascal, nếu ta khai báo b[1..nxn,1..nxn] thì sẽ không thể giải khi n >10.

- Vậy ta sẽ viết 1 hàm kt(u,v) kiểu boolean xem từ u có thể tới v không. Đoạn mã như sau.

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;

+) Khác với cách duyệt xét tất cả các ô có thể đến từ ô đang đứng, ở đây ta chỉ xét và chọn

ô để đi tiếp theo từ ô đang đứng khi bậc của ô đó là nhỏ nhất. (Ta gọi bậc của ô (x,y) là số

ô có thể đến từ sô này mà chưa hề đi qua).

Như vậy số bậc của đỉnh u là số đỉnh có thể đến từ đỉnh u mà các đỉnh chưa hề đi qua.

Ta có thể dùng hàm Dembac(u) để đếm từ đỉnh u và hàm Bacnhonhat(u) để lưu giá trị của

bậc của đỉnh v nào đó có thể đến từ u và bậc của nó là nhỏ nhất.