I have a program in c that doesn't work as it should with parity very well

Question

My code doesn't display matrices larger than n>1

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

#define MAX_N 10

int n;
int matrix[MAX_N][MAX_N];
bool used[MAX_N * MAX_N + 1];
int count = 0;

bool check(int row, int col, int val) {
    if (row > 0 && abs(val - matrix[row-1][col]) % 2 == 0) {
        return false; // check parity with northern neighbor
    }
    if (col > 0 && abs(val - matrix[row][col-1]) % 2 == 0) {
        return false; // check parity with western neighbor
    }
    if (row < n-1 && abs(val - matrix[row+1][col]) % 2 == 0) {
        return false; // check parity with southern neighbor
    }
    if (col < n-1 && abs(val - matrix[row][col+1]) % 2 == 0) {
        return false; // check parity with eastern neighbor
    }
    return true; //all neighbors respect the parity condition
}

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

void backtrack(int row, int col) {
    if (row == n) {
        count++;
        print_matrix();
        return;
    }
    if (col == n) {
        backtrack(row+1, 0);
        return;
    }
    for (int val = 1; val <= n*n; val++) {
        if (!used[val] && check(row, col, val)) {
            matrix[row][col] = val;
            used[val] = true;
            backtrack(row, col+1);
            used[val] = false;
        }
    }
}

int main() {
    printf("Enter the size of the array n (maxim %d): ", MAX_N);
    scanf("%d", &n);
    if (n <= 0 || n > MAX_N) {
        printf("The array size is invalid.\n");
        return 0;
    }
    printf("The matrices that respect the condition are:\n");
    backtrack(0, 0);
    printf("Total number of arrays generated: %d\n", count);
    return 0;
}

I am trying to solve the problem with displaying matrices when n>1. Or if I did not complete the program correctly, you can help me. This is my task: Generate all nxn matrices containing distinct elements from the set {1,...,n^2}, so that no element in the matrix has the same parity as its neighbors (neighbors of an element are considered in N, S, E, W directions).

Answer 1

The code checks the values in the matrix while it's beeing constructed, so that some of the neighbors are still 0. You may change the conditions in check like the following:

if (     row > 0  
     &&  matrix[row-1][col] != 0
     && (val - matrix[row-1][col]) % 2 == 0 ) {
    return false; // check parity with northern neighbor
}

Note, though, that you could exploit the fact that only matrices with a pattern of alternating odd and even values are possible solutions.