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):
from itertools import permutations
n=int(input())
q=[list(map(int,input().split())) for _ in range(n)]
l=list(range(8))
Q=list(permutations(l,8))
def OK(s):
    a=list(s)
    b=list(s)
    for i in range(len(s)):
        a[i]-=i
        b[i]+=i
    for i,j in enumerate(a[:-1]):
        if j in a[i+1:]:
            return False
    for i,j in enumerate(b[:-1]):
        if j in b[i+1:]:
            return False
    return True
for i in Q:
    chk=i
    for x,y in q:
        if i[x]!=y:
            chk=[]
            break
    if chk:
        if OK(i):
            A=i
            break
ans=[['.']*8 for _ in range(8)]
for i,j in enumerate(A):
    ans[i][j]='Q'
    print(''.join(map(str,ans[i])))

Solution (Python):
import sys
import itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


k = int(input())
pos = []
for i in range(k):
    x, y = map(int, input().split())
    pos.append((x, y))

N = 8
p = [i for i in range(N)]

def check(qs):
    board = [[0] * 8 for _ in range(8)]
    for q in qs:
        x, y = q
        board[x][y] = 1
    dirs = [(1, 1), (-1, -1), (1, -1), (-1, 1)]
    for q in qs:
        for d in dirs:
            dx, dy = q
            dx += d[0]
            dy += d[1]
            while (dx >= 0 and dy >= 0) and (dx < 8 and dy < 8):
                if board[dx][dy] == 1:
                    return False
                dx += d[0]
                dy += d[1]
    for i in range(8):
        for j in range(8):
            if board[i][j]:
                print("Q", end="")
            else:
                print(".", end="")
        print()
    return True

def perm(start):
    if start == N:
        qs = set((i, p[i]) for i in range(N))
        for x in pos:
            if not x in qs:
                break
        else:
            check(qs)
        return
    
    for i in range(start, N):
        p[i], p[start] = p[start], p[i]
        perm(start + 1)
        p[i], p[start] = p[start], p[i]

perm(0)

Solution (Python):
k=int(input())
l=[]


for _ in range(k):
  l.append(list(map(int, input().split())))
import itertools
for s in itertools.permutations(range(8)):
  t=[]
  for _ in range(8):
    t.append(([s[_], _]))
  for z in l:
    if not (z in t):
      break
  else:
    
    for a in range(7):
      for b in range(a+1, 8): 
        if abs(t[a][0]-t[b][0])==abs(t[a][1]-t[b][1]):
          break
      else:
        continue
      break
    else:
      tt=sorted(t)
      
      for _ in range(8):
        if tt[_][1]==0:
          print("Q.......")
        else:
          print("."*tt[_][1]+"Q"+"."*(7-tt[_][1]))
    continue

Solution (Python):
from itertools import permutations

n = int(input())
li = [list(map(int,input().split())) for _ in range(n)]
chess = [["." for i in range(8)]for j in range(8)]

for i in range(8):
    chess[i][i] = "Q"

point = 0


for patern in permutations(chess):
    for y,x in li:
        if patern[y][x] != "Q":
            break
    else:
        
        ld = [0]*15 
        rd = [0]*15 
        for i in range(8):
            for j in range(8):
                if patern[i][j] == "Q":
                    ld[i+j] += 1
                    rd[i+(7-j)] += 1
        for k in range(15):
            
            if rd[k] > 1 or ld[k] > 1:
                break
        else:
            for l in patern:
                print("".join(l))

Solution (Python):
import copy as cp
N = 8
ans = []

def out(M):
    for i in range(N):
        for j in range(N):
            print(M[i][j], end="")
        print("")
    
