Hỏi về Bài toán con mã (The Knight's tour problem), thuật toán quay lui

Rok_Hoang · April 7, 2015, 12:35pm

#include <stdio.h>
#define index 5 //rom and column
#define X 2
#define	Y 2
struct toado
{
	int x;
	int y;
};
toado b[index*index];
int v[]={-1,1,2,2 ,1 ,-1,-2,-2};
int h[]={2 ,2,1,-1,-2,-2,-1,1};
int dem=0;
int	horseTrace(int a[index][index],int x,int y,int n)
{
	if ((x<0) || (x>index-1) || (y<0) || (y>index-1) || (a[x][y]==1))
		return 0;
	toado temp={x,y}; //push
	b[n-1]=temp;
	a[x][y]=1;
	if (n==(index*index))
	{	
		int i;
		printf("\n%i: ",++dem); //pop
		for (i=0;i<(index*index);i++)
		{	
			temp=b[i];
			printf("%i-%i ",temp.x,temp.y);
		}
		a[x][y]=0;
		return 1;
	}
	else
	{	
		int i;
		int flag=0;
		int xTemp, yTemp;
		for(i=0;i<8;i++)
		{
			xTemp=x+v[i];
			yTemp=y+h[i];
			if (horseTrace(a,xTemp,yTemp,n+1))
				flag=1;
		}
		a[x][y]=0;
		if (flag) 
			return 1;
		else
			return 0;
	}
}
int main()
{
	int a[index][index]={0};
	if (!horseTrace(a,X,Y,1))
		printf("Ko tim thay loi giai");
	getchar();
	getchar();
	return 0;
}

khoa code tí :)) lủng củng quá

nhatlonggunz · April 7, 2015, 12:47pm

Em cám ơn anh.
Nhưng em đang thắc mắc sao code em nó chạy không ra (tuy e đã sửa giống ông kia)

Itachi_Citus · April 7, 2015, 12:59pm

[Khoe] Bài tìm hiểu mã đi tuần hồi trước của nhóm mình. dù có vài chỗ viết nhảm https://drive.google.com/file/d/0BwFOqsjqEVKYd3FnZVlad0JIejQ/view?usp=sharing

Rok_Hoang · April 7, 2015, 1:31pm

Thuật toán em làm đúng rồi đấy có điều để 8 ô, mã nhảy không nổi
Em thay đổi xuống khoảng 5 nhé
sửa lại chỗ điều kiện vòng for chỗ //Try all next move nhé k<8 không phải N
em có thể cải thiện thuật toán bằng cách chọn bước đi kế tiếp bằng cách đo góc (góc nhỏ nhất)

nhatlonggunz · April 7, 2015, 1:37pm

Thế mà code của ông tác giả (code đầu tiên ấy), run phát là ra (cũng 8 ô):

Còn code em:

Em #define N 8 rồi anh :’(

Rok_Hoang · April 7, 2015, 1:42pm

để xem đã… có khi thần thánh viết thì compile dịch khác với người thường

N của em là kích thước bàn cờ mà. Còn số 0->7 là những cách đi của mã lỗi tùy biến chương trình thế này thì không được nè

nhatlonggunz · April 7, 2015, 1:44pm

Cám ơn mọi người đã giúp em, em đã xử lý xong bài này rồi (8 x 8 ô).

Tình hình là nằm ở chỗ cái mảng, sắp xếp bước đi thế nào. Em cóp cái mảng của ổng về là run được. Theo em là mảng của ổng đã sắp xếp các bước đi hợp lý bằng cách này:

Nhưng do đang học Backtrack cơ bản nên ổng lược bớt

Gio · April 7, 2015, 2:04pm

Khác nhau có lẽ là cách xếp thứ tự của xMove với yMove, nếu sắp theo 1 thứ tự nào đó(thường là theo vòng tròn) thì sẽ ra kq nhanh hơn

Rok_Hoang · April 7, 2015, 2:07pm

Các bài toán này đều là cố định nên khác nhau có lẽ là cách chọn bước đi thôi

nguyenhuuca · April 11, 2015, 4:15am

