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):
def main():
    import itertools

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

    eight_lis = [x for x in range(8)]
    per_lis = itertools.permutations(eight_lis)



    for test in per_lis:
        
        cnt = 0
        tmp = 0
        for queen_in in cr_lis:
            if test[queen_in[0]] != queen_in[1]:
                cnt += 1
        if cnt > 0:
            continue
        zero_lis_1 = [0 for _ in range(8)]
        zero_lis_2 = [0 for _ in range(8)]
        zero_lis_3 = [0 for _ in range(8)]
        zero_lis_4 = [0 for _ in range(8)]
        zero_lis_5 = [0 for _ in range(8)]
        zero_lis_6 = [0 for _ in range(8)]
        zero_lis_7 = [0 for _ in range(8)]
        zero_lis_8 = [0 for _ in range(8)]

        check_lis = []
        dot_lis_1 = ["." for _ in range(8)]
        dot_lis_2 = ["." for _ in range(8)]
        dot_lis_3 = ["." for _ in range(8)]
        dot_lis_4 = ["." for _ in range(8)]
        dot_lis_5 = ["." for _ in range(8)]
        dot_lis_6 = ["." for _ in range(8)]
        dot_lis_7 = ["." for _ in range(8)]
        dot_lis_8 = ["." for _ in range(8)]


        check_lis.append(zero_lis_1)
        check_lis.append(zero_lis_2)
        check_lis.append(zero_lis_3)
        check_lis.append(zero_lis_4)
        check_lis.append(zero_lis_5)
        check_lis.append(zero_lis_6)
        check_lis.append(zero_lis_7)
        check_lis.append(zero_lis_8)

        ans_lis = []
        ans_lis.append(dot_lis_1)
        ans_lis.append(dot_lis_2)
        ans_lis.append(dot_lis_3)
        ans_lis.append(dot_lis_4)
        ans_lis.append(dot_lis_5)
        ans_lis.append(dot_lis_6)
        ans_lis.append(dot_lis_7)
        ans_lis.append(dot_lis_8)


        retsu = -1
        
        for c in test:
            retsu += 1
            check_lis[c][retsu] = 1
        

        retsu = -1
        for c in test:
            retsu += 1
            cnt_retsu = retsu
            cnt_c = c

            while 7>= cnt_retsu > 0 and 7>= cnt_c > 0: 
                if check_lis[cnt_c - 1][cnt_retsu - 1] == 1:
                    tmp += 1
                cnt_c -= 1
                cnt_retsu -= 1
            cnt_retsu = retsu
            cnt_c = c
            while 0<= cnt_retsu < 7 and 7>= cnt_c > 0: 
                if check_lis[cnt_c - 1][cnt_retsu + 1] == 1:
                    tmp +=1
                cnt_c -= 1
                cnt_retsu += 1
            cnt_retsu = retsu
            cnt_c = c
            while 7 >= cnt_retsu > 0 and 0<= cnt_c < 7: 
                
                if check_lis[cnt_c + 1][cnt_retsu - 1] == 1:
                    tmp += 1
                cnt_c += 1
                cnt_retsu -= 1
            cnt_retsu = retsu
            cnt_c = c
            while 0<= cnt_retsu < 7 and 0<= cnt_c < 7: 
                if check_lis[cnt_c + 1][cnt_retsu + 1] == 1:
                    tmp += 1
                cnt_c += 1
                cnt_retsu += 1
        
        if tmp > 1:
            pass
        else:
            for i in range(8):
                ans_lis[i][test[i]] = "Q"
                for ans in ans_lis[i]:
                    if ans == "Q":
                        pass
                    else:
                        ans = "."
            for ans in ans_lis:
                print(''.join(map(str, ans)))
            exit()




if __name__ == "__main__":
    main()

Solution (Python):

"""
Created on Thu May  7 22:24:11 2020

@author: Kanaru Sato
"""

import itertools
import copy

