Backtracking task got TRAGIC

Question

I was solving this task:

Let us consider the problem of calculating the number of paths in an n × n grid from the upper-left corner to the lower-right corner such that the path visits each square exactly once.

And for some reason my code isn't working properly, it should output 2 when the grid is 3 by 3, but for some reason it doesn't get to the last square and just stops with the output of 1.

#include <iostream>
#include <vector>
using namespace std;

long ans = 0;
const int n = 3;
int num = 3 * 3;
bool grid[n][n];

void search(int x, int y, int checked) {
    grid[x][y] = true;
    cout << "Searching in " << x << " " << y << " in " << checked << "\n";

    if (checked == num) {
        cout << "in IF!\n";
        if (x == n - 1 && y == n - 1){
            ans++;
            cout << "ans++!\n";
        }
        return;
    }   
    else {
        //Left
        if (x > 0 && !grid[x - 1][y]) {
            checked++;
            search(x - 1, y, checked);
            checked--;
        }

        //Right
        if (x < n - 1 && !grid[x + 1][y]) {
            checked++;
            search(x + 1, y, checked);
            checked--;
        }

        //Up
        if (y != 0 && !grid[x][y - 1]) {
            checked++;
            search(x, y - 1, checked);
            checked--;
        }

        //Down
        if (y != n - 1 && !grid[x][y + 1]) {
            checked++;
            search(x, y + 1, checked);
            checked--;
        }
    }
    grid[x][y] = false;
    return;

}

int main() {
    search(0, 0, 1);
    cout << ans;
    return 0;
}

Tried everything and no results.

Answer 1

Be careful when creating multiple paths through your code that they all perform all of the required actions.

When you find the end square you return without resetting grid[x][y] to false. Removing this return makes your code generate your expected result: https://godbolt.org/z/873jhG668

It's probably overkill in this scenario but in general you can avoid this in C++ with the RAII pattern.