Mình có làm bài này nhưng băng winform C#. nếu không yêu cầu in ra tất cả các đường đi từ vị trí ban đầu thì có thể áp dụng Heuristic để giải:Đi vào nước mà tại đó khả năng đi tiếp của quân Mã là nhỏ nhất.
Có cần soucre thảm khảo không?

nhatlonggunz · April 11, 2015, 7:30am

Dạ nếu được thì anh post code giùm ạ, cám ơn anh.

nguyenhuuca · April 11, 2015, 7:43am

link tải đây(vs2010): https://sites.google.com/site/canhhoanh/files/MaDiTuan.zip?attredirects=0&d=1

Worst_Players · November 25, 2018, 4:30am

bạn ơi có thỉ chỉ mình hướng tìm tất cả đường đi của quân mã khi nhập vào vị trí ban đầu ko c++

nguyenhuuca · November 25, 2018, 4:42am

4 năm rồi cơ ah @@

Worst_Players · November 28, 2018, 6:13am

Bạn ơi có thể hướng dẫn mình khử cái để quy trong bài đc ko vì mình có bài tập về mã đi tuần chỉ dùng stack. Mong bạn chỉ giúp

Thuc_Nguyen_tan · November 28, 2018, 7:07am

Xem bài này có giúp gì cho bạn không?

Worst_Players · November 28, 2018, 5:05pm

mình mới học c++ bạn ơi nên chưa biết gì nhiều hướng dẫn mình làm để hiểu đi. Làm sao để dùng stack trong bài mã đi tuần đó z

Thuc_Nguyen_tan · November 29, 2018, 12:32am

Bài toán mã đi tuần là bài toán khó, theo kinh nghiệm mình bạn nên chia thành nhiều cấp độ
ví dụ:
cho nó chày phài
cho nó chạy trái
…
cho nó chạy đúng hình chữ nhật
…
Làm từ từ mới hấp dẫn, cái đemo của mình chưa check các vị trí đã đi qua chỉ cho nó chạy ram dom thôi

Còn vấn đề khử đệ qui thì bạn làm theo cách kinh điển như sau

Bạn xem cái link này, nghiên cứu họ đệ qui sao, rồi họ khử thế nào

http://blogitnlu.azurewebsites.net/blogerIT/laptrinh/ltdt/DFS.jsp

hope usefull to you

