Problem:
8 Queens Problem The goal of 8 Queens Problem is to put eight queens on a chess-board such that none of them threatens any of others. A queen threatens the squares in the same row, in the same column, or on the same diagonals as shown in the following figure.   For a given chess board where $k$ queens are already placed, find the solution of the 8 queens problem. Input In the first line, an integer $k$ is given. In the following $k$ lines, each square where a queen is already placed is given by two integers $r$ and $c$. $r$ and $c$ respectively denotes the row number and the column number. The row/column numbers start with 0. Output Print a $8 \times 8$ chess board by strings where a square with a queen is represented by ' Q ' and an empty square is represented by ' . '. Constraints  There is exactly one solution  Sample Input 1 2
2 2
5 3 Sample Output 1 ......Q.
Q.......
..Q.....
.......Q
.....Q..
...Q....
.Q......
....Q...

Solution (Python):
N = 8
FREE = 1
NOT_FREE = -1

def initialize():
    row = [FREE] * N
    col = [FREE] * N
    dpos = [FREE] * (2 * N - 1)
    dneg = [FREE] * (2 * N - 1)
    return row, col, dpos, dneg


def printBoard(x, row):
    for i in range(N):
        for j in range(N):
            if x[i][j]:
                if row[i] != j:
                    return
    for i in range(N):
        line = ''
        for j in range(N):
            if row[i] == j:
                line += 'Q'
            else:
                line += '.'
        print(line)


def recursive(i, x, row, col, dpos, dneg):
    if i == N:
        printBoard(x, row)
        return

    for j in range(N):
        if (NOT_FREE == col[j] or
            NOT_FREE == dpos[i + j] or
            NOT_FREE == dneg[i - j + N - 1]):
            continue
        row[i] = j
        col[j] = NOT_FREE
        dpos[i + j] = NOT_FREE
        dneg[i - j + N - 1] = NOT_FREE
        recursive(i+1, x, row, col, dpos, dneg)
        row[i] = FREE
        col[j] = FREE
        dpos[i + j] = FREE
        dneg[i - j + N - 1] = FREE


if __name__ == '__main__':
    row, col, dpos, dneg = initialize()
    x = [[False] * N for i in range(N)]
    k = int(input())
    for i in range(k):
        r, c = [int(v) for v in input().split()]
        x[r][c] = True

    recursive(0, x, row, col, dpos, dneg)

Solution (Python):
def check(a):
    flag = True
    for i in C:
        if (i[0] == a[0]) or (i[1] == a[1]) or (abs(i[0]-a[0]) == abs(i[1]-a[1])):
            flag = False
    return flag

def recq(r):
    if r == 8:
        pass
    elif DPr[r] == 1:
        recq(r+1)
    else:
        for c in range(8):
            if DPc[c]:
                continue
            else:
                if check((r,c)):
                    DPr[r] = 1
                    DPc[c] = 1
                    C.append([r,c])
                    recq(r+1)
                    flag = False
                    for i in range(8):
                        if DPr[i]==0:
                            flag = True
                    if flag:
                        C.pop()
                        DPr[r] = 0
                        DPc[c] = 0
k = int(input())
C = [[int(i) for i in input().split()] for _ in range(k)]
DPr = [0 for i in range(8)]
DPc = [0 for i in range(8)]
for i in C:
    DPr[i[0]]=1
    DPc[i[1]]=1
recq(0)
Q = [["." for i in range(8)] for i in range(8)]
for i in C:
    Q[i[0]][i[1]] = "Q"
for i in Q:
    tmp = ""
    for j in i:
        tmp+=j
    print(tmp)

Solution (Python):

class Chess_board:
    def __init__(self):
        self.board=[[0]*8 for i in range(8)]
        self.queen_array=[]
        self.queen_row=[]


def copy_board(chess_board):
    new_board=Chess_board()
    new_board.board=[chess_board.board[i][:] for i in range(8)]
    new_board.queen_array=chess_board.queen_array[:]
    new_board.queen_row=chess_board.queen_row[:]
    return new_board


