Problem:
 Score : 900 points    Problem Statement Let us consider a grid of squares with N rows and N columns. You want to put some domino pieces on this grid.
Each domino piece covers two squares that have a common side. Each square can be covered by at most one piece.  For each row of the grid, let's define its quality as the number of domino pieces that cover at least one square in this row.
We define the quality of each column similarly.  Find a way to put at least one domino piece on the grid so that the quality of every row is equal to the quality of every column,
or determine that such a placement doesn't exist.      Constraints  2 \le N \le 1000         Input Input is given from Standard Input in the following format:  N       Output If the required domino placement doesn't exist, print a single integer -1 .  Otherwise, output your placement as N strings of N characters each.
If a square is not covered, the corresponding character must be . (a dot).
Otherwise, it must contain a lowercase English letter.
Squares covered by the same domino piece must contain the same letter.
If two squares have a common side but belong to different pieces, they must contain different letters.        Sample Input 1 6      Sample Output 1 aabb..
b..zz.
ba....
.a..aa
..a..b
..a..b  The quality of every row and every column is 2.       Sample Input 2 2      Sample Output 2 -1

Solution (Python):
N = int(input())

if N == 2:
    print(-1)
    exit()
elif N == 3:
    print('a..')
    print('a..')
    print('.aa')
    exit()

ans = [['.'] * N for _ in range(N)]
u = [['a', 'a'], ['b', 'b']]
v = [['c', 'd'], ['c', 'd']]
if N % 4 == 0:
    for i in range(0, N, 2):
        for h in range(2):
            for w in range(2):
                ans[i+h][i+w] = u[h][w]
        for h in range(2):
            for w in range(2):
                ans[i+h][N-i-w-1] = v[h][w]