def setdanger(Map,r,c):
    Map[r][c] == 0
    for i in range(8):
        Map[r][i] = 0
        Map[i][c] = 0
    for i in range(max(r-7,-c),min(r,7-c)+1):
        Map[r-i][c+i] = 0
    for i in range(max(-c,-r),min(7-c,7-r)+1):
        Map[r+i][c+i] = 0

def dfs(i,Map,ans):
    if i == 0:
        return True
    else:
        for pointtuple in itertools.product([i for i in range(8)], repeat=2):
            point = list(pointtuple)
            if Map[point[0]][point[1]]:
                currentMap = copy.deepcopy(Map)
                setdanger(currentMap,point[0],point[1])
                if dfs(i-1,currentMap,ans):
                    ans.append(point)
                    return True
                    break
    
k = int(input())

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

Map = [[1 for i in range(8)] for j in range(8)]
for i in range(k):
    setdanger(Map,ans[i][0],ans[i][1])

dfs(8-k,Map,ans)

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

Solution (Python):
k = int(input())
Qs = [tuple(map(int, input().split())) for _ in range(k)]
from itertools import permutations
Lis = [(i, j) for i in range(8) for j in range(8)]

def dfs(idx, lis):
    if idx==8:
        return lis
    Xs = set([x for x, y in lis])
    Ys = set([y for x, y in lis])
    Dif = set([x-y for x, y in lis])
    xDif = set([(8-x)-y for x, y in lis])
    ans = False
    for i in range(8):
        if i in Xs: continue
        for j in range(8):
            if j in Ys: continue
            if i-j in Dif: continue
            if (8-i)-j in xDif: continue
            lis.append((i, j))
            ans = dfs(idx+1, lis)
            if ans:
                return ans
            lis.pop()
    else:
        return False

chess = [['.']*8 for _ in range(8)]
for x, y in dfs(k, Qs):
    chess[x][y] = 'Q'
for i in range(8):
    print(''.join(chess[i]))

Solution (Python):


















































































































N = int(input())
DEFAULT_TABLE = [False for _ in range(8)]
DEFAULT_UPS = [False for _ in range(15)]
DEFAULT_DOWNS = [False for _ in range(15)]
for i in range(N):
    r,c = list(map(int,input().split()))
    DEFAULT_TABLE[r] = c
    DEFAULT_DOWNS[r-c + 7] = True
    DEFAULT_UPS[r + c] = True


def exclude(data, idx):
    return [x for i, x in enumerate(data) if i not in idx]


def permutationListRecursive(data, r, progress):
    

    if r == 0:
        
        table = DEFAULT_TABLE.copy()
        ups  =DEFAULT_UPS.copy()
        downs = DEFAULT_DOWNS.copy()

        for i,t in enumerate(table):
            if t is False:
                col = progress.pop()
                

                if ups[i+ col] or downs[i- col + 7]:
                    return False
                table[i]=col
                ups[i+col ] = True
                downs[i-col + 7] = True
            else:
                continue
        

        result = table
        return result
    for i in range(len(data)):
        
        res = permutationListRecursive(exclude(data, [i]), r - 1, progress + [data[i]])
        if res:
            return res
data =list(range(8))

for x in DEFAULT_TABLE:
    if x is not False:
        data.remove(x)
res_table= permutationListRecursive(data,len(data),[])

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

Solution (Python):

import itertools







def check(queens):
    for r1, c1 in queens:
        for r2, c2 in queens:
            
            if r1 == r2 and c1 == c2:
                continue
            if (r1 == r2) or (c1 == c2):
                return False
            if abs(r1 - r2) == abs(c1 - c2):
                return False
    return True


k = int(input())
queens = []
row, col = list(range(8)), list(range(8))
for _ in range(k):
    r, c = map(int, input().split())
    queens.append((r, c))
    row.remove(r)
    col.remove(c)


