Bài toán quan mã đi tuần cho cả toán & tin học

Từ một trò chơi
thành bài toán lý thú
Bài toán Quân mã đi tuần
Hành trình của quân Mã đi tuần
Đây là bài toán di chuyển một quân mã trên bàn cờ vua ( 8 x 8). Quân mã được đặt ở một ô trên một bàn cờ trống; nó phải di chuyển theo quy tắc của cờ vua để đi qua mỗi ô trên bàn cờ đúng một lần.
Có rất nhiều lời giải cho bài toán, chính xác là
26.534.728.821.064 lời giải
Hành trình đóng của quân mã
trên bàn cờ
Hành trình trong đó quân mã có thể kết thúc tại chính ô mà nó khởi đầu.
Một hành trình như vật được gọi là “Hành trình đóng”.
Như hình bên
Hành trình mở
Có những hành trình, trong đó quân mã sau khi đi hết tất cả 64 ô của bàn cờ (kể cả ô xuất phát), thì từ ô cuối của hành trình không thể đi về ô xuất phát chỉ bằng một nước đi. Những hành trình như vậy được gọi là ”Hành trình mở”.
Như hình bên
Hai lời giải với bàn cờ 8 x 8
Các biến thể mở rộng bài toán
Nhiều biến thể với chủ đề “quân mã trên bàn cờ” đã được các nhà toán học nghiên cứu, trong đó có nhà toán học Euler. Các biến đổi có thể theo các hướng:
- thay đổi kích thước bàn cờ 8x8  6x6; 10x10…
- biến thành trò chơi hai người theo ý tưởng này
- giảm nhẹ các yêu cầu trên đường đi của quân mã: Đi hình theo hình vuông, theo chiều kim đồng hồ…
2 người chơi trên bàn cờ 6x6
Chu trình Hamiltonian
Bài toán quân mã đi tuần là một dạng của bài toán tổng quát hơn là bài toán tìm đường đi Hamilton trong l‎ý thuyết đồ thị. Đây là một bài toán NP-đầy đủ. Bài toán tìm hành trình đóng của quân mã là một bài toán cụ thể của bài toán tìm chu trình hamiltonian.
Hành trình của quân mã trên nửa bàn cờ đã được giới thiệu dưới dạng thơ trong một tác phẩm tiếng Phạn.
Giải thuật đầu tiên đầy đủ cho bài toán về hành trình của quân mã là Giải thuật Warnsdorff, công bố lần đầu năm 1823 bởi H. C. Warnsdorff.

Thuật giải đệ quy:
Tại mỗi bước lần lượt cho quân mã thử tất cả các nước đi kế tiếp (tám nước đi kế tiếp). Với mỗi bước đi, kiểm tra xem nếu nước đi hợp lệ (chưa đi qua và ở trong bàn cờ) thì thử đi nước này. Nếu quân mã đã đi qua hết bàn cờ thì xuất kết quả. Ngược lại thì gọi đệ quy tiếp cho vị trí mới thử trên. Lưu ý là mỗi khi vị trí đã đi qua được đánh dấu chính bằng chính thứ tự nước đi trên bàn cờ. Sau khi không thử vị trí này thì phải bỏ đánh dấu để chọn giải pháp khác (trường hợp quay lui).
Nếu coi các ô của bàn cờ là các đỉnh của đồ thị và các cạnh là nối giữa hai đỉnh tương ứng với hai ô mã giao chân thì dễ thấy rằng hành trình của quân mã cần tìm sẽ là một đường đi Hamilton. Ta có thể xây dựng hành trình bằng thuật toán quay lui kết hợp với phương pháp duyệt ưu tiên Warnsdorff: Nếu gọi deg(x, y) là số ô kề với ô (x, y) và chưa đi qua (kề ở đây theo nghĩa đỉnh kề chứ không phải là ô kề cạnh) thì từ một ô ta sẽ không thử xét lần lượt các hướng đi có thể, mà ta sẽ ưu tiên thử hướng đi tới ô có deg nhỏ nhất trước.
Thứ tự tám nước đi theo chiều kim đồng hồ
Thuật giải với n chẵn và n lẻ
Trong trường hợp có tồn tại đường đi, phương pháp này hoạt động với tốc độ tuyệt vời: Với mọi n chẵn trong khoảng từ 6 tới 18, với mọi vị trí ô xuất phát, trung bình thời gian tính từ lúc bắt đầu tới lúc tìm ra một nghiệm < 1 giây.
Tuy nhiên trong trường hợp n lẻ, có lúc không tồn tại đường đi, do phải duyệt hết mọi khả năng nên thời gian thực thi lại hết sức tồi tệ. (Có xét ưu tiên như trên hay xét thứ tự như trước kia thì cũng vậy thôi).
Cấu trúc dữ liệu:
Mảng board[MAX][MAX]: lưu bàn cờ, trong đó board[i][j] là ô (i, j); giá trị của board[i][j] là 0 khi quân mã chưa đi qua, và >0 khi quân mã đã đi qua, giá trị board[i][j] lúc này chính là thứ tự nước đi trên hành trình.
Mảng dr[8], dc[8]: lưu các độ dời của bước đi kế tiếp, có tám nước đi có thể cho vị trí quân mã hiện tại. Do đó để đi nước thứ i ta chỉ cần cộng thêm dr[i] cho dòng và dc[i] cho cột!.
dr[ ] = {-2, -2, -1, -1, 1, 1, 2, 2}
dc[ i] = {-1, 1, -2, 2, -2, 2, -1, 1}
Cài đặt bằng ngôn ngữ C++
#include
#include
#include
#include