def mk_board(chess_board,queen_array):
    for queen in queen_array:
        row=queen[0]
        col=queen[1]
        if(chess_board.board[row][col]==0):
            chess_board.queen_array.append(queen)
            chess_board.queen_row.append(row)
            for i in range(8):
                chess_board.board[row][i]=1
            for i in range(8):
                chess_board.board[i][col]=1
            for i in range(1,8):
                if(row - i >=0 and col - i >=0):
                    chess_board.board[row-i][col-i]=1
                else:
                    break
            for i in range(1,8):
                if(8 > row + i >=0 and col - i >=0):
                    chess_board.board[row+i][col-i]=1
                else:
                    break
            for i in range(1,8):
                if(row - i >=0 and 8 > col + i >=0):
                    chess_board.board[row-i][col+i]=1
                else:
                    break
            for i in range(1,8):
                if(8 > row + i >=0 and 8 > col + i >=0):
                    chess_board.board[row+i][col+i]=1
                else:
                    break

        else:
            return 0
    
    return 1



def find_queen(chess_board):
    
    for tmp_row in range(8):
        if(tmp_row in chess_board.queen_row):
            pass
        else:
            break
    
    for col in range(8):
        new_board=copy_board(chess_board)
        if(mk_board(new_board,[[tmp_row,col]])==1):
            if(len(new_board.queen_row)==8):
                return new_board
            else:
                result=find_queen(new_board)
                if(result is not None):
                    return result
    
    return None



n=int(input())

queen_array=[]
for i in range(n):
    queen_array.append(list(map(int,input().split())))

board=Chess_board()
mk_board(board,queen_array)
if(n!=8):
    result_board=find_queen(board)
else:
    result_board=board

for i in range(8):
    for queen in result_board.queen_array:
        if(queen[0]==i):
            str1="."*queen[1]
            str2="."*(7-queen[1])
            print(f"{str1}Q{str2}")

Solution (Python):
import copy

n = int(input())

dotsa = []
for _ in range(n):
    y,x = map(int,input().split(" "))
    dotsa.append([y,x])

pattern = []
pattern.append(dotsa)


for y in range(8):
    nextpattern = []
    
    
    for pat in pattern:
        
        
        flag = False
        for dot in pat:
            if dot[0] == y:
                flag = True
                break

        if flag:
            nextpattern = pattern
            continue

        ifFound = False
        for x in range(8):
            ank = len(pat)
            flag2 = True
            for i in range(ank):
                if abs(pat[i][0]-y) == abs(pat[i][1]-x) or pat[i][1] == x:
                    flag2 = False
                    break
            if flag2:
                
                
                
                tmp = copy.deepcopy(pat)
                tmp.append([y,x])
                nextpattern.append(tmp)
        
    pattern = nextpattern

ans = pattern[0]
board = [["."]*8 for i in range(8)]

for ele in ans:
    board[ele[0]][ele[1]] = "Q"
for row in board:
    print(''.join(map(str,row)))

Solution (Python):
from functools import lru_cache
cc = [["." for i in range(8)] for j in range(8)]

@lru_cache(maxsize=None)     
def dia(s,a,b):
    d = []
    for i in range(8):
        for j in range(8):
            try:
                if j + (a - i) == b: 
                    d.append(s[i][j])
                if j -  (a - i) == b:
                    d.append(s[i][j])
                if j + (i - a) == b: 
                    d.append(s[i][j])
                if j -  (i - a) == b:
                    d.append(s[i][j])
            except IndexError: continue
    print(d)
    return d


def check(cc,a,b):
    ss = list(zip(*cc))
    if 'Q' in cc[a]: return False
    if 'Q' in ss[b]: return False
    d = []
    for i in range(8):
        for j in range(8):
            try:
                if j + (a - i) == b: 
                    d.append(cc[i][j])
                if j -  (a - i) == b:
                    d.append(cc[i][j])
                if j + (i - a) == b: 
                    d.append(cc[i][j])
                if j -  (i - a) == b:
                    d.append(cc[i][j])
            except IndexError: continue
    if 'Q' in d: return False
    return True

