Is this code to find path into square grid using backtracking is right?

Question

I was reading antti lakesonen's competitive programming handbook and I came across backtracking for finding grid paths with some optimizations applied. In nutshell here are the rules for a valid path across the grid :

0. Path search starts from top left cell and ends at bottom right cell.
1. A valid path has traversed all the cells of the grid once.
2. From current cell you can move right, left, top, bottom and only if the move doesn't leave the grid.

Now I have written this code that works fine with square grid of dimension = 7 with time taken ~400ms and total paths : 111712. I have two queries here :

--> With dimension = 9 its taking like a lot of time to report even the first valid path in its search. Am I stuck into the infinite loop or what?

--> Grid path search for even number of dimension like 2,4,6 are giving answer 0. I tried with finding path for 2*2 and 4*4 grid manually but I see that it's impossible to find such paths, but i don't know how to formally or logically prove that even dimensions square grids cannot have such paths mentioned above.

Here is my code :

#include <bits/stdc++.h>

using namespace std;

#define LOG_PATH 1;
#define ARRAY_BASED_CONSTANT_GRID 1;

struct Cell {
    int x,y;
};

const int HORIZONTAL_DIRECTION = 0, VERTICAL_DIRECTION = 1;

long long validPathCount, recursiveCallCount, visitedCellCount, currentDirection;

#ifdef ARRAY_BASED_CONSTANT_GRID
    const int DIMENSION = 7;
    bool grid[DIMENSION][DIMENSION];
#else
    int DIMENSION;
    vector<vector<bool>> grid;
#endif



/* *-*-*-*-*-*-*-*- UTILITY FUNCTIONS -*-*-*-*-*-*-*-*-*-*-*-*-*-* */
bool hasPathCompleted(Cell);
bool isPathValid();
void validPathCheckAndUpdate();

void setState(Cell);
void resetState(Cell);

void updateAndLogPathCounter();
void backtrackPathSearching(Cell);
void moveAlongTheGrid(Cell);
bool isOccupied(Cell);

bool canMoveRight(Cell);
bool canMoveLeft(Cell);
bool canMoveUp(Cell);
bool canMoveDown(Cell);

bool isRightBorder(Cell);
bool isLeftBorder(Cell);
bool isUpBorder(Cell);
bool isDownBorder(Cell);

Cell generateRight(Cell);
Cell generateLeft(Cell);
Cell generateUp(Cell);
Cell generateDown(Cell);

bool isThereHorizontalPartition();
bool isThereVerticalPartition();

void printGrid();
/* *-*-*-*-*-*-*-*- UTILITY FUNCTIONS -*-*-*-*-*-*-*-*-*-*-*-*-*-* */

Cell generateRight(Cell position) { 
    currentDirection = HORIZONTAL_DIRECTION;
    return {position.x, position.y + 1};
}
Cell generateLeft(Cell position) { 
    currentDirection = HORIZONTAL_DIRECTION;
    return {position.x, position.y - 1};
}
Cell generateUp(Cell position) { 
    currentDirection = VERTICAL_DIRECTION;
    return {position.x - 1, position.y};
}
Cell generateDown(Cell position) { 
    currentDirection = VERTICAL_DIRECTION;
    return {position.x + 1, position.y};
}

bool isRightBorder(Cell position) { return position.y == DIMENSION - 1; }
bool isLeftBorder(Cell position) { return position.y == 0; }
bool isUpBorder(Cell position) { return position.x == 0; }
bool isDownBorder(Cell position) { return position.x == DIMENSION - 1; }

bool isOccupied(Cell position) { return grid[position.x][position.y]; }

bool canMoveRight(Cell position) { return !isRightBorder(position) && !isOccupied(generateRight(position)); }
bool canMoveLeft(Cell position) { return !isLeftBorder(position) && !isOccupied(generateLeft(position)); }
bool canMoveUp(Cell position) { return !isUpBorder(position) && !isOccupied(generateUp(position)); }
bool canMoveDown(Cell position) { return !isDownBorder(position) && !isOccupied(generateDown(position)); }

