Chúng tôi nghĩ là giải thuật backtracking giải bài toán “Mã đi tuần” đã được trình bày trong tài liệu mà bạn đọc. Và nếu nắm vững giải thuật thì về nguyên tắc bạn sẽ dịch được giải thuật ra chương trình máy tính dùng ngôn ngữ mà bạn ưa thích. Sau đây chúng tôi liệt kê chương trình Pascal giải bài toán này theo yêu cầu của bạn, lưu ý là giải thuật dựa trên bước lặp cơ bản như sau: nếu con mã đang ở vị trí ô cờ (i,j) thì nó có thể đi tiếp 1 trong 8 khả năng khác nhau xung quanh ô (i,j) hiện tại, chúng ta sẽ lần lượt thử cho con mã đi từng khả năng, nếu được thì tốt, nếu cả 8 khả năng đều không đi được ta sẽ lùi con mã về vị trí ô cờ ngay trước đó rồi tiếp tục thử các khả năng chưa thử. Chương trình dùng 2 biến dữ liệu chính là:

• Biến Banco là 1 dãy 8*8 phần tử, mỗi phần tử miêu tả thứ tự nước đi của con mã (từ 0 tới 63), nếu vị trí nào con mã chưa đi qua sẽ có giá trị đầu là -1 để phân biệt.

• Biến Nuocdi là 1 danh sách 64 phần tử lưu giữ trình tự các vị trí ô cờ mà con mã đi qua từ vị trí xuất phát nào đó do user qui định, mỗi vị trí đi qua ta nhớ lại tọa độ (i,j) và chỉ số hướng đi đã thử. Tất cả chỉ số của các dãy đều bắt đầu từ 0.
bắt đầu chương trình đây:

Program MadiTuan;

{Chỉ số hàng cột lớn nhất của bàn cờ : thường là 7}

Const Max = 7;

{Kiểu dữ liệu chứa thông tin của 1 bước đi}

Type ItemRec = Record

x, y : Integer;

huong : Integer;

End;

{ Các biến dữ liệu chính}

Var Banco: Array [0..7,0..7] of Integer;

Nuocdi: Array [0..63] of ItemRec;

SoNuocdi : Integer;

cach : Integer;

{Thủ tục khởi động các giá trị đầu của chương trình}

Procedure Khoidong;

Var i,j : Integer;

Begin

cach := 0;

for i:=0 to Max do

for j:= 0 to Max do

Banco[i,j] := -1;

write(‘Nhập tọa độ hàng chứa con mã : ‘);

readln(Nuocdi[0].y);

write(‘Nhập tọa độ cột chứa con mã : ‘);

readln(Nuocdi[0].x);

Nuocdi[0].huong := 0;

{Thiết lập nước đi đầu tiên của con mã}

SoNuocdi :=0;

Banco[Nuocdi[SoNuocdi].x,Nuocdi[SoNuocdi].y] := 0;

End;



{In kết quả con mã đi trên bàn cờ}

Procedure InKetqua;

Var h,c : Integer;

Begin

cach := cach + 1;

writeln(‘Cách đi thứ : ‘,cach);

for h:= 0 to Max do begin

{ Hiển thị hàng lưới ngang bàn cờ }

for c:= 0 to Max do write(‘+——’);

writeln(‘+’);

{ Hiển thị nội dung hàng thứ h bàn cờ }

for c:= 0 to Max do

write(‘| ‘,Banco[h,c]:2,’ ‘);

writeln(‘|’);

end;

{Hiển thị hàng lưới ngang bàn cờ cuối cùng}

for c:= 0 to Max do write(‘+——’);

writeln(‘+’);

{readln;}

End;



{Thủ tục tìm nước đi kế tiếp}

Function TimNuocKe : Boolean;

Var x, y : Integer;

RetVal : Boolean;

Begin

RetVal := False;

Repeat {lặp tìm nước đi kế tiếp đến khi tìm được hoặc hết cách đi}

while (RetVal=False) and (Nuocdi[SoNuocdi].huong < do begin

Case Nuocdi[SoNuocdi].huong of {thử hướng đi hiện tại}

0 : begin

x := Nuocdi[SoNuocdi].x + 2;

y := Nuocdi[SoNuocdi].y - 1;

end;

1 : begin

x := Nuocdi[SoNuocdi].x + 1;

y := Nuocdi[SoNuocdi].y - 2;

end;

2 : begin

x := Nuocdi[SoNuocdi].x - 1;

y := Nuocdi[SoNuocdi].y - 2;

end;

3 : begin

x := Nuocdi[SoNuocdi].x - 2;

y := Nuocdi[SoNuocdi].y - 1;

end;

4 : begin;

x := Nuocdi[SoNuocdi].x - 2;

y := Nuocdi[SoNuocdi].y + 1;

end;

5 : begin

x := Nuocdi[SoNuocdi].x - 1;

y := Nuocdi[SoNuocdi].y + 2;

end;

6 : begin

x := Nuocdi[SoNuocdi].x + 1;

y := Nuocdi[SoNuocdi].y + 2;

end;

7 : begin

x := Nuocdi[SoNuocdi].x + 2;

y := Nuocdi[SoNuocdi].y + 1;

end

End;

if (0<=x) and (x<=Max) and (0<=y) and (y<=Max) and (Banco[x,y]=-1) then begin

{nếu được thì ghi nhận}

SoNuocdi := SoNuocdi + 1;

Banco[x,y] := SoNuocdi;

Nuocdi[SoNuocdi].x := x;

Nuocdi[SoNuocdi].y := y;

Nuocdi[SoNuocdi].huong := 0;

RetVal:=True;

end else

{nếu không được thì thủ hướng kế tiếp}

Nuocdi[SoNuocdi].huong := Nuocdi[SoNuocdi].huong + 1;

end;

if (RetVal=False) and (SoNuocdi <> 0) then begin

{nếu không tìm được nước đi kế thì lùi con mã lại 1 bước}

Banco[Nuocdi[SoNuocdi].x,Nuocdi[SoNuocdi].y] := -1;

SoNuocdi := SoNuocdi - 1;

Nuocdi[SoNuocdi].huong := Nuocdi[SoNuocdi].huong + 1;

end

until RetVal or (SoNuocdi = 0);

TimNuocKe := RetVal;

End;



{Chương trình chính}

Begin

Khoidong;

while TimNuocKe do begin

if SoNuocdi = (Max+1)*(Max+1)-1 then begin

{nếu tìm được 1 nghiệm}

InKetqua;

Banco[Nuocdi[SoNuocdi].x,Nuocdi[SoNuocdi].y] := -1;

SoNuocdi := SoNuocdi -1;

Nuocdi[SoNuocdi].huong := Nuocdi[SoNuocdi].huong + 1;

end

end

End.

Lưu ý giải thuật backtracking thuộc loại giải thuật vét cạn nên thường có thời gian tính toán rất lớn, cụ thể với bài toán trên nếu kích thước bàn cờ là 8*8 thì giải thuật sẽ phải xét 864 = 2192 hướng đi, các máy PC hiện tại (ngay cả Pentium IV 3,1GHz) cũng phải tốn hàng tỉ tỉ năm mới chạy xong giải thuật. Do đó để tìm được kết quả thực sự, bạn nên chọn kích thước bàn cờ 4,5,6 là vừa (khai báo lại hằng Max = 3,4,5).