def chess(s,queen):
    if queen == 8:
        return s
    for i in range(8):
        for j in range(8):
            if check(s,i,j):
                sol = s
                sol[i][j] = 'Q'
                if chess(sol,queen+1) != [[]]:
                    return sol
                else: sol[i][j] = "."
    return [[]]


k = int(input())
for i in range(k):
    a, b = input().split()
    cc[int(a)][int(b)] = 'Q'
ans = chess(cc,k)
print('\n'.join(list(map(lambda x: ''.join(x),ans))) )

Solution (Python):
from functools import lru_cache
cc = [["." for i in range(8)] for j in range(8)]

def check(cc,a,b):
    ss = list(zip(*cc))
    if 'Q' in cc[a]: return False
    if 'Q' in ss[b]: return False
    d = []
    for i in range(8):
        for j in range(8):
            try:
                if j + (a - i) == b: 
                    d.append(cc[i][j])
                if j -  (a - i) == b:
                    d.append(cc[i][j])
                if j + (i - a) == b: 
                    d.append(cc[i][j])
                if j -  (i - a) == b:
                    d.append(cc[i][j])
            except IndexError: continue
    if 'Q' in d: return False
    return True

def chess(s,queen):
    if queen == 8:
        return s
    for i in range(8):
        for j in range(8):
            if check(s,i,j):
                sol = s
                sol[i][j] = 'Q'
                if chess(sol,queen+1) != [[]]:
                    return sol
                else: sol[i][j] = "."
    return [[]]


k = int(input())
for i in range(k):
    a, b = input().split()
    cc[int(a)][int(b)] = 'Q'
ans = chess(cc,k)
print('\n'.join(list(map(lambda x: ''.join(x),ans))) )

Solution (Python):
from functools import lru_cache
cc = [["." for i in range(8)] for j in range(8)]
 
def check(cc,a,b):
    ss = list(zip(*cc))
    if 'Q' in cc[a]: return False
    if 'Q' in ss[b]: return False
    d = []
    for i in range(8):
        for j in range(8):
            try:
                if j + abs(a - i) == b: 
                    d.append(cc[i][j])
                if j -  abs(a - i) == b:
                    d.append(cc[i][j])
            except IndexError: continue
    if 'Q' in d: return False
    return True
 
def chess(s, queen):
    if queen == 8:
        return s
    for i in range(8):
        for j in range(8):
            if check(s, i, j):
                sol = s
                sol[i][j] = 'Q'
                if chess(sol, queen+1) != [[]]:
                    return sol
                else: sol[i][j] = "."
    return [[]]
 
 
k = int(input())
for i in range(k):
    a, b = map(lambda x: int(x), input().split())
    cc[a][b] = 'Q'
ans = chess(cc, k)
print('\n'.join(list(map(lambda x: ''.join(x), ans))) )

Solution (Python):
import sys, itertools
f = sys.stdin
        
n = int(f.readline())
q = []
rest_r = set(range(8))
rest_c = [i for i in range(8)]
for _ in range(n):
    r, c = map(int, f.readline().split())
    q.append([r, c, r + c, r - c])
    rest_r.remove(r)
    rest_c.remove(c)

def check(q, rc):
    for qi in q:
        if qi[2] == rc[2] or qi[3] == rc[3] :
            return False
    return True
    
def put_queen(q, rest_r, rest_c):
    if len(q) == 8:
        return q
    c = rest_c[len(rest_r) - 1]
    for r in rest_r:
        rc = [r, c, r + c, r - c]
        if check(q, rc):
            ret = put_queen(q + [rc], rest_r.difference([r]) , rest_c)
            if ret:
                return ret
    return False
q = put_queen(q, rest_r, rest_c)
    
board = [None for _ in range(8)]
for qi in q:
    board[qi[0]] = '.' * qi[1] + 'Q' + '.' * (8 - qi[1] - 1)
for line in board:
    print(line)

Solution (Python):
def put_queen(board, pr, pc):
    def check_square(r, c):
        tmp = (pr == r) + (pc == c)
        if tmp:
            return tmp
        return 1 if abs(pr - r) == abs(pc - c) else board[r][c]

    return list(list(check_square(r, c) for c in range(8)) for r in range(8))