def DFS(r,c,dp,dn,qn):
    global ans
    if qn == N:
        for h in range(N):
            for w in range(N):
                if r[h] & c[w] & dp[h+w] & dn[w-h+7]:
                    ans.append([h,w])
                    return True
        return False

    for h in range(N):
        for w in range(N):
            if r[h] & c[w] & dp[h+w] & dn[w-h+7]:
                new_r = cp.deepcopy(r)
                new_c = cp.deepcopy(c)
                new_dp = cp.deepcopy(dp)
                new_dn = cp.deepcopy(dn)
                new_r[h],new_c[w],new_dp[h+w],new_dn[w-h+7] = False,False,False,False
                if DFS(new_r,new_c,new_dp,new_dn,qn+1):
                    ans.append([h,w])
                    return True
    return False


def main():
    row = [True]*N
    col = [True]*N
    dp = [True]*(2*N-1)
    dn = [True]*(2*N-1)
    k = int(input())
    MAP = [["." for _ in range(N)] for __ in range(N)]
    for _ in range(k):
        h,w = map(int,input().split())
        MAP[h][w] = "Q"
        row[h] = False
        col[w] = False
        dp[w+h] = False
        dn[w-h+7] = False
    
    DFS(row,col,dp,dn,k+1)

    
    for h,w in ans:
        MAP[h][w] = "Q"

    out(MAP)

main()

Solution (Python):
import itertools
K = int(input())
RC = [list(map(int,input().split())) for _ in range(K)]
P = list(itertools.permutations([0,1,2,3,4,5,6,7]))
PP = []
for p in P:
    for rc in RC:
        if p[rc[0]] != rc[1]:
            break
    else:
        PP.append(p)
for pp in PP:
    for i in range(8):
        for j in range(1,8):
            if i+j <= 7 and (pp[i]+j == pp[i+j] or pp[i]-j == pp[i+j]):
                break
            if i-j >= 0 and (pp[i]+j == pp[i-j] or pp[i]-j == pp[i-j]):
                break
        else:
            continue
        break
    else:
        ppp = pp
        break
for p in ppp:
    print('.......'[:p] + 'Q' + '.......'[p:])

Solution (Python):



import itertools
import copy

k = int(input())
q_l = [[int(x) for x in input().split()] for y in range(k)]

x_l = list(range(8))
y_l = list(range(8))
plus_l = []
minus_l = []
for i in range(k):
    x_l.remove(q_l[i][1])
    y_l.remove(q_l[i][0])
    plus_l.append(q_l[i][0] + q_l[i][1])
    minus_l.append(q_l[i][0] - q_l[i][1])
    
per = itertools.permutations(x_l)
per2 = itertools.permutations(x_l)

for order in per:
    _p_l = copy.deepcopy(plus_l)
    _m_l = copy.deepcopy(minus_l)
    _x_l = list(order)
    for i,_y in enumerate(y_l):
        _p_l.append(_y + _x_l[i])
        _m_l.append(_y - _x_l[i])
    if len(set(_p_l)) == 8 and len(set(_m_l)) == 8:
        ans_l = [["."]*8 for j in range(8)]
        for j in range(k):
            ans_l[q_l[j][0]][q_l[j][1]] = "Q"
        for j in range(8-k):
            ans_l[y_l[j]][_x_l[j]] = "Q"
        for j in range(8):
            print(*(ans_l[j]), sep="")

Solution (Python):
from itertools import permutations

k = int(input())
rc = [list(map(int, input().split())) for _ in range(k)]

field = [["."] * 8 for _ in range(8)]


column = [i for i in range(8)]

row = [i for i in range(8)]

for r, perm_column in rc:
    column.remove(perm_column)
    row.remove(r)

    field[r][perm_column] = "Q"

dir_r = [1, 1, -1, -1]
dir_c = [1, -1, -1, 1]


def queen_check(field, perm_column):
    for i, j in zip(row, perm_column):
        for dr, dc in zip(dir_r, dir_c):
            r, c = i, j
            while True:
                r += dr
                c += dc

                if r < 0 or r >= 8 or c < 0 or c >= 8:
                    break

                if field[r][c] == "Q":
                    return False

    return True


