Backtracking not working on a Hitori matrix

Question

It seems the code I wrote doesn't backtrack properly and i have no idea where the backtracking goes wrong.

Hitori is an "reverse" Sudoku. You are given a matrix filled with numbers and have to eliminate certain ones with these rules:

• the number in a cell cannot be found anywhere else on its respective row and column (no duplicates)
• final matrix has to be whole (no "islands" - isolated cells) - this part i'm checking with a DFS
• i can't eliminate a cell which is adjacent to an eliminated cell.

BTW, I am not looking for efficiency for this hitori solver using backtracking. I just want to get a general grip of this. For some cases this works, but for the example given i still have duplicate numbers left.

#include <stdio.h>
#include <stdbool.h>

#define DIM 5

int nr=0, marcaj[DIM][DIM] = {0}, matrice[DIM][DIM] = {
    {5, 1, 2, 3, 2},
    {5, 3, 2, 2, 4},
    {5, 2, 4, 5, 4},
    {3, 4, 5, 1, 2},
    {3, 5, 5, 4, 2},
    };

bool solutionFound = false;

void printMatrice() {
    for (int i = 0; i < DIM; i++) {
        for (int j = 0; j < DIM; j++) {
            printf("%d ", marcaj[i][j]);
        }
        printf("\n");
    }
}

void dfs(bool visited[DIM][DIM], int row, int col) {
    int rowOffset[] = {-1, 0, 1, 0};
    int colOffset[] = {0, 1, 0, -1};

    visited[row][col] = true;

    for (int i = 0; i < 4; i++) {
        int newRow = row + rowOffset[i];
        int newCol = col + colOffset[i];

        if (newRow >= 0 && newRow < DIM && newCol >= 0 && newCol < DIM &&
            !visited[newRow][newCol] && marcaj[newRow][newCol] == 0) {
            dfs(visited, newRow, newCol);
        }
    }
}

bool areAllzerosConnected() {
    bool visited[DIM][DIM] = {false};
    bool startFound = false;

    for (int i = 0; i < DIM && !startFound; i++) {
        for (int j = 0; j < DIM; j++) {
            if (marcaj[i][j] == 0) {
                dfs(visited, i, j);
                startFound = true;
                break;
            }
        }
    }

    if (!startFound) return true;

    for (int i = 0; i < DIM; i++) {
        for (int j = 0; j < DIM; j++) {
            if (marcaj[i][j] == 0 && !visited[i][j]) {
                return false;
            }
        }
    }

    return true;
}

bool duplicat(int lin, int col) {
    for (int i = 0; i < DIM; i++) {
        if (marcaj[lin][i] == 0 && i != col && matrice[lin][i] == matrice[lin][col]) {
            return true;
        }
        if (marcaj[i][col] == 0 && i != lin && matrice[i][col] == matrice[lin][col]) {
            return true;
        }
    }
    return false;
}

bool areAdjacentMarkedCells() {
    for (int i = 0; i < DIM; i++) {
        for (int j = 0; j < DIM; j++) {
            if (marcaj[i][j] == 1) {
                if ((i > 0 && marcaj[i - 1][j] == 1) ||
                    (i < DIM - 1 && marcaj[i + 1][j] == 1) ||
                    (j > 0 && marcaj[i][j - 1] == 1) ||
                    (j < DIM - 1 && marcaj[i][j + 1] == 1)) {
                    return true;
                }
            }
        }
    }
    return false;
}

void bkt(int lin, int col) {
    if (solutionFound) return;

    if (lin == DIM) {
            printMatrice();
            printf("Numar mutari:%d\n",nr);
            solutionFound = true;
            return;
    }

    if (col == DIM) {
        bkt(lin + 1, 0);
        return;
    }

    if (duplicat(lin, col)) {
        nr++;
        marcaj[lin][col] = 1;
        if (areAllzerosConnected() && !areAdjacentMarkedCells()) {
            bkt(lin, col + 1);
        }

    }
    marcaj[lin][col] = 0;
    bkt(lin, col + 1);
}

int main() {
    bkt(0, 0);
    return 0;
}