def check_board(board):
    return sum(sum(row) for row in board) == 72


def draw_board(board):
    print('\n'.join(''.join('Q' if c == 2 else '.' for c in row) for row in board))


def search_place(board):
    for r, row in enumerate(board):
        for c, square in enumerate(row):
            if square == 0:
                if search_place(put_queen(board, r, c)):
                    return True
    if check_board(board):
        draw_board(board)
        return True
    else:
        return False


n = int(input())
board = list(list(0 for c in range(8)) for r in range(8))

for _ in range(n):
    r, c = map(int, input().split())
    board = put_queen(board, r, c)

search_place(board)

Solution (Python):

import itertools

def print_boad(boad):
    b = [['.' for i in range(8)] for j in range(8)]
    for q in boad:
        b[q[0]][q[1]] = 'Q'

    for i in range(8):
        print(''.join(b[i]))


def find_next(base, exist_r, exist_c, exist_lt, exist_rt, invalid):
    if len(base) == 8:
        print_boad(base)
        exit()
    all_set = set(range(8))
    rest_r = all_set - exist_r
    rest_c = all_set - exist_c
    for r, c in itertools.product(rest_r, rest_c):
        if r - c in exist_lt:
            continue
        if r - (7 - c) in exist_rt:
            continue

        find_next(
                base | {(r, c)},
                exist_r | {r},
                exist_c | {c},
                exist_lt | {r - c},
                exist_rt | {r - (7 - c)},
                invalid)
        invalid.add((r, c))

    return False





k = int(input())
boad = set()
exist_r = set()
exist_c = set()
exist_lt = set()
exist_rt = set()
invalid = set()
for i in range(k):
    r, c = map(int, input().split())
    boad.add((r, c))
    exist_r.add(r)
    exist_c.add(c)
    exist_lt.add(r - c)
    exist_rt.add(r - (7 - c))


find_next(boad, exist_r, exist_c, exist_lt, exist_rt, invalid)

Solution (Python):
from __future__ import division
import sys

def can_place(pos, idx, col):
    for i in range(8):
        if pos[i] is not None and pos[i] == col: return False
    for i in range(8):
        if pos[i] is not None and abs(pos[i] - col) == abs(i - idx): return False
    return True

def dfs(pos, depth):
    if 8 == depth:
        for idx, p in enumerate(pos):
            print('.' * p + 'Q' + '.' * (7 - p))
        return True
    else:
        if pos[depth] is None:
            for i in range(8):
                if can_place(pos, depth, i):
                    pos[depth] = i
                    if dfs(pos, depth + 1):
                        return True
                    pos[depth] = None
            return False
        else:
            return dfs(pos, depth + 1)

if __name__ == '__main__':
    n = int(sys.stdin.readline())
    pos = [None] * 8
    for _ in range(n):
        row, col = map(int, sys.stdin.readline().strip().split())
        pos[row] = col
    dfs(pos, 0)

Solution (Python):
from __future__ import division
import sys

def can_place(pos, idx, col):
    for i in range(8):
        if pos[i] is not None and pos[i] == col: return False
    for i in range(8):
        if pos[i] is not None and abs(pos[i] - col) == abs(i - idx): return False
    return True

def dfs(pos, depth):
    if 8 == depth:
        for idx, p in enumerate(pos):
            print('.' * p + 'Q' + '.' * (7 - p))
    else:
        if pos[depth] is None:
            for i in range(8):
                if can_place(pos, depth, i):
                    pos[depth] = i
                    dfs(pos, depth + 1)
                    pos[depth] = None
        else:
            return dfs(pos, depth + 1)

if __name__ == '__main__':
    n = int(sys.stdin.readline())
    pos = [None] * 8
    for _ in range(n):
        row, col = map(int, sys.stdin.readline().strip().split())
        pos[row] = col
    dfs(pos, 0)

Solution (Python):
from itertools import permutations


