Update:
Lý do code trên geeks chạy nhanh hơn do heuristic như @Itachi_Citus nói
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ùngbooltrong khi em thấy rằng nếu dùngvoidthì 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;
}
.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?