for perm_column in permutations(column):
    for i, j in zip(row, perm_column):
        field[i][j] = "Q"

    if queen_check(field, perm_column):
        for f in field:
            print("".join(f))
    for i, j in zip(row, perm_column):
        field[i][j] = "."

Solution (Python):
import itertools 
k = int(input())



xy = [-1] * 8
for i in range(k):
  y, x = list(map(int, input().split()))
  xy[y] = x



lis = [x for x in range(8)] 
permutations_lis = itertools.permutations(lis)

asn = [-1] * 8
for one_case in permutations_lis: 
  wrong = 0
  
  for i in range(8):
    if (xy[i] != -1) and (xy[i] != one_case[i]):
      
      wrong = 1
      break
    for j in range(i + 1, 8):
      
      if one_case[i] == one_case[j]:
        wrong = 1
      elif abs(one_case[i] - one_case[j]) == abs(i - j):
        wrong = 1
  if wrong == 0:
    ans = one_case
    

for i in range(8):
  for j in range(8):
    if ans[i] == j:
      print("Q", end = "")
    else:
      print(".", end = "")
  print("")

Solution (Python):
import itertools
k = int(input())
coords = [tuple(map(int, input().split())) for _ in range(k)]

for item in itertools.permutations(range(8)):
    for x, y in coords:
        if item[x] != y:
            break
    else:
        for i, j in enumerate(item):
            for k in range(1, 8):
                if i+k < 8:
                    if item[i+k] == j+k: break
                    if item[i+k] == j-k: break
                if i-k >= 0:
                    if item[i-k] == j+k: break
                    if item[i-k] == j-k: break
            else:
                continue
            break
        else:
            break

for i in range(8):
    print('.' * item[i] + 'Q' + '.' * (7-item[i]))

Solution (Python):
import itertools
queen=[-1]*8
N=int(input())
de=[]
for i in range(N):
    x,y =list(map(int,input().split()))
    de.append(x)
    queen[x]=y
def check(n):
    for y in range(n):
        if crshu(queen[y],y):return False
    return True
def crshu(x,y):
    for y1 in range(y):
        x1=queen[y1]
        if x1-y1==x-y or x1+y1==x+y:return True
    return False
def board():
    king=[]
    for i in range(8):
        king.append([i,queen[i]])
    for i in range(8):
        for j in range(8):
            if [i,j] in king:
                print("Q",end="")
            else:
                print(".",end="")
        print()
    exit()

def search(n,y):
    if n==y:
        if check(8):
            board()
    else:
        if y in de:
            search(n,y+1)
        else:
            for i in range(n):
                if i not in queen :
                    queen[y]=i
                    search(n,y+1)
                    for l in range(y+1,8):
                        if l not in de:
                            queen[l]=-1
search(8,0)

Solution (Python):
import itertools

k = int(input())

area = [["."]*8 for i in range(8)]

X = set(range(8))
Y = set(range(8))
A = set()
B = set()

for i in range(k):
    x, y = map(int, input().split())
    area[x][y] = "Q"

    X.remove(x)
    Y.remove(y)
    A.add(x-y)
    B.add(x+y)
for v in itertools.permutations(Y):
    ok = 1
    A_ = A.copy()
    B_ = B.copy()
    for x, y in zip(X, v):
        if x-y in A_ or x+y in B_:
            ok = 0
            break

        A_.add(x-y)
        B_.add(x+y)
    
    if ok:
        for x, y in zip(X, v):
            area[x][y] = "Q"
        break

for i in range(8):
    print("".join(area[i]))

Solution (Python):
import itertools
K=int(input())
R=[]
C=[]
RCd={}
rflag=[ 0 for _ in range(8) ]
for i in range(K):
  r,c=map(int,input().split())
  R.append(r)
  C.append(c)
  RCd[r]=c
  rflag[r]=1

l=[ i for i in range(8) ]
P=itertools.permutations(l,8)
for p in P:
  p=list(p)
  flag=0
  for i in range(8):
    if rflag[i]==1 and p[i]!=RCd[i]:
      flag=1
      break
    for j in range(8):
      if i==j: continue
      if abs(i-j)==p[i]-p[j]:
        flag=1
        break
  
  if flag==1:continue
  for i in range(8):
    ans='........'
    print(ans[:p[i]]+'Q'+ans[p[i]+1:])
  exit()