def check(queen):
    for r1, c1 in queen:
        if not all((r1 == r2 and c1 == c2) or (r1 != r2 and c1 != c2 and r1 + c1 != r2 + c2 and r1 - c1 != r2 - c2) for r2, c2 in queen):
            return False
    return True


N = int(input())
row, col = list(range(8)), list(range(8))
queen = []
for _ in range(N):
    r, c = map(int, input().split())
    queen.append((r, c))
    row.remove(r)
    col.remove(c)
for l in permutations(col):
    queen_tmp = queen[:]
    for r, c in zip(row, l):
        queen_tmp.append((r, c))
    if check(queen_tmp):
        board = [''.join('Q' if (r, c) in queen_tmp else '.' for c in range(8)) for r in range(8)]
        print(*board, sep='\n')
        break

Solution (Python):
from itertools import permutations
def check(queen):
    for r1, c1 in queen:
        if any((r1 != r2 or c1 != c2) and (r1 == r2 or c1 == c2 or r1 + c1 == r2 + c2 or r1 - c1 == r2 - c2) for r2, c2 in queen):
            return False
    return True
N = int(input())
queen, row, col = [], list(range(8)), list(range(8))
for _ in range(N):
    r, c = map(int, input().split())
    queen.append((r, c))
    row.remove(r)
    col.remove(c)
for l in permutations(col):
    queen_tmp = queen[:] + [(r, c) for r, c in zip(row, l)]
    if check(queen_tmp):
        board = [''.join('Q' if (r, c) in queen_tmp else '.' for c in range(8)) for r in range(8)]
        print(*board, sep='\n')
        break

Solution (Python):
from itertools import permutations
def check(queen):
    for r1, c1 in queen:
        if any((r1 != r2 or c1 != c2) and (r1 == r2 or c1 == c2 or r1 + c1 == r2 + c2 or r1 - c1 == r2 - c2) for r2, c2 in queen):
            return False
    return True
N = int(input())
Q, row, col = [], list(range(8)), list(range(8))
for _ in range(N):
    r, c = map(int, input().split())
    Q.append((r, c))
    row.remove(r)
    col.remove(c)
for l in permutations(col):
    queen = Q[:] + list(zip(row, l))
    if check(queen):
        board = [''.join('Q' if (r, c) in queen else '.' for c in range(8)) for r in range(8)]
        print(*board, sep='\n')
        break

Solution (Python):
import itertools
def check(q):
    for r1, c1 in q:
        if any((r1 != r2 or c1 != c2) and (r1 == r2 or c1 == c2 or r1 + c1 == r2 + c2 or r1 - c1 == r2 - c2) for r2, c2 in q): return 0
    return 1
N = input()
Q, row, col = [], range(8), range(8)
for _ in range(N):
    r, c = map(int, raw_input().split())
    Q.append((r, c))
    row.remove(r)
    col.remove(c)
for l in itertools.permutations(col):
    queen = Q[:] + list(zip(row, l))
    if check(queen):
        print '\n'.join([''.join('Q' if (r, c) in queen else '.' for c in range(8)) for r in range(8)])
        break

Solution (Python):
import itertools
N, Q, row, col = input(), [], range(8), range(8)
for _ in range(N):
    r, c = map(int, raw_input().split())
    Q.append((r, c))
    row.remove(r)
    col.remove(c)
for l in itertools.permutations(col):
    queen = Q + list(zip(row, l))
    if not any(any((r1 != r2 or c1 != c2) and (r1 == r2 or c1 == c2 or r1 + c1 == r2 + c2 or r1 - c1 == r2 - c2) for r2, c2 in queen) for r1, c1 in queen):
        print '\n'.join(''.join('Q' if (r, c) in queen else '.' for c in range(8)) for r in range(8))
        break

Solution (Python):
import itertools
N, Q, row, col = input(), [], range(8), range(8)
for _ in range(N):
    r, c = map(int, raw_input().split())
    Q.append((r, c))
    row.remove(r)
    col.remove(c)
