Program enters Infinite Loop - Problem "Horse Ride" in C

Question

The problem of the horse consists of which, the horse is placed on the board emptiness and, following the rules of the game, need to go through all the houses exactly once in consecutive moves. ie given a board of size n, and the starting position of the Startx horse, Starty. the algorithm should show on the screen an Nxn size matrix informing on which movement the horse passed in their homes. if given the starting position and the horse does not find a way to walk through all the houses 1 single sees then shows on the train that the problem has no solution.

My program when typing values greater than 8 for the board or 8x8, and if the horse position is different from 1 for the row or column the program simply enters Infinite Loop, I don’t know why. follow the code written in C

#include<stdio.h>
#define MAX 10

void imprimir(int n, int M[MAX][MAX]) 
{
    int x, y;
    for (x = 0; x < n; x++) {
        for (y = 0; y < n; y++)
            printf(" %3d ", M[x][y]);
        printf("\n");
    }   
}

int passeio(int n, int x, int y, int pos, int M[MAX][MAX], int xMove[], int yMove[]) 
{
    int k, nextX, nextY;
    if (pos == n*n) return 1;
    for (k = 0; k < 8; k++) {
        nextX = x + xMove[k];
        nextY = y + yMove[k];

        if ((nextX >= 0) && (nextX < n) && (nextY >= 0) && (nextY < n) &&
            (M[nextX][nextY] == 0)) {
            M[nextX][nextY] = pos + 1;
        if (passeio(n, nextX, nextY, pos + 1, M, xMove, yMove))
            return 1;
        else
            M[nextX][nextY] = 0; /* libera a posicao do tabuleiro */
        }
    }
    return 0;
}

int main() 
{
    int M[MAX][MAX], x, y, n, startX, startY;
    int xMove[8] = {2, 1, -1, -2, -2, -1,  1,  2};
    int yMove[8] = {1, 2,  2,  1, -1, -2, -2, -1};
    printf("Entre com o tamanho do tabuleiro: ");
    scanf("%d", &n);
    printf("Entre com a linha inicial do cavalo: ");
    scanf("%d", &startX);
    printf("Entre com a coluna inicial do cavalo: ");
    scanf("%d", &startY);
    for (x = 0; x < n; x++)
        for (y = 0; y < n; y++)
            M[x][y] = 0;
        M[startX - 1][startY - 1] = 1;
        if (passeio(n, startX - 1, startY - 1, 1, M, xMove, yMove) == 0)
            printf("Nao existe solucao.\n");
        else
            imprimir(n, M);
        return 0;
}