for l in itertools.permutations(col):
    tmp_queens = queens.copy()
    
    for r, c in zip(row, l):
        tmp_queens.append((r, c))
    if check(tmp_queens):
        board = [''.join('Q' if (r, c) in tmp_queens else '.' for c in range(8)) for r in range(8)]
        print(*board, sep='\n')
        break

Solution (Python):
import sys
import copy

k = int(input())


class Chessboard:
    def __init__(self):
        self.row = [True] * 8
        self.col = [True] * 8
        self.dpos = [True] * 15
        self.dneg = [True] * 15
        return

    def put(self, r, c):
        
        self.row[r] = False
        self.col[c] = False
        self.dpos[r + c] = False  
        self.dneg[r + 7 - c] = False  
        return

    def safe(self, r, c):
        
        return self.row[r] and self.col[c] and self.dpos[r + c] and self.dneg[r + 7 - c]

    def is_row(self, r):
        return self.row[r]


board = Chessboard()
ans = [['.'] * 8 for _ in range(8)]
for _ in range(k):
    r, c = map(int, sys.stdin.readline().strip().split())
    board.put(r, c)
    ans[r][c] = 'Q'
final_ans = None


def search(r=0, board=board, ans=ans):
    global final_ans
    if r == 8:  
        final_ans = ans
        return ans
    if not board.is_row(r):
        
        search(r=r+1, board=board, ans=ans)

    for c in range(8):
        board_temp = copy.deepcopy(board)
        ans_temp = copy.deepcopy(ans)
        if board_temp.safe(r, c):
            board_temp.put(r, c)
            ans_temp[r][c] = 'Q'
            search(r=r+1, board=board_temp, ans=ans_temp)
        else:
            continue


ans = search()
for r_ans in final_ans:
    print(''.join(r_ans))

Solution (Python):
import itertools

def check_p(p):
    
    for i in range(8):
        for j in range(i+1, 8):
            if p[j] - j == p[i] - i:
                return 0
    
    
    for i in range(8):
        for j in range(i+1, 8):
            if p[j] + j == p[i] + i:
                return 0

    return 1

def print_p(p):
    for i in range(8):
        q = p[i]
        for j in range(8):
            if j != q:
                print(".", end = "")
            else:
                print("Q", end = "")
    
        print()
    return 0

k = int(input())
put_Q = list()
for i in range(k):
    put_Q.append(list(map(int, input().split())))

board = [["n" for _ in range(8)] for _ in range(8)]

error = 0
for p in itertools.permutations(list(range(8))):
    
    for i in range(k):
        if p[put_Q[i][0]] != put_Q[i][1]:
            error = 1

    if error == 0:
        if check_p(p) == 1:
            print_p(p)
            break
    
    error = 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):


cin = open(0).read().strip().split('\n')
k = int(cin[0])
init_q = [tuple(map(int, a.split(' '))) for a in cin[1:]]

import itertools, copy



init_b = [[0 for _ in range(8)] for _ in range(8)]
for q in init_q:
    init_b[q[0]][q[1]] = 1

def culc_diag(list2d, k=0, r2l=False):
    """正方行列のみ"""
    n = len(list2d)

    ret = 0
    if r2l:
        if k > 0:
            ret = sum(list2d[i][n-1-k-i] for i in range(n-k))
        else:
            ret = sum(list2d[i-k][n-1-i] for i in range(n+k))
    else:
        if k > 0:
            ret = sum(list2d[i][i+k] for i in range(n-k))
        else:
            ret = sum(list2d[i-k][i] for i in range(n+k))

    return ret

for cases in itertools.permutations(range(8)):
    b = copy.deepcopy(init_b)
    for idx, c in enumerate(cases):
        if 1 != sum(b[idx]):
            b[idx][c] = 1

    if all([sum(a) for a in b]):
        t_b = [list(x) for x in zip(*b)]
        if all([sum(a) for a in t_b]):
            flg = True
            for i in range(8):
                if (culc_diag(b, k=i, r2l=False) > 1) or (culc_diag(b, k=i, r2l=True) > 1) or (culc_diag(b, k=-1*i, r2l=False) > 1) or (culc_diag(b, k=-1*i, r2l=True) > 1):
                    flg = False
            if flg:
                for row in b:
                    new_b = []
                    for ad in row:
                        new_b.append('.' if ad == 0 else 'Q')
                    print(''.join(new_b))
                break

