I was recently assigned the knight's tour problem.
Here is my try at it:

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int count = 1;
int movej[8] = {1, -1,-2, 2, -2, -1,  1,  2};
int movei[8] = {2,  2,  1,  1, -1, -2, -2, -1};

void boardprinter(int **board)
{
    for (int i = 0; i < 8; i  )
    {
        for (int j = 0; j < 8; j  )
        {
            printf("%d ", board[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}
_Bool safe(int **board, int i, int j)
{
    if ((board[i][j] == (-1)) && i >= 0 && i < 8 && j >= 0 && j < 8)
    {
        return 1;
    }
    return 0;
}
_Bool solve(int **board, int si, int sj)
{
    if (count == 64)
    {
        boardprinter(board);
        return 1;
    }
    int i=0;
    while(i<8)
    {  
        if (safe(board, (si   movei[i]), (sj   movej[i])))
        {
            board[si   movei[i]][sj   movej[i]] = count  ;
            if (solve(board, (si   movei[i]), (sj   movej[i])))
            {   
                return 1;
            }
            else
            {   
                board[si   movei[i]][sj   movej[i]] = -1;
            }
        }
        i  ;
    }
    return 0;
}
int main()
{
    int **board = (int **)malloc(8 * sizeof(int *));
    for (int i = 0; i < 8; i  )
    {
        *(board   i) = (int *)malloc(8 * sizeof(int));
        for (int j = 0; j < 8; j  )
        {
            board[i][j] = -1;
        }
    }
    // board initiallized
    int si, sj;
    scanf("%d %d", &si, &sj);
    board[si][sj] = 1;
    count  ;
    _Bool c = solve(board, si, sj);
    printf("%d",c);
    return 0;
}

I applied recursion and backtracking in this but the code crashes after reaching (4,2),now I think this fails because the while loop doesn't seem to behave properly (it gets teminated somehow)
But I dont know why.. I have been stuck over this and tried all sorts of things to debug this Kindly help me out!!

CodePudding user response：

Thanks to Mr Tom Karzes for pointing out the mistakes in my code.

Cause of Error

The Problem with my code was that I was indexing into my array before checking if it was out of bounds,i.e. This happened because I assumed that the condition :
(board[i][j] == (-1)) && i >= 0 && i < 8 && j >= 0 && j < 8 would automatically fail if the array was out of bounds, but it turns out that I forgot that the compiler first checks (board[i][j] == (-1)) before checking the next mentioned conditions,Which was the cause of the undefined behavior of my program.

Fixed Code

Here is the fixed code:

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int count = 0;
int movej[8] = {1, -1,-2, 2, -2, -1,  1,  2};
int movei[8] = {2,  2,  1,  1, -1, -2, -2, -1};

void boardprinter(int **board)
{
    for (int i = 0; i < 8; i  )
    {
        for (int j = 0; j < 8; j  )
        {
            printf("%d ", board[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}
_Bool safe(int **board, int i, int j)
{
    if (i >= 0 && i < 8 && j >= 0 && j < 8)
    {
        if((board[i][j] == (-1)))
        {
            return 1;
        }
    }
    return 0;
}
_Bool solve(int **board, int si, int sj)
{
    if (count == 64)
    {
        boardprinter(board);
        return 1;
    }
    int i=0;
    while(i<8)
    {  
        if (safe(board, (si   movei[i]), (sj   movej[i])))
        {
            board[si   movei[i]][sj   movej[i]] = count  ;
            if (solve(board, (si   movei[i]), (sj   movej[i])))
            {   
                return 1;
            }
            else
            {   
                board[si   movei[i]][sj   movej[i]] = -1;
                count--;
            }
        }
        i  ;
    }
    return 0;
}
int main()
{
    int **board = (int **)malloc(8 * sizeof(int *));
    for (int i = 0; i < 8; i  )
    {
        board[i] = (int *)malloc(8 * sizeof(int));
        for (int j = 0; j < 8; j  )
        {
            board[i][j] = -1;
        }
    }
    // board initiallized
    int si, sj;
    scanf("%d %d", &si, &sj);
    board[si][sj] = 0;
    count  ;
    _Bool c = solve(board, si, sj);
    printf("%d",c);
    return 0;
}