Solution (Python):
from itertools import permutations

k = int(input())

points = {tuple(map(int, input().split())) for _ in range(k)}

for perm in permutations(range(8), 8):
    test = {(i, perm[i]) for i in range(8)}
    if test & points == points:
        flg = 0
        for x, y in test:
            diag = {(x - i, y - i) for i in range(1, min(x, y) + 1)} | {(x + i, y + i) for i in range(1, min(7 - x, 7 - y) + 1)} | {(x - i, y + i) for i in range(1, min(x, 7 - y) + 1)} | {(x - i, y + i) for i in range(1, min(7 - x, y) + 1)}
            if diag & test == set():
                flg += 1
        if flg == 8:
            ans = test
            break

for i in range(8):
    col = ""
    for j in range(8):
        if (i,j) in ans:
            col += "Q"
        else:
            col += "."
    print(col)

Solution (Python):
from itertools import permutations

k = int(input())
points = [tuple(map(int, input().split(' '))) for _ in range(k)]

indexes = set(range(8))
xs = indexes - {x for _, x in points}
ys = list(indexes - {y for y, _ in points})

result = None
for x_indexes in permutations(xs):
    selected = set(points)
    for i, x in enumerate(x_indexes):
        y = ys[i]
        for sy, sx in selected:
            if abs(sx - x) == abs(sy - y):
                break
        else:
            selected.add((y, x))
            continue
        break
    else:
        result = selected
        break

rows = []
for _ in range(8):
    row = ['.'] * 8
    rows.append(row)

for y, x in result:
    rows[y][x] = 'Q'

for row in rows:
    print(''.join(row))

Solution (Python):
board = [['
n = int(input())
v1=[0]*8
v2=[0]*8
v3=[0]*16
v4=[0]*16


def dot(y,x):
    for j in range(8):
        board[y][j]='.'
        board[j][x]='.'
    for i in range(1,min(x,y)+1):
        board[y-i][x-i]='.'
    for i in range(1,min(7-x,y)+1):
        board[y-i][x+i]='.'
    for i in range(1,min(x,7-y)+1):
        board[y+i][x-i]='.'
    for i in range(1,min(7-x,7-y)+1):
        board[y+i][x+i]='.'
    board[y][x]='Q'
st=set()
ans=[]

def dfs(now,k,stock):
    if now == 8:
        ans.append(list(stock))
        return stock
    if not li[now]:
        dfs(now+1,k,stock)
    for i in li[now]:
        x,y1,y2=i
        if v2[x]==0 and v3[y1+7]==0 and v4[y2]==0:
            stock.add((now,x))
            v2[x]=1
            v3[y1+7]=1
            v4[y2]=1
            dfs(now+1,k,stock)
            v2[x]=0
            v3[y1+7]=0
            v4[y2]=0
            stock.remove((now,x))

for i in range(n):
    y , x = map(int, input().split())
    dot(y,x)
    v1[y]=1
    v2[x]=1
    v3[y-x+7]=1
    v4[y+x]=1

li=[[]for i in range(8)]
for i in range(8):
    for j in range(8):
        if board[i][j]=='
            li[i].append((j,i-j,j+i))

dfs(0,2,st)

for i in ans[0]:
    y,x=i
    dot(y,x)

for i in board:
    print(''.join(i))

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())


R = list(range(8))
C = list(range(8))


queen = []
for _ in range(N):
    r, c = map(int, input().split())
    queen.append((r, c))
    R.remove(r)
    C.remove(c)


for columns in permutations(C):
    
    tmp_queen = queen[:]
    for r, c in zip(R, columns):
        tmp_queen.append((r, c))
    for r1, c1 in tmp_queen:
        for r2, c2 in tmp_queen:
            if r1 == r2 and c1 == c2:
                continue
            else:
                if r1 == r2 or c1 == c2:
                    break
                if r1 + c1 == r2 + c2 or r1 - c1 == r2 - c2:
                    break
        else:
            continue
        break
    else:
        board = [''.join('Q' if (r, c) in tmp_queen else '.' for c in range(8))
                 for r in range(8)]
        print(*board, sep='\n')
        exit(0)

Solution (Python):


from math import factorial as f

from math import ceil,floor,sqrt


import bisect
import re
import heapq


from copy import deepcopy
import itertools
from itertools import permutations

from sys import exit

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))


