I'm trying to make the knight tour problem, return the maximum number of moves possible, (when n = 3 will be 8) instead of just 1 for when it's possible and 0 when there's no solution.

My return is always coming back to zero.

It looks like I have to change the base case because my recursion goes back to the beginning where the plays parameter is equal to 0.

Can someone help me??

#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(" - ", 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 %d\n" , 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();    
}

CodePudding user response：

The first problem is that your condition on backtracking isn't updated for the new algorithm : if (solveKTUtil(next_x, next_y, movei 1, sol, xMove, yMove, plays) == 1) is true only if the recursion returned exactly 1. You want to change that to > 0

The second problem, is that you don't return the maximum number of moves possibles : the variable play count the number of moves you tested for a particular step, that's totally different.

What you want to return at step movei is:

• if no movement is valid, return 0
• if a recursive call return N*N directly return that (it's not possible to do better)
• else keep the maximum return value of the recursive calls, and return the max between that value and movei

CodePudding user response：

This apparently solved the problem I removed the if, start the play variable at 1 and did a count on the recursive calls

#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(" - ", 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 %d\n" , 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();    
    }