30/09/2018, 16:48

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

Em đang làm bài The Knight’s tour problem (thuật quay lui cơ bản): Cho một con mã (Knight) trong bàn cờ vua (8 x 8), đi theo luật cờ vua (nôm na là 1 bước thẳng rồi 1 bước chéo). Hãy tìm và in ra đường đi của quân mã (Knight) ấy sao cho nó đi hết cả bàn cờ mà không đi qua ô đã đi qua trước đó.

Trên http://www.geeksforgeeks.org/backtracking-set-1-the-knights-tour-problem/ thì người ta code thế này (ghi ra cho ai lười vào link)

bool solveKT()
{
    int sol[N][N];
 
    /* Initialization of solution matrix */
    for (int x = 0; x < N; x++)
        for (int y = 0; y < N; y++)
            sol[x][y] = -1;
 
    /* xMove[] and yMove[] define next move of Knight.
       xMove[] is for next value of x coordinate
       yMove[] is for next value of y coordinate */
    int xMove[8] = {  2, 1, -1, -2, -2, -1,  1,  2 };
    int yMove[8] = {  1, 2,  2,  1, -1, -2, -2, -1 };
 
    // Since the Knight is initially at the first block
    sol[0][0]  = 0;
 
    /* Start from 0,0 and explore all tours using solveKTUtil() */
    if(solveKTUtil(0, 0, 1, sol, xMove, yMove) == false)
    {
        printf("Solution does not exist");
        return false;
    }
    else
        printSolution(sol);
 
    return true;
}
 
/* A recursive utility function to solve Knight Tour problem */
int solveKTUtil(int x, int y, int movei, int sol[N][N], int xMove[N],
                int yMove[N])
{
   int k, next_x, next_y;
   if (movei == N*N)
       return true;
 
   /* Try all next moves from the current coordinate x, y */
   for (k = 0; k < 8; k++)
   {
       next_x = x + xMove[k];
       next_y = y + yMove[k];
       if (isSafe(next_x, next_y, sol)) // Kiểm tra xem bước tiếp theo có nằm trong bàn cờ hay không (x, y >= 0 và < N)
       {
         sol[next_x][next_y] = movei;
         if (solveKTUtil(next_x, next_y, movei+1, sol, xMove, yMove) == true)
             return true;
         else
             sol[next_x][next_y] = -1;// backtracking
       }
   }
 
   return false;
}

Em có 2 câu hỏi:

Trong hàm solveKT, tại sao phải dùng bool trong khi em thấy rằng nếu dùng void thì có lẽ vẫn sẽ làm y như vậy ?
Em chế biến nó một chút, thành như vầy, thế nhưng nó lại không in ra gì (hoặc có lẽ là run quá lâu), em sai cái gì, mọi người giúp với

Update, Em đã sửa code lại giống ông đó, em thấy code em đâu khác chỗ nào đâu, sao lại chạy không được nhỉ @Gio

Update lần nữa @Gio

#include <iostream>
#include <conio.h>
#include <stdio.h>
using namespace std;
#define N 8



void OutputArr(int A[N][N])
{

	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			cout << A[i][j] << " ";
		}
		cout << endl;
	}
}

// Check if the move is available
int isSafe(int x, int y, int A[N][N])
{
	if(x >= 0 &&
	   y >= 0 &&
	   x < N &&
	   y < N &&
	   A[x][y] == -1) // If the square is still not visited
		return 1;
	return 0;
}

int BackTrack(int sol[N][N], int xMove[N], int yMove[N], int x, int y,
	int Move)
{
	int k, next_x, next_y;
	if(Move == N * N){
		return true;
	}

	// Try all next moves
	for(k = 0; k < N; k++){
		next_x = x + xMove[k];
		next_y = y + yMove[k];
		if(isSafe(next_x, next_y, sol)){
			sol[next_x][next_y] = Move;
			if(BackTrack(sol, xMove, yMove, next_x, next_y, Move + 1) == true){
				return true;
			}
			else // Backtrack, mark that the path is fail
				sol[next_x][next_y] = -1;
		}
	}
	return false;
}

bool Solve()
{
	int sol[N][N];

	// Set up the "board"
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			sol[i][j] = -1;
		}
	}

	// Square that the Knight can move to
	int xMove[8] = {2, -2, -1, 1, -2,  2,  1, -1};
	int yMove[8] = {1,  1,  2, 2, -1, -1, -2, -2};

	// Where the knight starts
	sol[0][0] = 0;

	if(BackTrack(sol, xMove, yMove, 0, 0, 1) == false){
		cout << "No solution." << endl;
		return false;
	}
	else{
		OutputArr(sol);
	}
	return true;
}

