Construct a unique matrix n x n for an input n - GeeksforGeeks
Given an odd integer n, find a matrix of size n x n with following conditions:
Read full article from Construct a unique matrix n x n for an input n - GeeksforGeeks
Given an odd integer n, find a matrix of size n x n with following conditions:
- Each cell contains an integer from 1 and n (inclusive).
- No integer appears twice in the same row or the same column.
- All 1's must be at every possible distance from the center of the matrix. The center of a n x n square is cell ((n-1)/2, (n-1)/2) for odd n.
The idea is to first decide positions of 1s. Once possible arrangement of 1s for n = 5 is,
_ _ _ _ 1 1 _ _ _ _ _ _ _ 1 _ _ 1 _ _ _ _ _ 1 _ _
Once we have decided 1s, task of filling remaining items is simple. We fill remaining entries column by column. For every 1, we traverse its column and fill all entries below it with 2, 3,…p and fill all entries above it with p+1, .. n. We get following.
5 3 2 4 1 1 4 3 5 2 2 5 4 1 3 3 1 5 2 4 4 2 1 3 5
To decide initial positions of 1s, we traverse all rows and keep track of two column numbers “left” and “right”.
1) “right” starts with n-1 and keep decrementing after every alternate row.
2) “left” starts with 0 and keep incrementing after every alternate row.
1) “right” starts with n-1 and keep decrementing after every alternate row.
2) “left” starts with 0 and keep incrementing after every alternate row.
const
int
MAX = 100;
int
mat[MAX][MAX];
// Fills non-one entries in column j
// Given that there is a "1" at position mat[i][j],
// this function fills other entries of column j.
void
fillRemaining(
int
i,
int
j,
int
n)
{
// Initialize value to be filled
int
x = 2;
// Fill all values below i as 2, 3, ...p
for
(
int
k=i+1; k<n; k++)
mat[k][j] = x++;
// Fill all values above i as p+1, p+2, .. n
for
(
int
k=0; k<i; k++)
mat[k][j] = x++;
}
// Fills entries in mat[][] with the given set of
// rules
void
constructMatrix(
int
n)
{
// Alternatively fill 1s starting from
// rightmost and leftmost columns. For
// example for n = 3, we get { {_ _ 1},
// {1 _ _} {_ 1 _}}
int
right = n-1, left = 0;
for
(
int
i=0; i < n; i++)
{
// If i is even, then fill next column
// from right
if
(i%2 == 0)
{
mat[i][right] = 1;
// After filling 1, fill remaining entries
// of column "right"
fillRemaining(i, right, n);
// Move right one column back
right--;
}
else
// Fill next column from left
{
mat[i][left] = 1;
// After filling 1, fill remaining entries
// of column "left"
fillRemaining(i, left, n);
// Move left one column forward
left++;
}
}
}