Bài toán ngựa đi tuần

Cho bàn cờ có n x n ô . Một con ngựa được phép đi theo luật cờ vua, đầu tiên được đặt ở ô có tọa độ x0 , y0. Vấn đề là hãy chỉ ra các hành trình (nếu có) của ngựa – Đó là ngựa đi qua tất cả các ô của bàn cờ, mỗi ô đi qua đúng một lần .

Cách giải quyết rõ ràng là xét xem có thể thực hiện một nước đi tiếp nữa hay không. Sơ đồ đầu tiên có thể phát thảo như sau:

Try(i)

for ( j = 1 → k)

If ( x_i chấp nhận được khả năng k)

{

Xác định x_i theo khả năng của k;

Ghi nhận trạng thái mới;

If (i<n²)

Try(i+1);

Else

Ghi nhận nghiệm;

Trả lại trạng thái cũ của bài toán;

}

Để mô tả chi tiết thuật toán, ta quy định về kiểu dữ liệu lưu trữ và các thao tác:

• Biểu diễn bàn cờ .
• Các khả năng chọn lựa cho xi ?
• Cách thức xác định xi theo j.
• Cách thức ghi trạng thái mới, trả về trạng thái cũ
• Ghi nhận nghiệm….

* Ta sẽ biểu diễn bàn cờ bằng 1 ma trận vuông cấp n : int h[n][n]; Sở dĩ thể hiện mỗi ô cờ bằng 1 số nguyên thay cho giá trị boole (để đánh dấu ô đã được đi qua chưa) là vì ta muốn lần dò theo quá trình dịch chuyển của con ngựa

Ta qui ước như sau :

h[x][y] = 0 ≡ Ô <x,y> ngựa chưa đi qua;

h[x][y] = I ≡ Ô <x, y> ngựa đã đi qua ở bước thứ i (1 ≤ i ≤ n² ).

* Các khả năng chon lựa cho x_i ? Đó chính là các nước đi của ngựa mà x_i có thể

chấp nhận được.

Với cặp tọa độ bắt đầu <x,y> như trong hình vẽ, có tất cả 8 ô <u,v> mà

con ngựa có thể đi đến. Giả sử chúng được đánh số từ 0 đến 7 như hình sau:

Một phương pháp đơn giản để có được u, v từ x, y là ta dùng 2 mảng a và b lưu trữ các sai biệt về tọa độ. Nếu ta dùng một chỉ số k để đánh số "bước đi tiếp " thì chi tiết đó được thể hiện bởi : u = x +a[k]; v = y + b[k]; k = 0,7 .

Điều kiện "chấp nhận được" có thể được biểu diễn kết hợp của các điều kiện:

- Ô mới phải thuộc bàn cờ (1 ≤ u ≤ n và 1 ≤ v ≤ n) và chưa đi qua ô đó,

nghĩa là h[u,v] = 0;

* Để ghi nhận nước đi hợp lệ ở bước i, ta gán h[u][v] = i; và để hủy một nước đi thì

ta gán h[u][v] = 0.

* Ma trận h ghi nhận kết quả nghiệm. Nếu có <x,y> sao cho h<x,y> = 0 thì đó không phải là lời giải của bài toán , còn ngược là h chứa đường đi của ngựa. Vậy thuật toán có thể mô tả như sau :

Input n, //Kích thước bàn cờ

x, y;//Toạ độ xuất phát ở bước i

Output h;

Mô tả :

Try(i, x, y)

for(k = 0; k <= 7; k++)

{

u = x + a[k];

v = y + b[k];

if (1 <= u ,v <= n &&h[u][v] == 0)

{

h[u][v] = i;

if (i < n*n) Try(i+1,u,v);

else

xuat_h(); // In ma trận h

}

h[u][v] = 0;

}

}

Thủ tục này xuất tất cả các lời giải, nếu có.

Thủ tục đệ qui được khởi động bằng một lệnh gọi các tọa độ đầu x₀, y₀ là tham số. Ô xuất phát có trị 1, còn các ô khác được đánh dấu còn trống.

H[x₀ ][y₀ ] = 1; Try(2,x , y );

Các mảng a và b có thể khởi đầu như sau :

int a[8]= {2,1,-1,-2,-2,-1,1,2};

int b[8]= {1,2,2,1,-1,-2,-2,-1};

* Các lời giải sau là một số kết quả cho từ thuật toán trên :

* Với n = 5, các tọa độ xuất phát sau không có lời giải : (2,3), (3,2)...