Mã đi tuần! Xin giúp đỡ !!!

[danhdanh111]

Mình đang gặp rắc rối trong bài mã đi tuần. Nếu bàn cờ là 8*8 thì chắc phải đợi 1 năm để tìm ra hết các nghiệm. Có bạn nào bít cách thoát khỏi đệ quy khi tìm được nghiệm đầu tiên không? (Nếu bạn nào bít cách khử đệ quy để tìm lời giải cho bài toán này thì càng tốt!)
Dưới đây là hàm đệ quy tìm đường đi dựa trên sách của tác giả Hoàng Kiếm:

void Try(int i, int x, int y)
{
int u, v, j;
for ( j = 0; j < 8 ; j++)
{
u = x + dx[j];
v = y + dy[j];
if ( BanCo[u][v] == 0 )
{
BanCo[u][v] = i;
if ( i < mn )
Try ( i + 1, u, v );
else
Result();

BanCo[u][v] = 0;
}
}
}

[verbway]

Nếu bạn tìm hết các nghiệm thì đợi cả năm là phải rồi. Khử đệ qui hầu như không nhanh hơn đệ qui là mấy (khử đệ qui thường phải dùng stack tự tạo thì cũng gần giống như đệ qui dùng stack hệ thống).

Còn nếu muốn dừng sau khi tìm thấy biên đầu tiên thì quá dễ. Dùng hàm exit để thoát khỏi chương trình luôn hoặc thêm một biến toàn cục và kiểm tra nó.

Ví dụ:
int stop = 0; // biến toàn cục
void Try(...)
{
...
for ( j = 0; j < 8 && !stop; j++) // ngừng vòng lặp nếu stop != 0
...
else {
Result(); // lấy kết quả đầu tiên
stop = 1; // lệnh dừng đệ qui
}

Cách khác có thể cho Try trả về giá trị 1 là tiếp tục, 0 là dừng cũng được.

[danhdanh111]

Cám ơn bạn verbway nhiều nhá! Mình cũng nghĩ khai báo hàm Try là: int Try(...) rồi cho nó return 1 để thoát. Nhưng thực sự mình không nắm vững về đệ quy nên không bit đặt điều kiện thoát ở đâu? Nhờ bạn nên mình bít rồi!!!
Cám ơn bạn nhiều nhá!!!

[nadongtae]

Có một cách khác là chia đôi bàn cờ ra và chỉ cho mã đi tuần trên 1/2 bàn cờ sao cho con mã đó đi hết các ô trong 1/2 bàn cờ và điểm cuối của nước đi là mép 1/2 bàn cờ. => điều này là do tính đối xứng của bàn cờ. :d Từ đó bạn sẽ có số nghiệm cần tìm mà chỉ phải xét 1/2. Ngoài ra bạn có thể coi bàn cờ như một ma trận 64x64. Rồi chuyển về bài toán tìm tất cả đường đi trên ma trận.

[verbway]

Em chưa từng làm bài này đúng không? Đúng là spam rồi ;)

Bàn cờ đối xứng thật, nhưng quân Mã đi không đối xứng nên việc chia nhỏ bàn cờ ra không giúp được gì cả. Nếu không người ta sẵn sàng chia bàn cờ đi 64 x 64 lần và giải trên bàn cờ... có 1 ô thôi. Ý kiến thứ 2 của em cũng... vô ích nốt.

[NgôiSaoMayMắn]

Một con mã ở vị trí (r, c) có thể đi đến tối đa 8 vị trí sau:
(r-1,c-2), (r + 1, c - 2), (r - 2, c - 1), (r + 2, c - 1), (r - 2, c + 1), (r + 2, c + 1), (r - 1, c + 2) và (r + 1, c + 2)

Các vị trí mới phải thỏa mãn điều kiện 0<=newR<=7 và 0<=newC<=7.

Để dễ quản lí ta có thể khai lưu trữ các độ dời vào 2 array như sau:
const int Offset1[] = {-2,-2, -1,-1, 1, 1, 2, 2};
const int Offset2[] = {-1, 1, -2, 2, -2, 2, -1, 1};