for l in itertools.permutations(col):
    queen = Q + list(zip(row, l))
    if not any((r1 != r2 or c1 != c2) and (r1 == r2 or c1 == c2 or r1 + c1 == r2 + c2 or r1 - c1 == r2 - c2) for r2, c2 in queen for r1, c1 in queen):
        print '\n'.join(''.join('Q' if (r, c) in queen else '.' for c in range(8)) for r in range(8))
        break

Solution (Python):
from itertools import permutations


def check(queen):
    for r1, c1 in queen:
        if not all((r1 == r2 and c1 == c2) or (r1 + c1 != r2 + c2 and r1 - c1 != r2 - c2) for r2, c2 in queen):
            return False
    return True


N = int(input())
row, col = list(range(8)), list(range(8))
queen = []
for _ in range(N):
    r, c = map(int, input().split())
    queen.append((r, c))
    row.remove(r)
    col.remove(c)
for l in permutations(col):
    queen_tmp = queen[:]
    for r, c in zip(row, l):
        queen_tmp.append((r, c))
    if check(queen_tmp):
        board = [''.join('Q' if (r, c) in queen_tmp else '.' for c in range(8)) for r in range(8)]
        print(*board, sep='\n')
        break

Solution (Python):
import itertools
N, Q, row, col = input(), [], range(8), range(8)
for _ in range(N):
    r, c = map(int, raw_input().split())
    Q.append((r, c))
    row.remove(r)
    col.remove(c)
for l in itertools.permutations(col):
    queen = Q + list(zip(row, l))
    if not any((r1 != r2 or c1 != c2) and (r1 + c1 == r2 + c2 or r1 - c1 == r2 - c2) for r2, c2 in queen for r1, c1 in queen):
        print '\n'.join(''.join('Q' if (r, c) in queen else '.' for c in range(8)) for r in range(8))
        break

Solution (Python):
def try_set(v):
    def print_board():
        for (r, c) in preset:
            if queen_pos[r] != c:
                return
        for pos in queen_pos:
            for c in range(8):
                print('Q' if c == pos else '.', end='')
            print()

    for h in range(8):
        if all((horizontal[h], dip_positive[v+h], dip_negative[v-h+7])):
            queen_pos[v] = h
            if v == 7:
                print_board()
            else:
                horizontal[h] = dip_positive[v+h] = dip_negative[v-h+7] = False
                try_set(v + 1)
                horizontal[h] = dip_positive[v+h] = dip_negative[v-h+7] = True

n = int(input())
queen_pos = [None] * 8
preset = [[pre for pre in map(int, input().split())] for _ in range(n)]
horizontal = [True] * 8
dip_positive = [True] * 15
dip_negative = [True] * 15
try_set(0)

Solution (Python):
from itertools import product

class Board(object):
    def __init__(self):
        self.queen_pos = []  
        self.status = []  
        for i in range(8):
            self.status.append(['.'] * 8)
        self.situation = []  
        for i in range(8):
            self.situation.append(['.'] * 8)

    def clear(self):
        
        temp = self.queen_pos[:]
        for q in temp:
            
            self.remove_queen(q)

    def show_status(self):
        for r in self.status:
            print('{0}'.format(''.join(r)))

    def show_situation(self):
        print(' | 01234567')
        print('-----------')
        for i, r in enumerate(self.situation):
            print('{0}| {1}'.format(i, ''.join(r)))

    def put_queen(self, pos):
        if pos not in self.queen_pos:
            y, x = pos
            
            if self.situation[y][x] != '.':
                return False
            self.status[y][x] = 'Q'
            self.queen_pos.append(pos)
            self.update_situation()
            return True
        else:
            
            return False

    def remove_queen(self, pos):
        if pos in self.queen_pos:
            y, x = pos
            self.status[y][x] = '.'
            self.queen_pos.remove(pos)
            self.update_situation()
            return True
        else:
            
            return False

    def update_status(self):
        self.status = []  
        for i in range(8):
            self.status.append(['.'] * 8)
        for y, x in self.queen_pos:
            self.status[y][x] = 'Q'


    def update_situation(self):
        self.situation = []  
        for i in range(8):
            self.situation.append(['.'] * 8)
        
        for y, x in self.queen_pos:
            
            for i in range(8):  
                self.situation[y][i] = 'x'
            for i in range(8):  
                self.situation[i][x] = 'x'
            i = 1
            while y - i >= 0 and x - i >=0:  
                self.situation[y - i][x - i] = 'x'
                i += 1
            i = 1
            while y + i <= 7 and x + i <= 7:  
                self.situation[y + i][x + i] = 'x'
                i += 1
            i = 1
            while y + i <= 7 and x - i >= 0:  
                self.situation[y + i][x - i] = 'x'
                i += 1
            i = 1
            while y - i >= 0 and x + i <= 7:  
                self.situation[y - i][x + i] = 'x'
                i += 1
        
        for y, x in self.queen_pos:
            self.situation[y][x] = 'Q'

    def is_available(self, pos):
        y, x = pos
        if self.situation[y][x] == '.':
            return True
        else:
            return False

    def get_availability(self):
        
        results = []  
        for y in range(8):
            available = []  
            for x in range(8):
                if self.situation[y][x] == '.':
                    available.append((y, x))
            if available:  
                results.append(available)
        return results

    def get_empty_row(self):
        available = list(range(0, 8))
        for y, x in self.queen_pos:
            available.remove(y)
        return available

    def get_empty_col(self):
        available = list(range(0, 8))
        for y, x in self.queen_pos:
            available.remove(x)
        return available