bool hasPathCompleted(Cell position) { return position.x == DIMENSION - 1 && position.y == DIMENSION - 1; }

bool isPathValid() { return visitedCellCount == DIMENSION * DIMENSION; }

void validPathCheckAndUpdate() {
    if (isPathValid()) { updateAndLogPathCounter(); }
}

void updateAndLogPathCounter() {
    validPathCount++;
    #ifdef LOG_PATH
    cout << "\rFound " << validPathCount << " paths";
    cout.flush();
    #endif
}

void setState(Cell position) {
    recursiveCallCount++;
    visitedCellCount++;
    grid[position.x][position.y] = true;
}

void resetState(Cell position) {
    visitedCellCount--;
    grid[position.x][position.y] = false;
}

void printGrid() {
    cout << "-------------------------------" << endl;
    for (int i = 0; i < DIMENSION; i++) {
        for (int j = 0; j < DIMENSION; j++) {
            cout << grid[i][j] << " ";
        }
        cout << endl;
    }
}

void moveAlongTheGrid(Cell position) {
    if (canMoveRight(position)) {
        backtrackPathSearching(generateRight(position));
    }

    if (canMoveLeft(position)) {
        backtrackPathSearching(generateLeft(position));
    }

    if (canMoveUp(position)) {
        backtrackPathSearching(generateUp(position));
    }

    if (canMoveDown(position)) {
        backtrackPathSearching(generateDown(position));
    }
}

bool isThereHorizontalPartition(Cell position) {
    if (currentDirection == VERTICAL_DIRECTION) {
        if (!canMoveUp(position) && !canMoveDown(position)) {
            if (canMoveLeft(position) && canMoveRight(position)) {
                return true;
            }
        }
    }
    return false;
}

bool isThereVerticalPartition(Cell position) {
    if (currentDirection == HORIZONTAL_DIRECTION) {
        if (!canMoveLeft(position) && !canMoveRight(position)) {
            if (canMoveUp(position) && canMoveDown(position)) {
                return true;
            }
        }
    }
    return false;
}

// OPTIMIZATION : 4 > Direction awareness
// Optimization 3 followed border awareness but this concept can be generalized 
// and we can make the grid aware of its direction
// If path can't go forward in current direction but either can turn into both cross axis path
// then there is partition
void backtrackPathSearching(Cell position) {    
    setState(position);

    // printGrid();
    // cout << "x : " << position.x << " y : " << position.y << endl;
    // cout << "validPathCount : " << validPathCount << endl;
    // string s;
    // getline(cin, s);

    if (hasPathCompleted(position)) {
        validPathCheckAndUpdate();
    }
    else if (!isThereHorizontalPartition(position) && !isThereVerticalPartition(position)) {
        moveAlongTheGrid(position);
    }

    resetState(position);
}

#ifndef ARRAY_BASED_CONSTANT_GRID
    void inputFromUser() {
        cout << "Give Dimension of box grid : ";
        cin >> DIMENSION;

        for (int i = 0; i < DIMENSION; i++) grid.push_back(vector<bool>(DIMENSION, false));
    }
#endif

int main() {
    #ifndef ARRAY_BASED_CONSTANT_GRID
        inputFromUser();
    #endif

    validPathCount = recursiveCallCount = 0;
    visitedCellCount = 1;
    grid[0][0] = 1;
    currentDirection = VERTICAL_DIRECTION;

    backtrackPathSearching({1, 0});

    cout << endl;
    cout << "Paths : " << validPathCount * 2 << endl;
    cout << "Calls : " << recursiveCallCount << endl;
    return 0;
}

/*
Paths : 111712
Calls : 26790463

real    0m0.281s
user    0m0.281s
sys 0m0.000s
*/

Just comment ARRAY_BASED_CONSTANT_GRID to enable user input for grid dimension.

Can someone help me with this? Thanks in advance :)

PS: Due to my coding practices I had to paste the whole code in order to make it sensible. I know in stackoverflow only minimal required code has to be pasted but here I don't know what's really needed in order to analyze the code!