Thuật toán mã đi tuần đùng đệ quy như sau:
// A[8][8]: bàn cờ, ban đầu các cell có giá trị = -1 (chưa đặt quân mã)
// N: kích thước bàn cờ (ở đây là 8)
// Px: vị trí cột khởi đầu
// Py: vị trí dòng khởi đầu
// Count đếm số vị trí đã đặt quân mã
void Horse(int A[8][8], int N, int Py, int Px, int& Count)
{
if(Count==N*N)// Kiểm tra xem đã đặt đủ số quân mã chưa - 8 x 8 = 64
{
if(A[Py][Px]==-1)// Nếu vị trí này chưa đặt quân mã
{
A[Py][Px] = Count;// gán giá trị thứ tự
ShowResult_Horse(A, N);// In matrix A (kết quả)
A[Py][Px] = -1;
getch();
}
}
else
{
if(A[Py][Px]==-1)// Chua dat
{
int tmp;
int r, c;

A[Py][Px] = Count++;
tmp = Count;

// Tìm các vị trí lân cận (có 8 vị trí)
for(int i = 0; i < 8; i++)
{
c = Px + Offset1[i];
r = Py + Offset2[i];

if((c >=0)&&(c < N)&&(r >= 0)&&(r < N))
{
Horse(A, N, r, c, Count);
if(tmp < Count)
{
A[r][c] = -1;
Count = tmp;
}
}
}

A[Py][Px] = -1;
Count--;
}
}
}

Chạy đoạn mã trên như sau:
int N = 8;
int A[8];

for(int i = 0 ; i < N; i++)
for(int j = 0; j < N; j++)
A[i][j] = -1;

int Px = 0;
int Py = 0;
int Count = 1;
Horse(A, N, Py, Px, Count);


Hy vọng giúp ích cho bạn.

[nadongtae]

Em chưa từng làm bài này đúng không? Đúng là spam rồi ;)

Bàn cờ đối xứng thật, nhưng quân Mã đi không đối xứng nên việc chia nhỏ bàn cờ ra không giúp được gì cả. Nếu không người ta sẵn sàng chia bàn cờ đi 64 x 64 lần và giải trên bàn cờ... có 1 ô thôi. Ý kiến thứ 2 của em cũng... vô ích nốt.

Người ta chỉ chia đôi thôi bác ơi. Tui có nói chia thành 64 ô đâu. Chán. Tôi có nói quan mã đi đối xứng đâu. Tôi chỉ nói là quân mã đi hết các ô trong bàn cờ rút gọn 8x4 theo điều kiện mới rồi từ đó tính được số nước đi trên toàn bàn cờ. Đây là bài toán đồ thị 2 phía.
Ý kiến thứ 2 là một cách giải để khỏi phải kiểm tra điều kiện đi theo hình chữ L của quân mã. Một cách giải quyết bài toán bằng đồ thị. Có gì vô ích. hành trình quân mã là một bài toán trong đồ thị có đường đi Hamilton.

[vtnphong]

Người ta chỉ chia đôi thôi bác ơi. Tui có nói chia thành 64 ô đâu.

Vấn đề là nếu chia 2 thì bạn giới hạn con mã chỉ đi được trong một nửa bàn cờ thôi. Sẽ thiếu những đường đi đòi hỏi việc con mã phải nhảy qua nhảy lại giữa 2 nửa bàn cờ. Cách này không thể liệt kê tất cả các đường đi được. Tốt nhất là cứ làm cách truyền thống đi. Còn cái bạn mở topic này, bộ bàn cờ 8x8 mà đệ quy quay lui thì phải chạy 1 năm thiệt hả (tìm tất cả nghiệm đó)? Mình nghi ngờ lắm đó nha, bạn đã chạy thử chưa vậy :D?

[nadongtae]

Vấn đề là nếu chia 2 thì bạn giới hạn con mã chỉ đi được trong một nửa bàn cờ thôi. Sẽ thiếu những đường đi đòi hỏi việc con mã phải nhảy qua nhảy lại giữa 2 nửa bàn cờ. Cách này không thể liệt kê tất cả các đường đi được. Tốt nhất là cứ làm cách truyền thống đi. Còn cái bạn mở topic này, bộ bàn cờ 8x8 mà đệ quy quay lui thì phải chạy 1 năm thiệt hả (tìm tất cả nghiệm đó)? Mình nghi ngờ lắm đó nha, bạn đã chạy thử chưa vậy :D?

Bạn đọc kĩ lại đi tui có nói điều kiện thêm để giải quyết bài toán. Điều kiện là quân mã phải có nước cuối cùng nằm ở 1 trong 8 ô giữa bàn cờ đã chia đôi. Khi này sẽ tồn tại một nước cờ ở nửa bàn cờ còn lại có nước đi qua hết tất cả các ô và dừng ở một ô ở rìa thỏa điều kiện là ô đã dừng bên trên có thể tới ô đó đúng 1 bước đi của quân mã.
Bạn có thể chạy chương trình của bạn NgoiSaoMayMan và ngồi liệt kê ra thử coi tui nói đúng hay sai.
Bài này đã được chứng minh đàng hoàng trên tạp chí tin học và tuổi trẻ cách đây khoảng 4-5 năm.