if __name__ == '__main__':
    
    b = Board()
    init_pos = []
    num = int(input())
    for i in range(num):
        init_pos.append([int(x) for x in input().split(' ')])
    for y, x in init_pos:
        b.put_queen((y, x))

    results = b.get_availability()
    combi = product(*results)
    for p in combi:
        found = True
        for pos in p:
            result = b.put_queen(pos)
            if result == False:
                found = False
                b.clear()
                for p in init_pos:
                    b.put_queen(p)
                break
        if found is True:
            b.update_status()
            b.show_status()

Solution (Python):



"""
input:
2
2 2
5 3

output:
......Q.
Q.......
..Q.....
.......Q
.....Q..
...Q....
.Q......
....Q...
"""

import sys

N = 8
FREE, NOT_FREE = -1, 1


def generate_board(_q_list):
    for queen in _q_list:
        x, y = map(int, queen)
        init_q_check[x][y] = True

    return init_q_check


def print_board():
    for i in range(N):
        for j in range(N):
            if q_check[i][j]:
                if row[i] != j:
                    return None
    for i in range(N):
        line = []
        for j in range(N):
            if row[i] == j:
                line.append('Q')
            else:
                line.append('.')
        print(*line, sep='')

    return None


def recursive(i):
    if i == N:
        print_board()
        return None

    for j in range(N):
        if ((col[j] is NOT_FREE) or
                (dpos[i + j] is NOT_FREE) or
                (dneg[i - j + N - 1] is NOT_FREE)):
            continue

        row[i] = j
        col[j] = dpos[i + j] = dneg[i - j + N - 1] = NOT_FREE

        recursive(i + 1)

        row[i] = col[j] = dpos[i + j] = dneg[i - j + N - 1] = FREE

    return q_check


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    q_num = int(_input[0])
    q_list = map(lambda x: x.split(), _input[1:])

    
    row, col = ([FREE] * N for _ in range(2))
    dpos, dneg = ([FREE] * (2 * N - 1) for _ in range(2))

    init_q_check = [[False] * N for _ in range(N)]
    q_check = generate_board(q_list)

    ans = recursive(0)

Solution (Python):



"""
input:
2
2 2
5 3

output:
......Q.
Q.......
..Q.....
.......Q
.....Q..
...Q....
.Q......
....Q...
"""

import sys

N = 8
FREE, NOT_FREE = -1, 1


def generate_board(_q_list):
    for queen in _q_list:
        x, y = map(int, queen)
        init_q_check[x][y] = True

    return init_q_check


def print_board():
    for i in range(N):
        for j in range(N):
            if q_check[i][j]:
                if row[i] != j:
                    return None

    for i in range(N):
        print(''.join(('Q' if row[i] == j else '.' for j in range(N))))

    return None