Solution (Python):
from itertools import permutations
from copy import deepcopy
board = [["."] * 8 for _ in range(8)]
N = int(input())

def check(r, c, board):
    
    for i in range(8):
        if board[i][c] == "Q": return False
        if board[r][i] == "Q": return False
    for i in range(-8,8):
        if 0 <= i + c < 8 and 0 <= i + r < 8:
            if board[i+r][i+c] == "Q": return False
        if 0 <= c+(-i) < 8 and 0 <= i + r < 8:
            if board[i+r][-i+c] == "Q": return False
    return True

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

def main():
    for p in permutations(range(8)):
        tmp = deepcopy(board)
        for i, v in enumerate(p):
            tmp[i][v] = "Q"
        if not all(tmp[rc[i][0]][rc[i][1]] == "Q" for i in range(N)): continue
        judge = True
        for i, v in enumerate(p):
            tmp[i][v] = "."
            if check(i, v, tmp):
                pass
            else:
                judge = False
                break
            tmp[i][v] = "Q"
        if judge: return tmp
       
tmp = main()
for t in tmp:
    print(''.join("Q" if i == "Q" else "." for i in t))

Solution (Python):


def solve():
    import itertools
    import copy

    K = int(input())
    grid = [[0 for i in range(8)] for j in range(8)]

    def put_queen(grid, r, c):
        for j in range(8):
            grid[r][j] = -1
        for i in range(8):
            grid[i][c] = -1
        
        i, j = r-1, c-1
        while i >= 0 and j >= 0:
            grid[i][j] = -1
            i, j = i-1, j-1
        
        i, j = r+1, c-1
        while i < 8 and j >= 0:
            grid[i][j] = -1
            i, j = i+1, j-1
        
        i, j = r-1, c+1
        while i >= 0 and j < 8:
            grid[i][j] = -1
            i, j = i-1, j+1
        
        i, j = r+1, c+1
        while i < 8 and j < 8 :
            grid[i][j] = -1
            i, j = i+1, j+1
        grid[r][c] = 1


    for i in range(K):
        r, c = list(map(int, input().split()))
        put_queen(grid, r, c)

    
    ps = itertools.permutations([i for i in range(8)], r=8)
    for p in ps:
        ans_grid = copy.deepcopy(grid)
        is_ok = True
        for i in range(8):
            if ans_grid[i][p[i]] == 1:
                continue
            if ans_grid[i][p[i]] == -1:
                is_ok = False
                break
            put_queen(ans_grid, i, p[i])
        if is_ok:
            break

    
    for i in range(8):
        s = ""
        for j in range(8):
            if ans_grid[i][j] == 1:
                s += "Q"
            else:
                s += "."
        print(s)


if __name__ == "__main__":
    solve()

Solution (Python):

import sys

stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip() 


def permutation(ret: list, leftovers: list) -> list:
    if len(leftovers) == 0:
        yield ret
    
    for left in leftovers:
        leftoverscopy = [i for i in leftovers]
        leftoverscopy.remove(left)
        yield from permutation(ret+[left], leftoverscopy)


def canAssign(xs, ys):
    for i in range(7):
        for j in range(i+1,8):
            if abs(xs[i]-xs[j]) == abs(ys[i]-ys[j]):
                return False
    return True


def displayChessboard(xs, ys):
    board = [['.']*8 for i in range(8)]
    for i in range(8):
        board[ys[i]][xs[i]] = 'Q'
    for i in range(8):
        for j in range(8):
            print(board[i][j], end='')
        print()
    return