yes = "Yes"
no = "No"




def main():
    n = ii()
    donelist = []
    for i in range(n):
        tmp = li()
        donelist.append(tmp)

    anslist = [['.' for i in range(8)] for j in range(8)]


    for i in permutations(range(8)):
        lli = list(i)
        flag = False
        for tmp in donelist:
            if lli[tmp[0]] != tmp[1]:
                flag = True
        if flag:
            continue

        wa = []
        sa = []
        for e,tmp in enumerate(lli):
            if (tmp-e in sa) or (tmp+e in wa):
                flag = True
                break
            wa.append(tmp+e)
            sa.append(tmp-e)
        if not flag:
            for e,tmp in enumerate(lli):
                anslist[e][tmp] = 'Q'
                print(''.join(anslist[e]))
            exit()









main()

Solution (Python):
import sys
import itertools


input = sys.stdin.readline


def cannot_attack(Q):
    for i in range(7):
        sx, sy = Q[i]
        for j in range(i+1, 8):
            tx, ty = Q[j]
            if abs(tx-sx) == abs(ty-sy):
                return False
    return True


def include_fq(sq):
    for e in fq:
        if e not in sq:
            return False
    return True


def main():
    Q = []
    for p in itertools.permutations(range(8)):
        Q = [(i, p[i]) for i in range(8)]
        if cannot_attack(Q) and include_fq(set(Q)):
            break
    for y, x in Q:
        print("."*x+"Q"+"."*(7-x))


if __name__ == "__main__":
    K = int(input())
    fq = [tuple(map(int, input().split())) for _ in range(K)]
    main()

Solution (Python):
def putQueen(i):
    while i < 8 and row[i]:i += 1
    if i == 8:
        for i in range(8):
            print(''.join(queen[i]))
    for j in range(8):
        if col[j] or dpos[i+j] or dneg[i-j+7]: continue
        queen[i][j] = 'Q'
        row[i] = col[j] = dpos[i+j] = dneg[i-j+7] = 1
        putQueen(i+1)
        queen[i][j] = '.'
        row[i] = col[j] = dpos[i+j] = dneg[i-j+7] = 0

k = int(input())
row = [0] * 8
col = [0] * 8
dpos = [0] * 15
dneg = [0] * 15
queen = [['.' for j in range(8)] for i in range(8)]

for i in range(k):
    r, c = map(int, input().split())
    row[r] = col[c] = dpos[r+c] = dneg[r-c+7] = 1
    queen[r][c] = 'Q'

putQueen(0)

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

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

X = [[False for _ in range(N)] for _ in range(N)]

def printBoard():
    i,j = 0, 0
    for i in range(N):
        for j in range(N):
            if X[i][j]:
                if row[i] != j: return
    
    for i in range(N):
        for j in range(N):
            print("Q" if row[i]==j else ".", end='')
        print()
            

def recursive(i):
    j = 0

    if i==N:
        printBoard()
    
    else:
        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] = 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

k = int(input())
for _ in range(k):
    r,c = map(int,input().split())
    X[r][c] = True

recursive(0)

