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 solution is to change check to only consider values that have been previously set. This is very easy, since you can take advantage of the order in which they're set. Just eliminate the last two cases, so you end up with:

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
    }
    return true; //all neighbors respect the parity condition
}

This only checks the values above and to the left of the current value.

Note that it does not suffice to check for zero values, since that will fail after it backtracks (in which case subsequent values are not guaranteed to be zero).

Answer 2

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.