def main():
    k = ni()
    queens = [na() for _ in range(k)]
    xqueens = []
    yqueens = []
    xs = [x for x in range(8)]
    ys = [y for y in range(8)]
    for queen in queens:
        xs.remove(queen[1])
        ys.remove(queen[0])
        xqueens.append(queen[1])
        yqueens.append(queen[0])
    
    for yspernm in permutation([],ys):
        if canAssign(xqueens+xs, yqueens+yspernm):
            displayChessboard(xqueens+xs, yqueens+yspernm)
            return
    
    print("Can't make chessboard.")
    return


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import permutations

k = int(input())
r = [0] * k; c = [0] * k;
for i in range(k):
    r[i], c[i] = [int(a) for a in input().split()]

r_avail = list(range(8))
c_avail = list(range(8))

for i in range(k):
    r_avail.remove(r[i])
    c_avail.remove(c[i])

cperms = list(permutations(c_avail, 8 - k))

for perm in cperms:
    Q = [(r[i], c[i]) for i in range(k)] + list(zip(r_avail, perm))
    for a in range(8):
        for b in range(a + 1, 8):
            rdiff = Q[a][0] - Q[b][0]
            cdiff = Q[a][1] - Q[b][1]
            if abs(rdiff) == abs(cdiff):
                break 
        else:
            continue
        break
    else: 
        break

ans = [['.' for _ in range(8)] for _ in range(8)]
for i in range(8):
    ans[Q[i][0]][Q[i][1]] = 'Q'

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

Solution (Python):
from itertools import permutations as per
z=int(input())
chk=[]
for i in range(z):
    chk.append([int(i) for i in input().split()])
a=list(range(8))
pera=list(per(a))
k=0
for i in pera:
    st1=set() ; st2=set() ; flag=0
    for j in range(z):
        if i[chk[j][0]]!=chk[j][1]:
            flag=1
            break
    if flag==1: continue
    for j in range(8):
        if i[j]-j not in st1:
            st1.add(i[j]-j)
        else: break
        if i[j]+j not in st2:
            st2.add(i[j]+j)
        else: 
            break
    if len(st1)==8 and len(st2)==8:
        ans=[['.']*8 for i in range(8)]
        for j in range(8):
            ans[j][i[j]]='Q'
        for le in range(8):
            print(''.join(ans[le]))
        break

Solution (Python):
import itertools
p = list(itertools.permutations(range(8)))
n = int(input())
k = [list(map(int,input().split())) for i in range(n)]
for d in p:
    f = True
    for r,c in k:
        if d[r]!=c:
            f = False
    if not f:continue
    for i in range(8):
        for j in range(8):
            if i==j:continue
            if i+d[i]==j+d[j]:
                f = False
            if i-d[i]==j-d[j]:
                f = False
    if f:
        for i in d:
            s = ['.']*8
            s[i]='Q'
            print(''.join(s))

Solution (Python):
from itertools import permutations as per
from copy import deepcopy
k = int(input())
b = [["."]*8 for _ in range(8)]
st = [[False]*8 for _ in range(8)]

def setQueen(r,c):
    if st[r][c]: return False
    for i in range(8):
        st[i][c] = True
        st[r][i] = True
    d = abs(r-c)
    y,x = d,0
    if r < c: y,x = x,y
    for i in range(8-d): st[y+i][x+i] = True
    d = abs(7-r-c)
    y,x = d,0
    if 7-r < c: y,x = x,y
    for i in range(8-d): st[7-y-i][x+i] = True
    b[r][c] = "Q"
    return True

sr = [True]*8
sc = [True]*8
for _ in range(k):
    r,c = map(int,input().split())
    b[r][c] = "Q"
    setQueen(r,c)
    sr[r] = False
    sc[c] = False

row = [i for i in range(8) if sr[i]]
col = [i for i in range(8) if sc[i]] 

tmpb = b
tmpst = st
for p in per(row):
    b = deepcopy(tmpb)
    st = deepcopy(tmpst)
    for r,c in zip(p,col):
        if not setQueen(r,c): break
    else:
        for i in range(8): print("".join(b[i]))
        break

