Construct a Matrix N x N with first N^2 natural numbers for an input N

Given an integer N, the task is to construct a matrix M[][] of size N x N with numbers in the range [1, N^2] with the following conditions :

1. The elements of the matrix M should be an integer between 1 and N^2.
2. All elements of the matrix M are pairwise distinct.
3. For each square submatrix containing cells in row r through r+a and in columns c through c+a(inclusive) for some valid integers r,c and a>=0: M(r,c)+M(r+a,c+a) is even and M(r,c+a)+M(r+a,c) is even.
    

Examples: 
 

Input: N = 2 
Output: 
1 2 
4 3 
Explanation: 
This matrix has 5 square submatrix and 4 of them ([1], [2], [3], [4]) have a=0 so they satisfy the conditions. 
The last square submatrix is the whole matrix M where r=c=a=1. We can see that M_{(1, 1)}+M_{(2, 2)}=1+3=4 and M_{(1, 2)}+M_{(2, 1)}=2+4=6 are both even.
Input: N = 4 
Output: 
1 2 3 4 
8 7 6 5 
9 10 11 12 
16 15 14 13 
 

Approach: We know that the sum of two numbers is even when their parity is the same. Let us say the parity of M_{(i, j)} is odd that means the parity of M_{(i+1, j+1)}, M_{(i+1, j-1)}, M_{(i-1, j+1)}, M_{(i-1, j-1)} has to be odd.
Below is the illustration for N = 4 to generate a matrix of size 4×4: 
 

So from the above illustration we have to fill the matrix in the Checkerboard Pattern. We can fill it in two ways: 
 

• All black cells have an odd integer and white cells have an even integer.
• All black cells have an even integer and white cells have an odd integer.

Below is the implementation of the above approach:
  

1 2 3 4 
8 7 6 5 
9 10 11 12 
16 15 14 13

Time Complexity: O(N^2) 
Auxiliary Space: O(1)