using namespace std;
#define MAX 60

struct nuocDi
{
char n; //Số ô có thể đi tiếp
char x, y; //Vị trí
};

int danhDau[MAX + 1][MAX + 1];
int kichThuoc;

char dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
char dy[] = { 1, -1, 2, -2, 2, -2, 1, -1};

nuocDi tam;

int thoat = 0;

void xuat()
{
int i, j;
for (i = 1; i<= kichThuoc; i++)
{
for (j = 1; j <= kichThuoc; j++)
cout << setw(3) << danhDau[i][j] << " ";
cout<}
thoat = 1;
}

int tinhSoNuocDi(int x, int y)
{
int i, j, n = 0;
for (int k = 0; k < 8 ; k++)
{

i = x + dx[k];
j = y + dy[k];
if (i>=1 && i <= kichThuoc && j >=1 && j <= kichThuoc && danhDau[i][j] == 0)
n++;
}
return n;
}

void diTuan(char x, char y, int buoc)
{
if (buoc == kichThuoc * kichThuoc)
xuat();
else
{
char i, j, soNuocDi = 0;
nuocDi luaChon[8];

for (char k = 0; k < 8 ; k++)
{

i = x + dx[k];
j = y + dy[k];
if (i>=1 && i <= kichThuoc && j >= 1 && j <= kichThuoc && danhDau[i][j] == 0)
{
tam.n = tinhSoNuocDi(i, j);
tam.x = i;
tam.y = j;
luaChon[soNuocDi++] = tam;
}
}

if (soNuocDi > 0)
{
//Sắp xếp các nước đi tăng dần theo số ô có thể đi tiếp
for (char i = 0; i < soNuocDi - 1; i++)
for (char j = i + 1; j < soNuocDi; j++)
if (luaChon[i].n > luaChon[j].n)
{
tam = luaChon[i];
luaChon[i] = luaChon[j];
luaChon[j] = tam;
};

for (char i = 0; i < soNuocDi && !thoat; i++)
{
danhDau[luaChon[i].x][luaChon[i].y] = buoc + 1;
diTuan(luaChon[i].x, luaChon[i].y, buoc + 1);
danhDau[luaChon[i].x][luaChon[i].y] = 0;
}
}
}
}
int main()
{
int x, y;
cout << "Nhap kich thuoc ban co: ";
cin >> kichThuoc;
cout << "Vi tri xuat phat:" << endl;
cout << " dong = "; cin >> x;
cout << " cot = "; cin >> y;
memset(danhDau[0], 0, sizeof(danhDau));
danhDau[x][y] = 1;
diTuan(x, y, 1);
getch();
return 0;
}



Mời các bạn vào thử
Theo http://kithuatlaptrinh.tk; NST PH Hoạt 30/5/2012