def recursive(i):
    if i == N:
        print_board()
        return None

    for j in range(N):
        if ((col[j] is NOT_FREE) or
                (dpos[i + j] is NOT_FREE) or
                (dneg[i - j + N - 1] is NOT_FREE)):
            continue

        row[i] = j
        col[j] = dpos[i + j] = dneg[i - j + N - 1] = NOT_FREE

        recursive(i + 1)

        row[i] = col[j] = dpos[i + j] = dneg[i - j + N - 1] = FREE

    return q_check


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    q_num = int(_input[0])
    q_list = map(lambda x: x.split(), _input[1:])

    
    row, col = ([FREE] * N for _ in range(2))
    dpos, dneg = ([FREE] * (2 * N - 1) for _ in range(2))

    init_q_check = [[False] * N for _ in range(N)]
    q_check = generate_board(q_list)

    ans = recursive(0)

Solution (Python):
from itertools import permutations as per
def check(queen):
    for r1, c1 in queen:
        if not all((r1 == r2 and c1 == c2) or (r1 + c1 != r2 + c2 and r1 - c1 != r2 - c2) for r2, c2 in queen):
            return False
    return True

k = int(input())
R, C = [i for i  in range(8)],[i for i in range(8)]
q = []
for _ in range(k):
    r, c = map(int, input().split())
    q.append((r, c))
    R.remove(r)
    C.remove(c)
for l in per(C):
    q_tmp = q[:]
    for r, c in zip(R, l):
        q_tmp.append((r, c))
    if check(q_tmp):
        for r in range(8):
            print(''.join('Q' if (r, c) in q_tmp else '.' for c in range(8)) )
        break

Solution (Python):
from sys import stdin
N = 8
FREE = -1
NOT_FREE = 1
row = [FREE] * N
col = [FREE] * N
dpos = [FREE] * (2 * N - 1)
dneg = [FREE] * (2 * N - 1)
X = [[False] * N for _ in range(N)]
n = int(stdin.readline())
for _ in range(0, n):
    r, c = map(int, stdin.readline().split())
    X[r][c] = True
def printBoard():
    for i in range(0, N):
        for j in range(0, N):
            if X[i][j] != 0 and row[i] != j: return
    for i in range(0, N):
        for j in range(0, N):
            print("Q" if row[i] == j else ".", end="")
        print("")
def recursive(i):
    if i == N:
        printBoard()
        return
    for j in range(0, N):
        if (NOT_FREE == col[j] or
            NOT_FREE == dpos[i + j] or
            NOT_FREE == dneg[i - j + N - 1]): continue
        row[i] = j
        col[j] = dpos[i + j] = dneg[i - j + N - 1] = NOT_FREE
        recursive(i + 1)
        row[i] = col[j] = dpos[i + j] = dneg[i - j + N - 1] = FREE
recursive(0)

Solution (Python):
from sys import stdin
N = 8
FREE = -1
NOT_FREE = 1
row = [FREE] * N
col = [FREE] * N
dpos = [FREE] * (2 * N - 1)
dneg = [FREE] * (2 * N - 1)
X = [[False] * N for _ in range(N)]
n = int(stdin.readline())
for _ in range(0, n):
    r, c = map(int, stdin.readline().split())
    X[r][c] = True
def printBoard():
    for i in range(0, N):
        for j in range(0, N):
            if X[i][j] != 0 and row[i] != j: return
    for i in range(0, N):
        print(''.join(('Q' if row[i] == j else '.' for j in range(N))))
def recursive(i):
    if i == N:
        printBoard()
        return
    for j in range(0, N):
        if (NOT_FREE == col[j] or
            NOT_FREE == dpos[i + j] or
            NOT_FREE == dneg[i - j + N - 1]): continue
        row[i] = j
        col[j] = dpos[i + j] = dneg[i - j + N - 1] = NOT_FREE
        recursive(i + 1)
        row[i] = col[j] = dpos[i + j] = dneg[i - j + N - 1] = FREE
recursive(0)