Solution (Python):
from itertools import permutations
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    k,*rc = map(int, read().split())

    tmp = []
    ng_list_add = []
    ng_list_sub = []
    for pattern in permutations(range(8)):
        flag = True
        for r, c in enumerate(pattern):
            if r + c in ng_list_add or r - c in ng_list_sub:
                flag = False
                break
            ng_list_add.append(r+c)
            ng_list_sub.append(r-c)
        if flag:
            tmp.append(pattern)
        ng_list_add = []
        ng_list_sub = []
    
    RC = []
    for r, c in zip(*[iter(rc)]*2):
        RC.append((r, c))

    ans_place = None
    for p in tmp:
        flag = True
        for r, c in RC:
            if p[r] != c:
                flag = False
                break
        if flag:
            ans_place = p
            break

    ans = []
    for i in ans_place:
        line = "." * i + "Q" + "." * (7-i)
        ans.append(line)

    print("\n".join(ans))


if __name__ == "__main__":
    main()

Solution (Python):
vert = [False] * 8
hori = [False] * 8
topright = [False] * (8 * 2 - 1)
topleft = [False] * (8 * 2 - 1)
queens = []
skip_row = []


def put_queen(x, y):
    vert[x] = True
    hori[y] = True
    topright[x + y] = True
    topleft[7 + (x - y)] = True
    queens.append((x, y))


def elim_queen(x, y):
    vert[x] = False
    hori[y] = False
    topright[x + y] = False
    topleft[7 + (x - y)] = False
    queens.remove((x, y))


def is_blank(x, y):
    if not vert[x] and not hori[y] and not topright[x+y] and not topleft[7+(x-y)]:
        return True


def search_blank_in_row(y):
    blanks = []
    for x in range(8):
        if is_blank(x, y):
            blanks.append(x)
    return blanks


def put_queen_in_row(y):
    
    if y == 8:
        return True     
    if y in skip_row:
        return put_queen_in_row(y + 1)   

    for x in search_blank_in_row(y):
        put_queen(x, y)
        if put_queen_in_row(y + 1):
            return True
        else:
            elim_queen(x, y)    
    return False    


def main():
    
    n = int(input())
    for i in range(n):
        x, y = map(int, input().split())
        put_queen(x, y)
        skip_row.append(y)

    
    put_queen_in_row(0)

    
    board = [list('........') for x in range(8)]
    for q_x, q_y in queens:
        board[q_x][q_y] = 'Q'
    [print(''.join(x)) for x in board]
    return


main()

Solution (Python):
from itertools import permutations, product
from copy import deepcopy
k = int(input())
rc = [tuple(map(int, input().split())) for _ in range(k)]

for i in permutations(range(8), 8):
    se = set(rc)
    bitmap = [0]*8
    
    for y,x in enumerate(i):
        bitmap[y] = 128>>x

    flag = False
    for i in se:
        if not (bitmap[i[0]] & 128>>i[1]):
            flag = True
            break
    if flag:
        continue
    left,down,right = 0,0,0
    for i in bitmap:
        if (left | down | right) & i:
            break
        left = (left | i)<<1
        down = down | i
        right = (right | i)>>1
    else:
        for i in bitmap:
            print('{:08b}'.format(i).replace('0','.').replace('1','Q'))

Solution (Python):
import itertools
import math
n = int(input())

placed = []

for i in range(n):
    a = list(map(int,input().split()))
    placed.append(a)

l = list(range(8))
perm = tuple(itertools.permutations(l))

for v in perm:
    flag = True
    
    for j in range(len(placed)):
        if v[placed[j][0]] != placed[j][1]:
            flag = False
            break 
    if flag == False:
        continue
    for i in range(8):
        k = 1
        
        while  i+k<=7:
            
            if i+k<=7:
                
                if v[i+k] == v[i]+k or v[i+k] == v[i]-k:
                    flag = False
                    break
                
                
                
            k += 1
        if flag == False:
            break
            
    if flag == True:
        
        for r in range(8):
            for c in range(8):
                if c == v[r]:
                    print("Q",end = "")
                else:
                    print(".",end = "")
            print("")
                
        break