[vtnphong]

Bạn đọc kĩ lại đi tui có nói điều kiện thêm để giải quyết bài toán. Điều kiện là quân mã phải có nước cuối cùng nằm ở 1 trong 8 ô giữa bàn cờ đã chia đôi. Khi này sẽ tồn tại một nước cờ ở nửa bàn cờ còn lại có nước đi qua hết tất cả các ô và dừng ở một ô ở rìa thỏa điều kiện là ô đã dừng bên trên có thể tới ô đó đúng 1 bước đi của quân mã.
Bạn có thể chạy chương trình của bạn NgoiSaoMayMan và ngồi liệt kê ra thử coi tui nói đúng hay sai.
Bài này đã được chứng minh đàng hoàng trên tạp chí tin học và tuổi trẻ cách đây khoảng 4-5 năm.

Thì cũng có ai nói là thuật giải của bạn sai đâu (mình bỏ báo tin học tuổi trẻ cũng khoảng 4-5 rồi nên mình ko biết thuật toán này :D). Chỉ là mình bảo nó sẽ bỏ sót một số nước đường đi của con mã mà thôi (do đó không thể dùng để liệt kê tất cả các đường đi được). Còn nếu bạn chỉ muốn tìm một nghiệm thì cứ tự nhiên :)

[ntrongdangkhoa]

Kô sai đâu nè:

#include <stdio.h>
#include <conio.h>

#define KICHTHUOC 5

// Do lech cua dong & cot giua vi tri con ma den cac nuoc di
int d[] = {2, 2, 1, -1, -2, -2, -1, 1};
int c[] = {1, -1, -2, -2, -1, 1, 2, 2};

int banco[KICHTHUOC][KICHTHUOC]; // Vi tri cac nuoc di
int soloigiai = 0;

void khoitao(); // Xoa het nuoc di tren ban co
void nuocdi(int, int, int); // Ham tim nuoc di cua con ma
void innuocdi(int banco[][KICHTHUOC]); // In cac nuoc di cua con ma

void main()
{
int i, j;

// Duyet het ban co de chon nuoc di thu 1
for (j=0; j<KICHTHUOC; j++)
for (i=0; i<KICHTHUOC; i++)
{
khoitao(); // Xoa het nuoc di tren ban co
banco[j][i] = 1; // Nuoc di thu 1 tai o (j, i)
nuocdi(2, j, i); // Nuoc di thu 2 xuat phat tu o (j, i)
}
}

// Xoa het nuoc di tren ban co
void khoitao()
{
int i, j;
for (j=0; j<KICHTHUOC; j++)
for (i=0; i<KICHTHUOC; i++)
banco[j][i] = 0;
}

// Ham tim nuoc di thu n, xuat phat tu o (y, x)
void nuocdi(int n, int y, int x)
{
for (int i=0; i<8; i++) // 8 nuoc di co the
{
// Chon thu huong di thu i (trong 8 huong di)
int ymoi = y + d[i];
int xmoi = x + c[i];

// Neu huong di nay hop le va tai vi tri do chua co nuoc di nao
if (ymoi>=0 && ymoi<KICHTHUOC && xmoi>=0 && xmoi<KICHTHUOC && banco[ymoi][xmoi] == 0)
{
// => Ghi nhan nuoc di thu n nay
banco[ymoi][xmoi] = n;

// Neu nuoc di nay la nuoc di cuoi cung => in tat cac nuoc di
if (n == KICHTHUOC*KICHTHUOC)
innuocdi(banco);
else
nuocdi(n+1, ymoi, xmoi); // Nguoc lai, tim nuoc di ke tiep

// Du thanh cong hay that bai deu quay lai de tim loi giai moi
// <=> phuc hoi trang thai truoc khi di nuoc di thu n
banco[ymoi][xmoi] = 0;
}
}
}

// In cac nuoc di cua con ma
void innuocdi(int banco[][KICHTHUOC])
{
int i, j;
printf("Loi giai thu %d:\n", ++soloigiai);


printf(" ");
for (i=0; i<KICHTHUOC; i++)
printf("%3d", i);
printf("\n");

for (j=0; j<KICHTHUOC; j++)
{
printf("%d ", j);

for (i=0; i<KICHTHUOC; i++)
{
printf("%-3d", banco[j][i]);
}

printf("\n");
}

printf("\n\n");
}