Solution (Python):
class eight_Q:
    
    N = 8

    def __init__(self):
        
        self.row = [-1 for _ in range(self.N)]
        self.col = ['Free' for _ in range(self.N)]
        self.dpos = ['Free' for _ in range(self.N*2 -1)]
        self.dneg = ['Free' for _ in range(self.N*2 -1)]
        self.initial = [-1 for _ in range(self.N)]

    def initQueen(self,i,j):
        self.row[i] = j
        self.initial[i] = j
        self.col[j] = 'NotFree'
        self.dpos[i+j] = 'NotFree'
        self.dneg[i-j+(self.N-1)] = 'NotFree'

    def putQueen(self, i):
        for j in range(self.N):
            
            if i == self.N:
                return 'Success'
            if self.initial[i] == j:
                if self.putQueen(i+1) == 'Success':
                    return 'Success'
                else:
                    continue
            if self.col[j] == 'Free' and self.dpos[i+j] == 'Free' and self.dneg[i-j+(self.N-1)] == 'Free':
                
                self.row[i] = j
                self.col[j] = 'NotFree'
                self.dpos[i+j] = 'NotFree'
                self.dneg[i-j+(self.N-1)] = 'NotFree'
                
                if i == self.N-1:
                    return 'Success'
                else:
                    if self.putQueen(i+1) == 'Success':
                        return 'Success'
                    
                    else:
                        self.row[i] = -1
                        self.col[j] = 'Free'
                        self.dpos[i+j] = 'Free'
                        self.dneg[i-j+(self.N-1)] = 'Free'

        return 'Fail'

    def printBoard(self):
        
        for i in range(self.N):
            for j in range(self.N):
                if self.row[i] == j:
                    print("Q",end='')
                elif self.initial[i] == j:
                    print("Q",end='')
                else:
                    print(".",end='')
            print()


if __name__ == "__main__":
    eightQueen = eight_Q()
    k = int(input())

    for i in range(k):
        _i, _j = (int(z) for z in input().split())
        eightQueen.initQueen(_i, _j)
    if eightQueen.putQueen(0) == 'Success':
        eightQueen.printBoard()
        
    else:
        print("Fail to put queen")

Solution (Python):

class EightQueens:
    def __init__(self,p):
        self.p = p
        
        self.N = 8
        
        
        self.row = [None] * 8
        
        self.col = ['FREE'] * 8
        
        
        self.dpos = ['FREE'] * 15
        self.dneg = ['FREE'] * 15

        
        i = 0
        while i < len(p):
            self.row[p[i][0]] = p[i][1]
            self.col[p[i][1]] = self.dpos[p[i][0] + p[i][1]] = self.dneg[p[i][0] - p[i][1] + self.N - 1] = 'NOT_FREE'
            i = i + 1


        

    """
    盤面の状態を表示
    """
    def printBoard(self):
        i = 0
        while i < self.N:
            j = 0
            while j < self.N:
                if j == self.row[i]:
                    print("Q", end="")
                
                    
                else:
                    print(".", end="")
                    
                j = j + 1
            print()
            i = i + 1
        return

    def putQueen(self,i):
        N = self.N

        
        k = 0
        while k < len(self.p):
            if i == self.p[k][0]:
                i = i + 1
                k = 0
            k = k + 1


        
        if i == N:
            
            self.printBoard()
            return

        j = 0
        while j < N :
            
            

            
            if self.col[j] == 'NOT_FREE' or self.dpos[i+j] == 'NOT_FREE' or self.dneg[i-j + N-1] == 'NOT_FREE':
                
                j = j + 1
                continue

            
            self.row[i] = j

            
            self.col[j] = self.dpos[i+j] = self.dneg[i-j+N-1] = 'NOT_FREE'
            
            self.putQueen(i+1)
            
            self.col[j] = self.dpos[i+j] = self.dneg[i-j+N-1] = 'FREE'
            j = j + 1
        return





def main():
    p = []  
    
    k = int(input())
    i = 0
    while i < k:
        try:
            p.append(list(map(int, input().split())))
            i = i + 1
        except:
            break;

    
    
    p.sort()
    q = EightQueens(p)
    q.putQueen(0)
    return






if __name__ == '__main__':
    main()

Solution (Python):
import sys