Solution (Python):


from itertools import permutations

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



def create_square(queens):
    square = [['.' for col in range(8)] for row in range(8)]
    for r, c in queens:
        square[r][c] = 'Q'
    return square


def print_square(square):
    for row in range(8):
        for col in range(8):
            print(square[row][col], end='')
        print('')


def includes(queens, queens_input):
    for q in queens_input:
        if q not in queens:
            return False
    return True


def calc_direction(queen):
    row, col = queen
    v, h, d_r, d_l = [], [], [[row, col]], [[row, col]]
    for i in range(8):
        v.append([i, col])
        h.append([row, i])
    for i in range(1, 8):
        if row - i >= 0 and col + i < 8:
            d_r.append([row - i, col + i])
        if row + i < 8 and col - i >= 0:
            d_r.append([row + i, col - i])
        if row - i >= 0 and col - i >= 0:
            d_l.append([row - i, col - i])
        if row + i < 8 and col + i < 8:
            d_l.append([row + i, col + i])
    return v, h, d_r, d_l


def count(direction, queens):
    res = 0
    for queen in queens:
        res += direction.count(queen)
    return res


def is_valid(queens):
    for queen in queens:
        v, h, d_r, d_l = calc_direction(queen)
        v_c, h_c = count(v, queens), count(h, queens)
        d_r_c, d_l_c = count(d_r, queens), count(d_l, queens)
        if not (v_c == 1 and h_c == 1 and d_r_c == 1 and d_l_c == 1):
            return False
    return True


perms = list(map(list, permutations(list(range(8)), 8)))
for perm in perms:
    queens = []
    for row in range(8):
        queens.append([row, perm[row]])
    if includes(queens, queens_input):
        if is_valid(queens):
            
            square = create_square(queens)
            print_square(square)
            break

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



start_exists = [[] for _ in range(8)]
exists_rows = []
for _ in range(k):
    r, c = map(int, input().split())
    exists_rows.append(r)
    start_exists[r].append(c)




def check_valid_positions(exist_positions):
    valid = True
    for start_position in exist_positions:
        for check_position in exist_positions:
            if start_position == check_position:
                continue
            if start_position[0] == check_position[0]:
                valid = False
            if start_position[1] == check_position[1]:
                valid = False
            if (start_position[0] - start_position[1]) == (check_position[0] - check_position[1]):
                valid = False
            if (start_position[0] + start_position[1]) == (check_position[0] + check_position[1]):
                valid = False
    return valid




queens_row_permutations = permutations(range(8))
ans = []
for queens_row_permutation in queens_row_permutations:
    exist_positions = []
    for i, row in enumerate(queens_row_permutation):
        if i in exists_rows:
            exist_positions.append([i, start_exists[i][0]])
        else:
            exist_positions.append([i, row])
    
    
    if check_valid_positions(exist_positions):
        ans = exist_positions
        break
    
    
    
    
    
    
    
for position in ans:
    print(
        ''.join(['Q' if position[1] == i else '.' for i in range(8)]))

Solution (Python):
from copy import copy,deepcopy
import itertools
k=int(input())
b=[['.']*8 for i in range(8)]
R=set(range(8))
C=set(range(8))
p=set()
m=set()
for i in range(k):
    r,c=map(int,input().split())
    b[r][c]='Q'
    R.remove(r);C.remove(c)
    p.add(r+c)
    m.add(r-c)
for x in itertools.permutations(C):
    P=p.copy()
    M=m.copy()
    ok=True
    for r,c in zip(R,x):
        if r+c in P:
            ok=0
        P.add(r+c)
        if r-c in M:
            ok=0
        M.add(r-c)
    if(ok):
        for r,c in zip(R,x):
            b[r][c]='Q'
        break
for i in range(8):
    print(''.join(b[i]))