Worst_Players · December 1, 2018, 11:05am

    #include <iostream>
    #include <stdio.h>
    #include <conio.h>
    using namespace std;
    #define N 5
    #define STMAX N*N

    //Định nghĩa cấu trúc cho 1 STACK
    struct STACK {
	int a[STMAX];		//Mảng các phần tử của ngăn xếp
	int top;		//Chỉ số phần tử đỉnh đầu của ngăn xếp
    };
   
    // Kiểu miêu tả thông tin của 1 bước đi 
    //Các biến toàn cục được sử dụng
    int board[N][N];			//Bảng 6x6
    int x, y, newx, newy, move_number, move_type, dem, n;

  
    int main()
    {
	STACK Horse;
	cout << "Nhap kich thuoc ban co:";
	
	InitBoard(n);
	InitStack(Horse);
	cout << "Nhap toa do diem bat dau (x, y): ";
	cin >> x >> y;
			board[x][y] = 1;		//Điểm bắt đầu
			move_number = 2;		//điểm đi tiếp theo
			
				do {

					find_move(Horse, move_type);
					Push(Horse, move_type);
					x = newx;
					y = newy;
					move_type = 0;
					board[x][y] = move_number++;
					if (move_number > N*N) {
						Show();
					}
				} while (move_number <= N * N );
			
			
			return 0;	
    }
    //1. Tạo ngăn xếp rỗng
    void InitStack(STACK& myStack) {
	myStack.top = 1;
    }
    //2. Kiểm tra ngăn xếp rỗng
    int IsEmptyStack(STACK& myStack) {
	if (myStack.top == -1) return 1;	//Ngăn xếp rỗng
	return 0;							//Ngăn xếp không rỗng
    }
    //3. Kiểm tra ngăn xếp đầy hay không?
    int IsFullStack(STACK& myStack) {
	if (myStack.top == STMAX - 1) return 1;	//Ngăn xếp đầy
	return 0;								//Ngăn xếp chưa đầy
    }
    //4. Thêm 1 phần tử vào ngăn xếp
    void Push(STACK& myStack, int x) {
	if (IsEmptyStack(myStack)) cout << "Ngan xep day";
	else
	{
		myStack.a[myStack.top + 1] = x;
		myStack.top++;
	}
    }
     //5. Lấy thông tin phần tử ở đỉnh ngăn xếp
    int Top(STACK myStack) {
	return myStack.a[myStack.top];
    }
    //6. Trích hủy phần tử ở đỉnh ngăn xếp
    int Pop(STACK& myStack) {
	int t = myStack.a[myStack.top];
	myStack.top--;
	return t;
}
    //7. Khởi tạo bàn cờ
    void InitBoard(int n)							//kích thước NxN
    {
	for (int i = 0; i<n; i++)
		for (int j = 0; j<n; j++)
			board[i][j] = 0;
    }

    //9. Kiểm tra xem có đi được hay ko
    int move_valid()
    {
	return ((newx >= 0) && (newx < N) &&
		(newy >= 0) && (newy < N) &&
		(board[newx][newy] == 0));
    }
    //10. 8 trường hợp đi của quân mã
    void try_move(int mt)		
    {
	switch (mt) {
	case 1:
		newx = x + 1;
		newy = y + 2;
		break;
	case 2:
		newx = x + 2;
		newy = y + 1;
		break;
	case 3:
		newx = x + 2;
		newy = y - 1;
		break;
	case 4:
		newx = x + 1;
		newy = y - 2;
		break;
	case 5:
		newx = x - 1;
		newy = y - 2;
		break;
	case 6:
		newx = x - 2;
		newy = y - 1;
		break;
	case 7:
		newx = x - 2;
		newy = y + 1;
		break;
	case 8:
		newx = x - 1;
		newy = y + 2;
		break;
	default:
		cout << "Ko ton tai nuoc di thoa man yeu cau";
		exit(1);
	}
    }
     //11.Truy xuất nước đi
    void retract_move(STACK& myStack)
    {
	int mtype;
	if (!IsEmptyStack(myStack))		 //Kiểm tra stack rỗng
		move_type = Pop(myStack);	// Nếu ko thì lấy nước đi ra khỏi stack	
	board[x][y] = 0;				//gán lại vị trí bắt đầu
	mtype = (move_type + 4) % 8;		// gán lại bước đi mới
	if (mtype == 0)						// kiểm tra bước đi mới
		mtype = 8;
	try_move(mtype);					// Thử bước đi
	x = newx;							// gán lại vị trí mới
	y = newy;
	move_number--;						// lùi lại số nước đi
    }
    //12. Tìm nước đi của quân mã
    void find_move(STACK& myStack, int& move_type)
    {
	do {
		while (move_type == 8) //Nếu đã đi hết nước đi
		{
			retract_move(myStack);		//Quay lui
		}
		move_type++;					
		try_move(move_type);			//kiểm tra trường hợp khác để đi tiếp	
	} while (!move_valid());			
     }

     //8. In kết quả con mã đi trên bàn cờ 
     void Show() {
	int h, c;
	
	printf("Cach di thu : %d\n", ++dem);
	for (h = 0; h < N; h++) {
		// Hiển thị hàng lưới ngang bàn cờ 
		for (c = 0; c < N; c++) printf("+----");
		printf("+\n");
		// Hiển thị nội dung hàng thứ h bàn cờ 
		for (c = 0; c < N; c++)
			printf("| %2d ", board[h][c]);
		printf("|\n");
	}
	// Hiển thị hàng lưới ngang bàn cờ cuối cùng
	for (c = 0; c < N; c++) printf("+----");
	printf("+\n");
     }

Em mới code bài mã đi tuần ngăn xếp này nhưng chỉ mới làm phần in ra 1 đáp án. Ai có thể chỉ em in ra nhiều đáp án từ 1 vị trí bắt đầu ko ạ, mong mọi người giúp đỡ, em tìm mãi trên mạng toàn đệ quy ko có ngăn xếp để tham khảo.

ddt · April 28, 2020, 3:13am

Chào anh,
Em xin phép tham khảo bài “báo cáo mã đi tuần” của anh cho báo cáo đồ án môn của em ạ.
em cảm ơn anh nhiều