Not Adjacent Matrix (Codeforces 1520C)
Tags: Others, constructive algorithms

We will consider the numbers $$$a$$$ and $$$b$$$ as adjacent if they differ by exactly one, that is, $$$|a-b|=1$$$.We will consider cells of a square matrix $$$n \times n$$$ as adjacent if they have a common side, that is, for cell $$$(r, c)$$$ cells $$$(r, c-1)$$$, $$$(r, c+1)$$$, $$$(r-1, c)$$$ and $$$(r+1, c)$$$ are adjacent to it.For a given number $$$n$$$, construct a square matrix $$$n \times n$$$ such that:   Each integer from $$$1$$$ to $$$n^2$$$ occurs in this matrix exactly once;  If $$$(r_1, c_1)$$$ and $$$(r_2, c_2)$$$ are adjacent cells, then the numbers written in them must not be adjacent. 

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$). Then $$$t$$$ test cases follow.Each test case is characterized by one integer $$$n$$$ ($$$1 \le n \le 100$$$).

Output: For each test case, output:   -1, if the required matrix does not exist;  the required matrix, otherwise (any such matrix if many of them exist). The matrix should be outputted as $$$n$$$ lines, where each line contains $$$n$$$ integers.


Sample Inputs:
3
1
2
3

Sample Outputs:
1
-1
2 9 7
4 6 3
1 8 5

Solution (Python):
def not_adjacent(n):
    if n == 2:
        return -1
    sol = [i for i in range(1, n * n + 1, 2)]
    for item in range(2, n * n + 1, 2):
        sol.append(item)
    matrix = list()
    for item in range(n):
        s = ' '.join(list(map(str, sol[item * n:item * n + n])))
        matrix.append(s)
    return matrix
if __name__ == '__main__':
    t = int(input())
    for test_case in range(t):
        n = int(input())
        result = not_adjacent(n)
        if result == -1:
            print(-1)
        elif len(result) == 1:
            print(1)
        else:
            for item in result:
                print(item)

Solution (Python):
def solve():
    n = int(input())
    if n == 2:
        print(-1)
        return
    if n == 1:
        print(1)
        return
    ans = [[0] * n for _ in range(n)]
    cur = 1
    for i in range(n):
        if i & 1:
            for j in range(1, n, 2):
                ans[i][j] = cur
                cur += 1
        else:
            for j in range(0, n, 2):
                ans[i][j] = cur
                cur += 1
    for i in range(n):
        for j in range(n):
            if not ans[i][j]:
                ans[i][j] = cur
                cur += 1
    for row in ans:
        print(' '.join(map(str, row)))
for _ in range(int(input())):
    solve()

Solution (Python):
def check(mat):
    for i in range(len(mat) - 1):
        for j in range(len(mat[0])):
            if abs(mat[i][j] - mat[i + 1][j]) <= 1:
                return False
    return True

def solve(n):
    arr = [0 for i in range(n * n)]
    i = 0
    for num in range(1, (n * n + 1) // 2 + 1):
        arr[2 * i] = num
        i += 1
    i = 0
    for num in range((n * n + 1) // 2 + 1, n * n + 1):
        arr[2 * i + 1] = num
        i += 1
    mat = []
    flag = 0
    for i in range(n):
        if not flag:
            mat.append(arr[n * i:n * i + n])
            flag = 1
        else:
            arr[n * i:n * i + n] = arr[n * i:n * i + n][::-1]
            mat.append(arr[n * i:n * i + n])
            flag = 0
    if n == 2:
        print(-1)
    else:
        for x in mat:
            print(' '.join(map(str, x)))
for t in range(int(input())):
    n = int(input())
    solve(n)