int main()
{
	Solve();
    getchar();
	return 0;
}

Nguyễn Minh Dũng viết 18:52 ngày 30/09/2018

Bài này hay này, vào nghiên cứu thử đi mọi người.

Itachi Citus viết 19:00 ngày 30/09/2018

Trong hàm solveKT, tại sao phải dùng bool trong khi em thấy rằng nếu dùng void thì có lẽ vẫn sẽ làm y như vậy ?

Thực tế thì người ta luôn tránh xây dựng các hàm void, hay hàm thực hiện mà không có thông báo gì cho hàm gọi nó. Khi xây dựng một hàm thực hiện một công việc nào đó nên trả về kết quả để hàm gọi nó có thể kiểm soát được những gì đã xảy ra.

Hồi trước mình cũng làm bài này chạy rất lâu, bạn chỉ nên nhập bàn cờ nhỏ hơn 6 * 6 thôi .

nhatlonggunz viết 19:04 ngày 30/09/2018

Thế mà code bên geeks, em chép vào, chạy phát ra luôn ấy (8 x 8) :’( còn em thì đảo lại trật tự chút (thử xem tại sao ổng làm như thế này mà không làm thế kia) thì … tuy code giống 90% nhưng em lại không có output (em nghĩ là do chạy lâu chứ không phải là không ra)

Gió viết 19:01 ngày 30/09/2018

Cái này thực ra là thuật toán duyệt đồ thị hamilton.
Code làm thay đổi thuật toán thì có kết quả khác thôi

Itachi Citus viết 18:57 ngày 30/09/2018

Có một heuristic nhỏ là trong các bước tiếp theo có thể đi được, bạn lựa chọn bước gần với góc nhất (Tính khoảng cách đến 4 góc, lấy min(min())), nó sẽ ra rất nhanh nếu tồn tại lời giải.

nhatlonggunz viết 18:50 ngày 30/09/2018

Anh có thể nói rõ hơn phần

Tính khoảng cách đến 4 góc

Không ạ

Itachi Citus viết 18:53 ngày 30/09/2018

Bạn tính khoảng cách euclid hoặc manhattan rồi chọn khoảng cách đến góc gần nhất ý, chẳng hạn ô (0, 0) khoảng cách đến góc bằng 0, ô (0, 1) khoảng cách đến góc bằng 1, ô (1, 1) khoảng cách đến góc bằng 2 (manhattan) hoặc sqrt(2) (euclid). Ô (7, 7) với bàn cờ 8X8 khoảng cách đến góc = 0.

nhatlonggunz viết 18:59 ngày 30/09/2018

Cám ơn anh nhiều, em sẽ thử cái này.

P/s: Em chẳng biết gì về khoảng cách Euclid với Manhattan cả. Em chỉ biết, Euclid là nhà toán học còn Manhattan là một thành phố (hay là bang nhỉ) bên Mỹ

nhatlonggunz viết 19:03 ngày 30/09/2018

Mà cho em hỏi, trong hàm solveKTUtil của tác giả, tại sao hàm int mà trong đó lại return true với false ?

Nguyễn Minh Dũng viết 18:56 ngày 30/09/2018

tại sao hàm int mà trong đó lại return true với false ?

Tại vì true tương đương với 1, false tương đương với 0 nếu gán cho một số int. Thế nên không có vấn đề gì với việc này cả.

Gió viết 18:56 ngày 30/09/2018

Post code hoàn thiện lên xem

Minh Hoàng viết 18:49 ngày 30/09/2018

#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 viết 18:50 ngày 30/09/2018

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 viết 19:01 ngày 30/09/2018

[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

Minh Hoàng viết 18:56 ngày 30/09/2018

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 viết 19:04 ngày 30/09/2018

để 8 ô, mã nhảy không nổi

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

Ideone.com

Ideone is something more than a pastebin; it's an online compiler and debugging tool which allows to compile and run code online in more than 40 programming languages.

Còn code em:

Ideone.com

Ideone is something more than a pastebin; it's an online compiler and debugging tool which allows to compile and run code online in more than 40 programming languages.

Try all next move nhé k<8 không phải N

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

Minh Hoàng viết 18:49 ngày 30/09/2018

Thế mà code của ông tác giả (code đầu tiên ấy), run phát là ra (cũng 8 ô):http://ideone.com/A7Rt2BCòn code em:http://ideone.com/sXhZAQ

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

Em #define N 8 rồi anh

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 viết 18:55 ngày 30/09/2018

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: