Tài liệu

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

Science and Technology

Bài toá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 .

Phân tích thiết kế thuật toá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 ( xi chấp nhận được khả năng k)

{

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

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

If (i<n2)

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 ≤ n2 ).

* Các khả năng chon lựa cho xi ? Đó chính là các nước đi của ngựa mà xi 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 x0, y0 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[x0 ][y0 ] = 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)...

Đánh giá:
0 dựa trên 0 đánh giá

Tuyển tập sử dụng module này

Nội dung cùng tác giả
 
Nội dung tương tự