Tản mạn xung quanh bài toán mã đi tuần
Trịnh Thanh Hải
Tản mạn xung quanh bài toán mã đi tuần
Đối với các bạn say mê môn Tin học thì bài toán phỏng theo quy luật di chuyển của con mã trên bàn cờ quốc tế rất quen thuộc. Đã có nhiều thuật toán để giải bài toán này. Trong bài viết này chúng tôi muốn trình bày thêm một số suy luận nhằm sáng tỏ câu hỏi: "Từ một vị trí bất kỳ trên bàn cờ, liệu con mã có thể đi đến tất cả các vị trí trên bàn cờ được không?".
Trước tiên ta xét bài toán: "Nếu đặt con mã ở một vị trí bất kỳ trên bàn cờ và chọn một vị trí đích thì liệu con mã có thể đi đến được vị trí đó không? Nếu đi được thì số bước đi tối thiểu là bao nhiêu?"
Để minh hoạ đường đi của con mã ta lập một hệ toạ độ mà gốc toạ độ O(0,0) là vị trí ban đầu của con mã, vị trí kết thúc sau khi di chuyển của con mã là M(x,y).
Ta xét từng trường hợp
+ Số bước đi là 1: từ quy luật di chuyển của con mã trên bàn cờ ta thấy ngay con mã sẽ có 8 khả năng di chuyển khác nhau. Khi đó toạ độ điểm đích của nó sẽ là một trong các trường hợp sau: M1(2,1); M2(1,2); M3(-1,2); M4(-2,1); M5(-2,-1); M6(-1,-2); M7(1,-2); M8(2,-1). Xét toạ độ x và y ta có: |x| +| y| = 3. Mặt khác khi di chuyển một bước, số ô theo bất kỳ hàng hoặc cột đều không quá 2, so với vị trí xuất phát số hàng, cột chênh lệch chỉ là 1 hoặc 2: |x| =< 2 và |y| =< 2. Hơn nữa x,y không cùng lẻ hoặc chẵn. Vậy với x, y không cùng chẵn hoặc lẻ thoả mãn { |x| =< 2, |y| =< 2; |x|+|y| = 3} thì con mã chỉ cần di chuyển một bước để đến vị trí M(x,y).
+ Số bước đi là 2 Sau 2 bước đi toạ độ x, y chỉ có một trong hai khả năng: x, y cùng lẻ hoặc x, y cùng chẵn và thoả mãn:{| x| =< 4 ; |y| =< 4; |x|+|y| =< 6}. Ngược lại nếu ta cho trước toạ độ điểm đích M(x,y) thoả mãn điều kiện trên thì con mã chỉ cần sau 2 bước là có thể đến được điểm M. (riêng để di chuyển tới vị trí M(2,2), N(-2,-2), P(2,2), Q(2,-2) cần 4 lần di chuyển).
+ Số bước đi là 3: Sau 3 bước di chuyển toạ độ x, y không cùng lẻ hoặc cùng chẵn và thoả mãn: {|x| =< 6; |y| =< 6; 3 * |x|+|y| =< 9} và đây cũng là điều kiện toạ độ x, y của điểm M để con mã có thể đến được sau 3 bước di chuyển.
Tiếp tục quá trình xét tương tự, chẳng hạn sau 5 bước di chuyển của con mã ta có |x| +|y| =< 15 trong đó x, y không cùng lẻ hoặc cùng chẵn... Ta có bảng sau:
Điều kiện ràng buộc với toạ độ x, y của điểm đích M(x,y)
Số bước ít nhất để con mã đi tới đích
|x|+|y| = 3; |x| =< 2; |y| =< 2; x, y không cùng lẻ hoặc chẵn
1
|x|+|y| =< 6; |x| =< 4; |y| =< 4; x,y cùng chẵn hoặc lẻ
2
3 * |x|+|y| =< 9; |x| =< 6; |y| =< 6; x,y không cùng chẵn hoặc lẻ
3
6< |x|+|y| =< 12; |x| =< 6; |y| =< 6; x,y cùng chẵn hoặc lẻ
4
9<|x|+|y| =< 15; |x| =< 7; |y| =< 7; x,y không cùng chẵn hoặc lẻ
5
12< |x|+|y| =< 15; |x| =< 7; |y| =< 7; x,y cùng chẵn hoặc lẻ
6
Ta minh hoạ bảng trên qua một vài ví dụ cụ thể:
Hình 2
Giả sử vị trí xuất phát của con mã là góc dưới bên trái, như vậy các ô được gắn toạ độ từ (0,0)... (7,7) ( hình 2)
+ Vị trí ô đích là (3,3). Vì |3|+|3| = 6, hơn nữa cả hai toạ độ x, y đều lẻ nên ta chỉ cần 2 bước để di chuyển từ (0,0) đến (3,3).
+ Vị trí đích là ô (1,6). Ta có |1| + |6| = 7, mặt khác trong 2 số x, y có một số lẻ, một số chẵn. Vậy con mã chỉ cần 3 bước để từ (0,0) đến (1,6)
+ Vị trí đích là ô (2,6). Ta có |2|+|6| = 8, mặt khác x, y cùng chẵn. Vậy để đi từ (0,0) đến (2,6) cần tối thiểu 4 lần di chuyển.
+ Vị trí ô đích là (7,6). Ta có |7| + |6| = 13, mặt khác x, y một số chẵn, một số lẻ. Căn cứ vào bảng trên ta có cố bước di chuyển tối thiểu là 5.
+ Ví trí ô đích là (7,7). Vì |7| + |7| = 14 và x, y cùng là số lẻ nên có bước tối thiểu để đi từ (0,0) đến (7,7) là 6 bước.
Chú ý rằng đây là số bước đi tối thiểu chứ không phải là cách di chuyển duy nhất. Có thể có nhiều cách đi với số bước trên để đến vị trí đích.
Vậy là nếu đặt con mã vào một vị trí bất kỳ trên bàn cờ (ta coi là gốc toạ độ) và chọn một ô bất kỳ (có toạ độ (x,y) với hệ toạ độ đã xác định) làm ô đích thì ta xét thấy x,y chỉ có thể là một trong các khả năng đã liệt kê trong bảng. Do đó con mã hoàn toàn có thể di chuyển tới đích và số lần di chuyển tối thiểu đã được nêu trong bảng.
Căn cứ quy luật di chuyển của con mã sau một bước, so với vị trí xuất phát số hàng, cột chênh lệch chỉ là 1 hoặc 2. Hơn nữa x, y không cùng lẻ hoặc chẵn. |x|+|y|=3; |x|<= 2; |y|<= 2 điều này tương đương với điều kiện x2 + y2 = 5, nên ta có thuật toán tìm vị trí ô có toạ độ (x[i],y[i]) cho bước di chuyển thứ i (i>=1) của con mã là:
for dong:=- 2 to 2 do
for cot:=- 2 to 2 do
if (dong*dong+cot*cot=5) then
begin
a:=x[i-1]+dong;
b:=y[i-1]+cot;
if (ô( a,b) vẫn thuộc bàn cờ) then
Begin
x[i]:=a;
y[i]:=b;
end;
end;
Cuối cùng ta giải quyết bài toán:"Đặt con mã vào một vị trí bất kỳ trên bàn cờ. Tìm chu trình của con mã để ghé thăm một lần duy nhất tất cả các ô còn lại". Kết quả ta tìm được nhiều chu trình đi khác nhau nhưng số bước đi đều là 63.
Để đơn giản ta chọn ô góc dưới bên trái là gốc toạ độ. Như vậy các cột, các dòng được gắn số thứ tự từ 0 đến 7 (hình 2). Theo trên ta có thủ tục Try_ma như sau:
Procedure Try_ma(i:integer);
var
dong,cot:-2..2;
a,b:integer;
Begin
for dong:=-2 to 2 do
for cot:=-2 to 2 do
if (dong*dong+cot*cot=5) then
begin
a:=x[i-1]+dong;
b:=y[i-1]+cot;
if (0=<a)and(a<=7)and(0=<b)and(b<=7)and(bc[a,b]) then
begin
x[i]:=a;
y[i]:=b;
bc[a,b]:=false;
if i< 63 then Try_ma(i+1)
else xuat;{thu tuc Xuat viet chu trinh con ma ra man hinh}
bc[a,b]:=true
end;
end;
end;
Trong bài trên sử dụng bc là mảng 2 chiều kiểu Boolean: bc[x,y]:=true nếu con mã chưa đi qua ô [x,y]. Trong thủ tục này, số bước duyệt cho một lần lựa chọn là 25, để giảm bớt số lần duyệt ta có thể căn cứ vào quy luật di chuyển cuả con mã sau một bước đã phân tích ở trên. Thiết lập mảng C, D lưu trữ toạ độ tương ứng 8 khả năng di chuyển của con mã:
c[1]:=2;c[2]:=1;c[3]:=-1;c[4]:=-2;c[5]:=-2;c[6]:=-1;c[7]:= 1; c[8]:= 2;
d[1]:=1;d[2]:=2; d[3]:=2;d[4]:= 1;d[5]:=-1;d[6]:=-2;d[7]:=-2; d[8]:=-1;
Mảng 2 chiều bc[x,y] ghi nhận con mã đã đi đến vị trí (x,y) sau bước di chuyển thứ i. Khởi đầu các giá trị của mảng bc[x,y]=0. Vị trí ban đầu con mã (io,jo).
Procedure Try_ma(i:byte);
begin
if i>63 then xuat {thủ tục Xuat viết chu trình con mã ra màn hình}
else
for j:=1 to 8 do
begin
x:=i0+c[j];
y:=j0+d[j];
then
begin
bc[x,y]:=i;
i0:=x;
j0:=y;
Try_ma(i+1);
i0:=x-c[j];
j0:=y-d[j];
bc[x,y]:=0;
end;
end;
end;
Từ đây ta đặt ra các bài toán khác, chẳng hạn: "Trên bàn cờ n x n ô (n>3) ta đặt con mã vào một vị trí (io,jo) bất kỳ trên bàn cờ. Hỏi trên bàn cờ đó còn sắp được thêm bao nhiêu con mã để không con nào ăn được con nào?. Hoặc cho trước vị trí xuất phát (io,jo) và một ô đích cần tới (x,y) trên bàn cờ. Liệu có thể tính trước được sẽ có bao nhiều đường đi khác nhau với cùng một số bước tối thiểu?... Rất mong được trao đổi với các bạn.
Xin liên hệ với địa chỉ
haisp@.edu.vnn.vn hoặc Trịnh Thanh Hải - Khoa Toán trường Đại học sư phạm - ĐH Thái Nguyên.
Trịnh Thanh Hải.