def print_board(board):
    for i in range(n):
        for j in range(n):
            if board[i][j] and row[i] != j:
                return
    for i in range(n):
        for j in range(n):
            if row[i] == j:
                print('Q', end='')
            else:
                print('.', end='')
        print('')

def set_queen(i, j):
    row[i] = j
    col[j] = NOT_FREE
    dpos[i+j] = NOT_FREE
    dneg[i-j+n-1] = NOT_FREE

def remove_queen(i, j):
    row[i] = FREE
    col[j] = FREE
    dpos[i+j] = FREE
    dneg[i-j+n-1] = FREE

def recursive(i):
    if i == n:
        print_board(board)
        return
    for j in range(n):
        if col[j] == NOT_FREE or dpos[i+j] == NOT_FREE or dneg[i-j+n-1] == NOT_FREE:
            continue
        set_queen(i, j)
        recursive(i+1)
        
        remove_queen(i, j)
    


n = 8
FREE = -1
NOT_FREE = 1

col = []
row = []
dpos = []
dneg = []
board = [[False] * n for i in range(n)]

for i in range(n):
    col.append(FREE)
    row.append(FREE)
for i in range(2 * n - 1):
    dpos.append(FREE)
    dneg.append(FREE)

k = int(input())
for i in range(k):
    r, c = map(int, input().split())
    board[r][c] = True

recursive(0)

Solution (Python):
import itertools
def I(): return int(input())
def LI(): return list(map(int,input().split()))
k = I()
rc = [LI() for _ in range(k)]
for a in itertools.permutations(range(8)):
    XY = [[x,y] for x,y in enumerate(a)]
    if len(set([x+y for x,y in XY])) !=8 or len(set([x-y for x,y in XY])) !=8:
        continue
    count = 0
    for r,c in rc:
        if [r,c] in XY:
            count += 1
    if count !=k:
        continue
    board = [['.' for _ in range(8)] for _ in range(8)]
    for x,y in XY:
        board[x][y] = 'Q'
    break
for b in board:
    print(*b,sep='')

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

board_size = 8
board = [[ '.' for _ in range(board_size)] for _ in range(board_size)]

def print_board(board):
    for bb in board:
        line = ""
        for b in bb:
            line = line + b
        print(line)



Q_list = list()
for _ in range(N):
 Q_list.append(tuple(map(int, input().split() )) )


skip_raws = list()
for (r,c) in Q_list:
    board[r][c] = "Q"
    skip_raws.append(r)


def is_enable_put(r, c, board):
    ok = True
    
    for i in range(board_size):
        
        if board[r][i] == "Q" and i != c:
            ok = False
            break
        
        if board[i][c] == "Q" and i != r:
            ok = False
            break
        
        if i > 0:
            if r-i >= 0 and c-i >= 0 \
            and board[r-i][c-i] == "Q":
                ok = False
                break
            if i+r < board_size and i+c < board_size \
            and board[i+r][i+c] == "Q":
                ok = False
                break
            if r-i >= 0 and c+i < board_size \
            and board[r-i][c+i] == "Q":
                ok = False
                break
            if r+i < board_size and c-i >= 0 \
            and board[r+i][c-i] == "Q":
                ok = False
                break
    return ok

import copy
def queen(r, qboard):
    
    
    if r == board_size:
        print_board(qboard)
        return
    elif r in skip_raws:
        queen(r+1,qboard)
        return

    else:
        for c in range(board_size):
            if is_enable_put(r, c, qboard) == False: continue
            else:
                tmp_board = copy.deepcopy(qboard)
                tmp_board[r][c] = "Q"
                queen(r+1, tmp_board)

queen(0,board)

Solution (Python):
k = int(input())
q = [list(map(int, input().split())) for _ in range(k)]
import itertools

row = list(range(0,8))
for i in q:
    row.remove(i[0])
col = list(range(0,8))
for i in q:
    col.remove(i[1])