elif N % 4 == 1:
    for i in range(0, N//2 - 2, 2):
        for h in range(2):
            for w in range(2):
                ans[i+h][i+w] = u[h][w]
        for h in range(2):
            for w in range(2):
                ans[i+h][N-i-w-1] = v[h][w]
    for i in range(N//2 + 3, N, 2):
        for h in range(2):
            for w in range(2):
                ans[i+h][i+w] = u[h][w]
        for h in range(2):
            for w in range(2):
                ans[i+h][N-i-w-1] = v[h][w]
    a = [['c', 'c', 'd', 'd', 'e'], ['f', 'g', '.', '.', 'e'], ['f', 'g', '.', '.', 'h'],
         ['i', '.', 'k', 'k', 'h'], ['i', 'j', 'j', 'l', 'l']]
    i0 = N//2 - 2
    for h in range(5):
        for w in range(5):
            ans[i0 + h][i0 + w] = a[h][w]
elif N % 4 == 2:
    for i in range(0, N//2 - 3, 2):
        for h in range(2):
            for w in range(2):
                ans[i+h][i+w] = u[h][w]
        for h in range(2):
            for w in range(2):
                ans[i+h][N-i-w-1] = v[h][w]
    for i in range(N//2 + 3, N, 2):
        for h in range(2):
            for w in range(2):
                ans[i+h][i+w] = u[h][w]
        for h in range(2):
            for w in range(2):
                ans[i+h][N-i-w-1] = v[h][w]
    a = [['c', '.', 'd', 'd', 'e', 'e'], ['c', 'f', '.', 'g', 'g', '.'], ['h', 'f', '.', '.', '.', 'i'],
         ['h', '.', '.', '.', 'k', 'i'], ['.', 'j', 'j', '.', 'k', 'n'], ['l', 'l', 'm', 'm', '.', 'n']]
    i0 = N//2 - 3
    for h in range(6):
        for w in range(6):
            ans[i0 + h][i0 + w] = a[h][w]
elif N % 4 == 3:
    for i in range(0, N//2 - 3, 2):
        for h in range(2):
            for w in range(2):
                ans[i+h][i+w] = u[h][w]
        for h in range(2):
            for w in range(2):
                ans[i+h][N-i-w-1] = v[h][w]
    for i in range(N//2 + 4, N, 2):
        for h in range(2):
            for w in range(2):
                ans[i+h][i+w] = u[h][w]
        for h in range(2):
            for w in range(2):
                ans[i+h][N-i-w-1] = v[h][w]

    a = [['c', '.', '.', 'd', 'd', 'e', 'e'], ['c', 'f', '.', '.', 'g', 'g', '.'], ['h', 'f', 'i', '.', '.', '.', '.'],
         ['h', '.', 'i', '.', '.', '.', 'k'], ['.', '.', '.', 'j', 'j', 'm', 'k'], ['.', 'l', 'l', '.', '.', 'm', 'p'],
         ['n', 'n', 'o', 'o', '.', '.', 'p']]
    i0 = N//2 - 3
    for h in range(7):
        for w in range(7):
            ans[i0 + h][i0 + w] = a[h][w]

[print(''.join(ans[i])) for i in range(N)]

Solution (Python):

import collections

table = collections.defaultdict(dict)
table[1][3] = '''
aa.
..b
..b
'''.strip().splitlines()
table[2][3] = '''
aab
d.b
dcc
'''.strip().splitlines()
table[3][4] = '''
aadc
bbdc
ghff
ghee
'''.strip().splitlines()
table[3][5] = '''
abb.d
a.ccd
eefgg
hif..
hi.jj
'''.strip().splitlines()
table[3][7] = '''
a.cc.dd
abb..e.
..mm.ef
l...n.f
lk..n..
.k..hhg
jj.ii.g
'''.strip().splitlines()

def solve1(n, q):
    dp = [None] * (n + 1)
    dp[0] = 0
    for i in range(n + 1):
        for delta in table[q].keys():
            if i - delta >= 0 and dp[i - delta] is not None:
                dp[i] = delta
    if dp[n] is None:
        return None
    f = [['.' for _ in range(n)] for _ in range(n)]
    k = n
    while k:
        delta = dp[k]
        k -= delta
        for y in range(delta):
            for x in range(delta):
                f[k + y][k + x] = table[q][delta][y][x]
    return [''.join(line) for line in f]

def solve(n):
    return solve1(n, 1) or solve1(n, 2) or solve1(n, 3)

def main():
    n = int(input())
    f = solve(n)
    if f:
        for line in f:
            print(line)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Solution (Python):
z3 = ['aa.',
      '..a',
      '..a']
z4 = ['abcc',
      'abdd',
      'eegh',
      'ffgh']
z5 = ['biihh',
      'baa.g',
      'c..ag',
      'c..af',
      'ddeef']
z6 = ['aa.bbc',
      '..ae.c',
      '..aedd',
      'bbcaa.',
      'e.c..a',
      'edd..a']
z7 = ['bbccdd.',
      'aa.aa.b',
      '..a..ab',
      '..a..ac',
      'aa.aa.c',
      '..a..ad',
      '..a..ad']
n = int(input())
if n == 2:
  print(-1)
elif n == 3:
  for x in z3:
    print(x)
else:
  m = n // 4 - 1
  if n % 4 == 0:
    for x in z4:
      print(x + '.' * (n-4))
  if n % 4 == 1:
    for x in z5:
      print(x + '.' * (n-5))
  if n % 4 == 2:
    for x in z6:
      print(x + '.' * (n-6))
  if n % 4 == 3:
    for x in z7:
      print(x + '.' * (n-7))
  for i in range(m):
    for x in z4:
      l = n % 4 + (i+1) * 4
      print( '.' * l + x + '.' * (n-l-4) )

Solution (Python):




import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n = int(input())



a21 = [["a","a"],["b","b"]]
a22 = [["c","d"],["c","d"]]

a3 = [["a","a","."],[".",".","b"],[".",".","b"]]

a4 = [["q","q","r","s"],["t","t","r","s"],["u","x","v","v"],["u","x","w","w"]]

a5 = [["c","c","d","d","l"],["e","f","f",".","l"],["e",".",".","h","g"],["i",".",".","h","g"],["i","j","j","k","k"]]

a7 = [["c","c","d","d",".",".","e"],[".","f","f",".",".","g","e"],[".",".","h","h",".","g","i"],["j",".",".",".","k",".","i"],["j","l",".",".","k",".","."],["m","l",".",".","n","n","."],["m",".",".","o","o","p","p"]]



if n == 2: print(-1)
else:
    if n == 3:
        ans = a3

    elif n%2 == 0:
        ans = [["."]*n for i in range(n)]
        for i in range(n//2):
            for j in range(2):
                for k in range(2):
                    ans[2*i+j][2*i+k] = a21[j][k]
    
        for i in range(n//2):
            for j in range(2):
                for k in range(2):
                    ans[2+2*i+j-n][2*i+k] = a22[j][k]

    elif n%4==1:
        ans = [["."]*n for i in range(n)]
        for i in range(5):
            for j in range(5):
                ans[i][j] = a5[i][j]
                
        for i in range((n-5)//2):
            for j in range(2):
                for k in range(2):
                    ans[5+2*i+j][5+2*i+k] = a21[j][k]
    
        for i in range((n-5)//2):
            for j in range(2):
                for k in range(2):
                    c = 5+2+2*i+j
                    d = 5+2*i+k
                    if c >= n:
                        c = 5+j
                    ans[c][d] = a22[j][k]
        


    elif n%4==3:
        ans = [["."]*n for i in range(n)]
        for i in range(7):
            for j in range(7):
                ans[i][j] = a7[i][j]

        for i in range((n-7)//2):
            for j in range(2):
                for k in range(2):
                    ans[7+2*i+j][7+2*i+k] = a21[j][k]
    
        for i in range((n-7)//2):
            for j in range(2):
                for k in range(2):
                    c = 7+2+2*i+j
                    d = 7+2*i+k
                    if c >= n:
                        c = 7+j
                    ans[c][d] = a22[j][k]

    for i in ans:
        print(*i,sep="")

Solution (Python):
import sys
input = sys.stdin.readline

N=int(input())
if N==2:
    print(-1)
    sys.exit()

if N==7:
    S=['.hhagg.\n', 'g..a..h\n', 'g.ee..h\n', 'bb..fcc\n', 'gg..f.h\n', '..hd..h\n', '..hdgg.\n']
    print("".join(S))
    sys.exit()

if N==11:
    S=['......abc..\n', '......abc..\n', '.....igg.dd\n', '.....i..hee\n', '....jj..hff\n', '..ll..kmm..\n', 'ff..h.k....\n', 'ee..hn.....\n', 'ddgg.n.....\n', '..abc......\n', '..abc......\n']
    print("".join(S))
    sys.exit()   

ANS=[["."]*N for i in range(N)]

if N%3==0:
    for i in range(0,N,3):
        ANS[i][i]="a"
        ANS[i][i+1]="a"
        ANS[i+1][i+2]="a"
        ANS[i+2][i+2]="a"
else:
    now=0
    while (N-now)%4!=0:

        i=now
        now+=5

        ANS[i][i]="a"
        ANS[i][i+1]="a"
        ANS[i][i+2]="b"
        ANS[i][i+3]="b"
        ANS[i][i+4]="c"
        ANS[i+1][i+4]="c"
        ANS[i+2][i+4]="d"
        ANS[i+3][i+4]="d"
        ANS[i+4][i+4]="e"
        ANS[i+4][i+3]="e"
        ANS[i+4][i+2]="f"
        ANS[i+4][i+1]="f"
        ANS[i+4][i]="g"
        ANS[i+3][i]="g"
        ANS[i+2][i]="h"
        ANS[i+1][i]="h"

        ANS[i+1][i+1]="i"
        ANS[i+1][i+2]="i"
        ANS[i+2][i+3]="j"
        ANS[i+3][i+3]="j"

    for i in range(now,N,4):
        ANS[i][i]="a"
        ANS[i][i+1]="a"
        ANS[i+1][i]="b"
        ANS[i+1][i+1]="b"

        ANS[i][i+2]="c"
        ANS[i+1][i+2]="c"
        ANS[i][i+3]="d"
        ANS[i+1][i+3]="d"

        ANS[i+2][i+2]="e"
        ANS[i+2][i+3]="e"
        ANS[i+3][i+2]="f"
        ANS[i+3][i+3]="f"

        ANS[i+2][i]="g"
        ANS[i+3][i]="g"
        ANS[i+2][i+1]="h"
        ANS[i+3][i+1]="h"
            
for ans in ANS:
    print("".join(ans))

Solution (Python):
def comb(n, k, L):
    X = [[0] * n for _ in range(n)]
    for A, a, b in L:
        for i in range(len(A)):
            for j in range(len(A)):
                X[i+a][j+b] = A[i][j] + k if A[i][j] else 0
    return X
def ans(A):
    for a in A:
        print("".join([chr(b+97) if b else "." for b in a]))
a3 = [[1, 0, 0], [1, 0, 0], [0, 2, 2]]
a4 = [[1, 2, 3, 3], [1, 2, 4, 4], [5, 5, 6, 7], [8, 8, 6, 7]]
a5 = [[1, 1, 2, 2, 3], [4, 0, 5, 5, 3], [4, 7, 0, 0, 8], [9, 7, 0, 0, 8], [9, 5, 5, 6, 6]]
a6 = [[1, 0, 0, 1, 0, 0], [1, 0, 0, 1, 0, 0], [0, 2, 2, 0, 2, 2], [1, 0, 0, 1, 0, 0], [1, 0, 0, 1, 0, 0], [0, 2, 2, 0, 2, 2]]
a7 = [[1, 0, 0, 1, 0, 0, 3], [1, 0, 0, 1, 0, 0, 3], [0, 2, 2, 0, 2, 2, 4], [1, 0, 0, 1, 0, 0, 4], [1, 0, 0, 1, 0, 0, 5], [0, 2, 2, 0, 2, 2, 5], [6, 6, 7, 7, 8, 8, 0]]

N = int(input())
if N <= 2:
    print(-1)
    exit()
if N <= 7:
    X = [a3, a4, a5, a6, a7][N-3]
elif N == 11:
    X = comb(11, 0, [[a4, 0, 0], [a7, 4, 4]])
elif N == 14:
    X = comb(14, 0, [[a7, 0, 0], [a7, 7, 7]])
else:
    b = N % 4
    a = (N - b * 5) // 4
    L = []
    i = 0
    for _ in range(a):
        L.append([a4, i, i])
        i += 4
    for _ in range(b):
        L.append([a5, i, i])
        i += 5
    X = comb(N, 0, L)

ans(X)

Solution (Python):
def main():
    n = int(raw_input())
    if n == 2:
        print -1
    elif n == 3 or n == 6:
        ans = [list('.' * n) for _ in xrange(n)]
        c = 0
        for i in xrange(n / 3):
            ans[c][c] = ans[c][c+1] = 'a'
            ans[c+1][c] = ans[c+2][c] = 'b'
            ans[c+2][c+1] = ans[c+2][c+2] = 'c'
            ans[c][c+2] = ans[c+1][c+2] = 'd'
            c += 3
        for l in ans:
            print ''.join(l)
    elif n == 7 or n == 11:
        ans = [list('.' * n) for _ in xrange(n)]
        ans[0][0] = ans[0][1] = 'a'
        ans[0][2] = ans[0][3] = 'b'
        ans[1][0] = ans[1][1] = 'c'
        ans[1][2] = ans[1][3] = 'd'
        ans[0][4] = ans[1][4] = 'e'
        ans[2][1] = ans[2][2] = 'f'
        ans[2][3] = ans[2][4] = 'g'
        ans[2][5] = ans[2][6] = 'h'
        ans[3][4] = ans[4][4] = 'i'
        ans[3][5] = ans[4][5] = 'j'
        ans[3][6] = ans[4][6] = 'k'
        ans[5][0] = ans[6][0] = 'l'
        ans[5][5] = ans[6][5] = 'm'
        ans[5][6] = ans[6][6] = 'n'
        c = 7
        if n == 11:
            ans[c][c] = ans[c][c+1] = 'a'
            ans[c+1][c] = ans[c+1][c+1] = 'b'
            ans[c][c+2] = ans[c+1][c+2] = 'c'
            ans[c][c+3] = ans[c+1][c+3] = 'd'
            ans[c+2][c] = ans[c+3][c] = 'e'
            ans[c+2][c+1] = ans[c+3][c+1] = 'f'
            ans[c+2][c+2] = ans[c+2][c+3] = 'g'
            ans[c+3][c+2] = ans[c+3][c+3] = 'h'
        for l in ans:
            print ''.join(l)
    else:
        s = t = 0
        for i in xrange(1000):
            if (n - 4 * i) % 5 == 0:
                s = i
                t = (n - 4 * i) / 5
                break
        c = 0
        ans = [list('.' * n) for _ in xrange(n)]
        for i in xrange(s):
            ans[c][c] = ans[c][c+1] = 'a'
            ans[c+1][c] = ans[c+1][c+1] = 'b'
            ans[c][c+2] = ans[c+1][c+2] = 'c'
            ans[c][c+3] = ans[c+1][c+3] = 'd'
            ans[c+2][c] = ans[c+3][c] = 'e'
            ans[c+2][c+1] = ans[c+3][c+1] = 'f'
            ans[c+2][c+2] = ans[c+2][c+3] = 'g'
            ans[c+3][c+2] = ans[c+3][c+3] = 'h'
            c += 4
        for i in xrange(t):
            ans[c][c] = ans[c][c+1] = 'a'
            ans[c+1][c] = ans[c+2][c] = 'b'
            ans[c+2][c+1] = ans[c+2][c+2] = 'c'
            ans[c][c+2] = ans[c+1][c+2] = 'd'
            ans[c][c+3] = ans[c][c+4] = 'e'
            ans[c+1][c+3] = ans[c+1][c+4] = 'f'
            ans[c+2][c+3] = ans[c+2][c+4] = 'g'
            ans[c+3][c] = ans[c+4][c] = 'h'
            ans[c+3][c+1] = ans[c+4][c+1] = 'i'
            ans[c+3][c+2] = ans[c+4][c+2] = 'j'
            c += 5
        for l in ans:
            print ''.join(l)
main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(read())

def output(A):
    print('\n'.join(''.join(row) for row in A))

a = 'a'; b = 'b'; c = 'c'; d = 'd'; e = 'e'; f = 'f'; g = 'g'; h = 'h'; x = '.'

A3 = np.array([
        [a,a,x],
        [x,x,a],
        [x,x,a]
],dtype='U1')

A4 = np.array([
    [a,a,c,d],
    [b,b,c,d],
    [e,f,g,g],
    [e,f,h,h]
],dtype='U1')

A5 = np.array([
    [a,a,c,a,a],
    [b,b,c,x,c],
    [x,a,b,b,c],
    [b,a,x,x,a],
    [b,x,b,b,a]
],dtype='U1')

A7 = np.array([
    [a,b,a,x,x,x,x],
    [a,b,a,x,x,x,x],
    [c,c,b,a,a,x,x],
    [x,a,b,c,c,x,x],
    [x,a,x,x,a,b,b],
    [a,x,x,x,a,c,c],
    [a,x,b,b,x,a,a],
],dtype='U1')

def solve(N):
    if N <= 2:
        print(-1)
        return
    if N == 3:
        output(A3)
        return
    if N == 6:
        A = np.full((6,6),'.','U1')
        A[:3,:3] = A3
        A[3:,3:] = A3
        output(A)
        return
    if N == 7:
        output(A7)
        return
    if N == 11:
        A = np.full((11,11),'.','U1')
        A[:4,:4] = A4
        A[4:,4:] = A7
        output(A)
        return
    
    
    x = 0
    while (N - 4 * x) % 5:
        x += 1
    y = (N - 4 * x) // 5
    A = np.full((N,N),'.','U1')
    for i in range(x):
        A[4*i:4*i+4,4*i:4*i+4] = A4
    for j in range(y):
        A[4*x+5*j:4*x+5*j+5,4*x+5*j:4*x+5*j+5] = A5
    output(A)
    return

solve(N)

Solution (Python):
a3 = """
aab
b.b
baa
"""
a6 = """
aabccd
b.bd.d
baadcc
ccdaab
d.db.b
dccbaa
"""

g4 = """
aaca
bbca
cabb
cacc
"""

g4 = list(map(list, g4.split()))

g5 = """
aabba
bcc.a
b..cb
a..cb
abbaa
"""

g5 = list(map(list, g5.split()))

g7 = """
caabb..
cb..cc.
aba....
a.a..aa
c..a..b
c..a..b
.aaccaa
"""

g7 = list(map(list, g7.split()))

def main():
    N = int(input())
    if N == 2: print(-1)
    elif N == 3: print("\n".join(a3.split()))
    elif N == 6: print("\n".join(a6.split()))
    else:
        x = [['.']*N for i in range(N)]
        for v4 in range(N//4+1):
            for v5 in range((N-v4*4)//5+1):
                v7 = (N-v4*4-v5*5)//7
                if v4*4+v5*5+v7*7 != N: continue

                idx = 0
                for i in range(v4):
                    for j in range(4):
                        x[idx+j][idx:idx+4] = g4[j]
                    idx += 4
                

                for i in range(v5):
                    for j in range(5):
                        x[idx+j][idx:idx+5] = g5[j]
                    idx += 5
                

                for i in range(v7):
                    for j in range(7):
                        x[idx+j][idx:idx+7] = g7[j]
                    idx += 7

                for q in x:
                    print(''.join(q))
                
                return

if __name__ == '__main__':
    main()