c-knight tour算法返回最大试验次数(回溯)

Question

我试图解决骑士之旅的问题，返回最大可能的移动次数(当n=3为8时(，而不是只有1表示可能，0表示没有解决方案。

我的回报总是归零。

看起来我必须更改基本情况，因为我的递归返回到plays参数等于0的开头。

有人能帮我吗？？

#include <stdio.h>
#define N 3

int solveKTUtil(int x, int y, int movei, int sol[N][N], int xMove[], int yMove[], int numJog);

int isSafe(int x, int y, int sol[N][N])
{
return (x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1);
}

void printSolution(int sol[N][N])
{
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++)
printf(" %2d ", sol[x][y]);
printf("n");
}
}

void 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;

sol[0][0] = 0; // Since the Knight is initially at the first block

/* xMove[] and yMove[] define next move of Knight. */
int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

/* Start from 0,0 and explore all tours using solveKTUtil() */
printf("Numbers of Attempts %dn" , solveKTUtil(0, 0, 1, sol, xMove, yMove, 0));
printSolution(sol);            

}

/* 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 plays)
{
int play = 0;
if (movei == N * N) 
return 1;

for (int k = 0; k < 8; k++) {
int next_x = x + xMove[k];
int next_y = y + yMove[k];
if (isSafe(next_x, next_y, sol)) 
{
plays = plays +1;
printf("%d", plays);
printf("n");
play = plays + 1;
sol[next_x][next_y] = movei;
if (solveKTUtil(next_x, next_y, movei + 1, sol, xMove, yMove, plays) == 1)
return play;
else
sol[next_x][next_y] = -1; // backtracking
}
}

// return 0;
}

void main()
{
solveKT();    
}

Answer 1

第一个问题是您的回溯条件没有为新算法更新：if (solveKTUtil(next_x, next_y, movei + 1, sol, xMove, yMove, plays) == 1)仅当递归返回的值恰好为1时为true。您想将其更改为> 0

第二个问题是，你没有返回可能的最大移动次数：变量play计算你为特定步骤测试的移动次数，这完全不同。

您想在步骤movei返回的是：

• 如果没有移动有效，则返回0
• 如果递归调用直接返回N*N(这是不可能做得更好的(
• 否则保留递归调用的最大返回值，并返回该值与movei之间的最大值

Answer 2

这显然解决了问题，我删除了if，在1开始播放变量，并对递归调用进行了计数

#include <stdio.h>
#define N 3

int solveKTUtil(int x, int y, int movei, int sol[N][N], int xMove[], int yMove[], int numJog);

int isSafe(int x, int y, int sol[N][N])
{
return (x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1);
}

void printSolution(int sol[N][N])
{
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++)
printf(" %2d ", sol[x][y]);
printf("n");
}
}

void 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;

sol[0][0] = 0; // Since the Knight is initially at the first block

/* xMove[] and yMove[] define next move of Knight. */
int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

/* Start from 0,0 and explore all tours using solveKTUtil() */
printf("Numbers of Attempts %dn" , solveKTUtil(0, 0, 1, sol, xMove, yMove, 0));
printSolution(sol);            

}

/* 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 plays)
{
int play = 1;
if (movei == N * N) 
return movei;

for (int k = 0; k < 8; k++) {
int next_x = x + xMove[k];
int next_y = y + yMove[k];
if (isSafe(next_x, next_y, sol)) 
{

sol[next_x][next_y] = movei;
play = solveKTUtil(next_x, next_y, movei + 1, sol, xMove, yMove, plays + 1) + 1;
sol[next_x][next_y] = -1; // backtracking

}
}

return play;
}

void main()
{
solveKT();    
}