for i in itertools.permutations(list(range(0,8-k)),8-k):
    queens = []
    for j in range(k):
        queens.append(q[j])
    for j in range(8-k):
        queens.append([row[j],col[i[j]]])
    flg = True
    for j in itertools.combinations(queens,2):
        if abs((j[0][0]-j[1][0])/(j[0][1]-j[1][1])) == 1:
            flg = False
    if flg == True:
        break


lit = [[]  for _ in range(8)]
for i in range(8):
    for j in range(8):
        lit[i].append('.')
for i in queens:
    lit[i[0]][i[1]] = 'Q'

for i in range(8): print(''.join(map(str,lit[i])))

Solution (Python):
from itertools import product

def setq(ri,ci,krc):
    for ir in range(8):
        if ir!=ri:
            if krc[ir*8+ci]=="Q":
                return False,krc
            else:
                krc[ir*8+ci]="X"
    for ic in range(8):
        if ic!=ci:
            if krc[ri*8+ic]=="Q":
                return False,krc
            else:
                krc[ri*8+ic]="X"
    for ix in range(-7,7,1):
        ir=ri+ix
        ic=ci+ix
        if 0<=ir and ir<=7 and ir!=ri:
            if 0<=ic and ic<=7 and ic!=ci:
                if krc[ir*8+ic]=="Q":
                    return False,krc
                else:
                    krc[ir*8+ic]="X"
        ir=ri-ix
        ic=ci+ix
        if 0<=ir and ir<=7 and ir!=ri:
            if 0<=ic and ic<=7 and ic!=ci:
                if krc[ir*8+ic]=="Q":
                    return False,krc
                else:
                    krc[ir*8+ic]="X"
    return True,krc

def chki(i,krc):
    krc=[""]*64
    for j in range(8):
        krc[j*8+i[j]]="Q"
        bl,krc=setq(j,i[j],krc)


        if not bl :


            return False


    return True

        
def prk(krc2):
    for i in range(8):
        print(krc2[i*8:(i+1)*8])        
    

icase=0
kr=[[] for i in range(8)]

if icase==0:
    k=int(input())
    krc=[""]*64
    for i in range(k):
        ri,ci=map(int,input().split())
        krc[ri*8+ci]="Q"
        setq(ri,ci,krc)
        kr[ri].append(ci)
elif icase==1:
    k=2
    krc=[""]*64
    ri,ci=2,2
    krc[ri*8+ci]="Q"
    setq(ri,ci,krc)
    kr[ri].append(ci)
    ri,ci=5,3
    krc[ri*8+ci]="Q"
    setq(ri,ci,krc)
    kr[ri].append(ci)
                


icnt=0

for ir in range(8):
    for ic in range(8):
        i=ir*8+ic
        if krc[i]=="":
            kr[ir].append(ic)
            
for i in product(kr[0],kr[1],kr[2],kr[3],kr[4],kr[5],kr[6],kr[7]):
    yn=""
    krc2=[""]*64
    if not chki(i,krc2):
        yn="no"
        continue
    else:
        break
if yn!="no":
    for ir in range(8):
        sti=["."]*8
        sti[i[ir]]="Q" 
        stii="".join(sti)
        print(stii)

Solution (Python):
from itertools import groupby, accumulate, product, permutations, combinations
from copy import copy, deepcopy
def solve():
    k = int(input())
    minus = []
    plus = []
    dic = {}
    for i in range(k):
        r,c = map(int, input().split())
        dic[r] = c
        minus.append(r-c)
        plus.append(r+c)
    for p in permutations(range(8),8):
        mi = copy(minus)
        pl = copy(plus)
        for i in range(8):
            if i in dic:
                if dic[i]!=p[i]:
                    break
                else:
                    continue
            mi.append(i-p[i])
            pl.append(i+p[i])
        else:
            if len(set(mi))==8 and len(set(pl))==8:
                break
    ans = []
    for i in p:
        row = ['.']*8
        row[i] = 'Q'
        ans.append(''.join(row))
    return ans
print(*solve(),sep='\n')