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
NOTFREE_ = 1
row = [FREE_ for i in range(N_)]
col = [FREE_ for i in range(N_)]
dpos = [FREE_ for i in range(2*N_-1)]
dneg = [FREE_ for i in range(2*N_-1)]
X = [[False for i in range(N_)] for j in range(N_)]

def output():
    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_):
            if row[i] == j:
                print('Q', end='')
            else:
                print('.', end='')
        print()

def recursive(i):
    if i == N_:
        output()
        return

    for j in range(N_):
        if col[j] == NOTFREE_ or dpos[i + j] == NOTFREE_ or dneg[i - j + N_ - 1] == NOTFREE_:
            continue
        row[i] = j
        col[j] = dpos[i + j] = dneg[i - j + N_ - 1] = NOTFREE_
        recursive(i + 1)
        row[i] = col[j] = dpos[i + j] = dneg[i - j + N_ - 1] = FREE_

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

recursive(0)

Solution (Python):

N = 8 
n = int(input())

raw = [-1 for i in range(N)]
col = [0 for i in range(N)] 
dpos = [0 for i in range(2*N-1)] 
dneg = [0 for i in range(2*N-1)] 


def put_queen(i):
	if i == N:
		return True
	elif raw[i] != -1:
		if put_queen(i+1):
			return True
		else :
			return False
	else:
		for j in range(N):
			if col[j] == 1 or dpos[i+j] == 1 or dneg[i-j+N-1] == 1:
				continue
			raw[i] = j
			col[j] = dpos[i+j] = dneg[i-j+N-1] = 1
			if put_queen(i+1):
				return True
			else :
				raw[i] = -1
				col[j] = dpos[i+j] = dneg[i-j+N-1] = 0
		return False


def output_result():
	for i in range(N):
		out_raw = ['.' for i in range(N)]
		out_raw[raw[i]] = 'Q'
		print(''.join(map(str, out_raw)))


for i in range(n):
	r, c = map(int, input().split())
	raw[r] = c
	col[c] = dpos[r+c] = dneg[r-c+N-1] = 1

put_queen(0)
output_result()

Solution (Python):
N = 8


def putQueen(i):
    if i == N:
        printBoard()
        return

    if i in default:
        putQueen(i+1)

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

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

            putQueen(i+1)

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


def printBoard():
    for i in range(N):

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

        print(line)


if(__name__ == '__main__'):
    row  = [None] * N
    col  = [False] * N
    dpos = [False] * (2*N - 1)
    dneg = [False] * (2*N - 1)

    default = []

    n = int(input())

    for _ in range(n):
        r, c = [int(i) for i in input().split()]

        row[r] = c
        col[c] = dpos[r+c] = dneg[r-c+N-1] = True

        default.append(r)

    putQueen(0)

Solution (Python):
from enum import Enum, auto
class Square(Enum):
    FREE = auto()
    NOT_FREE = auto()

row = [Square.FREE for i in range(8)]
col = [Square.FREE for i in range(8)]
dpos = [Square.FREE for i in range(2*8-1)]
dneg = [Square.FREE for i in range(2*8-1)]

board = [[False for j in range(8)] for i in range(8)]

def set_board(r, c, v=True):
    global board
    if v:
        board[r][c] = True
        row[r] = Square.NOT_FREE
        col[c] = Square.NOT_FREE
        dpos[r+c] = Square.NOT_FREE
        dneg[r-c+8-1] = Square.NOT_FREE
    else:
        board[r][c] = False
        row[r] = Square.FREE
        col[c] = Square.FREE
        dpos[r+c] = Square.FREE
        dneg[r-c+8-1] = Square.FREE

def print_board():
    for i in range(8):
        for j in range(8):
            if board[i][j]:
                print('Q', end='')
            else:
                print('.', end='')
        print('')

def recursive(i): 
    global board, row, col, dpos, dneg
    if i == 8:
        print_board()
        return None

    if row[i] == Square.NOT_FREE:
        recursive(i+1)
    else:
        for j in range(8):
            if col[j] == Square.NOT_FREE or dpos[i+j] == Square.NOT_FREE or dneg[i-j+8-1] == Square.NOT_FREE:
                continue
            set_board(i, j, True)
            recursive(i+1)
            set_board(i, j, False)

k = int(input())
for i in range(k):
    r, c = list(map(int, input().split(' ')))
    set_board(r, c, True)
recursive(0)

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

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

def update(r, c, FREE_OR_NOT):
    B[r][c] = "." if FREE_OR_NOT == FREE else "Q"
    row[r] = col[c] = dpos[r + c] = dneg[r - c + N - 1] = FREE_OR_NOT

def draw():
    for i in range(N):
        print("".join(B[i]))

def recursive(i):
    if i == N:
        draw()
        return
    if "Q" in B[i]:
        recursive(i + 1)

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

k = int(input())

for _ in range(k):
    r, c = map(int, input().split())
    update(r, c, NOT_FREE)
recursive(0)

Solution (Python):
def queenprint() :
    global x
    global col
    global row
    global k
    global maxx
    
    for i in range(maxx):
        for j in range(maxx):
            if x[i][j] and row[i] != j:
                return
       
    for i in range(maxx):
        for j in range(maxx):
            if row[i]==j: 
                print('Q',end='')
            else:
                print('.',end='')
        print()
        
def recursive(i):
    global x
    global col
    global row
    global k
    global maxx
    
    if (i == maxx) :
        queenprint()
        return
    
    for j in range(maxx):
        
        if (col[j] or dpos[i + j] or dneg[i - j + maxx - 1]):
            continue
        
        row[i] = j 
        col[j] = dpos[i + j] = dneg[i - j + maxx - 1] = 1;
        recursive(i + 1);
        
        row[i] = col[j] = dpos[i + j] = dneg[i - j + maxx - 1] = 0

maxx = 8    
k=int(input())
x=[[ 0 for i in range(maxx)] for j in range(maxx)]
col=[0 for i in range(maxx)]
row=[0 for i in range(maxx)]
dpos=[0 for i in range(maxx * 2 - 1)]
dneg=[0 for i in range(maxx * 2 - 1)]
      
for i in range(k):
    r,c=[int(x) for x in input().split()]
    x[r][c] = 1
   
recursive(0)

Solution (Python):
from copy import deepcopy


class EightQueen:
    NQUEENS = 8
    SIZE = 8

    class Board:
        def __init__(self, size):
            self.queens = []
            self.size = size

        def place(self, i, j):
            self.queens.append((i, j))

        def count(self):
            return len(self.queens)

        def ok(self, i, j):
            for qi, qj in self.queens:
                if qi == i:
                    return False
                if qj == j:
                    return False
                if i - j == qi - qj:
                    return False
                if i + j == qi + qj:
                    return False
            return True

        def __str__(self):
            result = []
            for i in range(self.size):
                s = ''
                for j in range(self.size):
                    if (i, j) in self.queens:
                        s += "Q"
                    else:
                        s += "."
                result.append(s)
            return '\n'.join(result)

    def __init__(self):
        self.board = self.Board(self.SIZE)

    def add_queen(self, i, j):
        self.board.place(i, j)

    def solve(self):
        def _solve(board, si, sj):
            if board.count() == self.NQUEENS:
                return board

            for i, j in _from_pos(si, sj):
                if board.ok(i, j):
                    b = deepcopy(board)
                    b.place(i, j)
                    result = _solve(b, i, j)
                    if result is not None:
                        return result
            else:
                return None

        def _from_pos(i, j):
            for n in range(i*self.SIZE + j, self.SIZE*self.SIZE):
                yield (n // self.SIZE, n % self.SIZE)

        self.board = _solve(self.board, 0, 0)

    def __str__(self):
        if self.board is None:
            return 'no solution'
        else:
            return str(self.board)


def run():
    n = int(input())
    q = EightQueen()

    for _ in range(n):
        i, j = [int(i) for i in input().split()]
        q.add_queen(i, j)

    q.solve()
    print(q)


if __name__ == '__main__':
    run()

Solution (Python):
from itertools import permutations


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


k = int(input())
row, col = list(range(8)), list(range(8))
queen = []
for _ in range(k):
    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):
k = int(input())
row = [1] * 8
col = [1] * 8
dpos = [1] * 15
dneg = [1] * 15
X = [['.' 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] = 0
    X[r][c] = 'Q'

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

Solution (Python):

from collections import namedtuple

position = namedtuple("position","row column")
def input_queens():
    queens = []
    n = int(input())
    for _ in range(n):
        row,column = [int(x) for x in input().split()]
        queens.append(position(row,column))
    return queens

def output_board(queens):
    for r in range(8):
        for c in range(8):
            print("Q" if position(r,c) in queens else ".",end = "")
        print()

def atackable(p,queens):
    return(
        p.row in [q.row for q in queens]
        or p.column in [q.column for q in queens]
        or any([abs(p.row - q.row) == abs(p.column-q.column) for q in queens])
    )


def next_p(p):
    if p.column == 7:
        return position(p.row+1,0)
    else:
        return position(p.row,p.column+1)
def over(p):
    return p.row > 7
    
def all_queens(queens):
    def rec(p,queens):
        if len(queens) == 8:
            return queens
        elif over(p):
            return False
        elif atackable(p,queens):
            return rec(next_p(p),queens)
        else:
            result = rec(position(p.row+1,0),queens+[p])
            return result if result else rec(next_p(p),queens)
    return rec(position(0,0),queens)
    

queens = input_queens()
output_board(all_queens(queens))

Solution (Python):
import copy


def is_vaild(board, i, j):
    if "Q" in board[i]:
        return False

    for k in range(8):
        if board[k][j] == "Q":
            return False

    
    m, n = i - 1, j - 1
    while m >= 0 and n > 0:
        if board[m][n] == "Q":
            return False
        m -= 1
        n -= 1

    
    m, n = i + 1, j - 1
    while m < 8 and n >= 0:
        if board[m][n] == "Q":
            return False
        m += 1
        n -= 1

    
    m, n = i + 1, j + 1
    while m < 8 and n < 8:
        if board[m][n] == "Q":
            return False
        m += 1
        n += 1

    
    m, n = i - 1, j + 1
    while m >= 0 and n < 8:
        if board[m][n] == "Q":
            return False
        m -= 1
        n += 1

    return True


def fill_board(board, i, j):
    if not is_vaild(board, i, j):
        return

    
    for k in range(8):
        board[i][k] = "."

    
    for k in range(8):
        board[k][j] = "."

    
    m, n = i - 1, j - 1
    while m >= 0 and n >= 0:
        board[m][n] = "."
        m -= 1
        n -= 1

    
    m, n = i + 1, j - 1
    while m < 8 and n >= 0:
        board[m][n] = "."
        m += 1
        n -= 1

    
    m, n = i + 1, j + 1
    while m < 8 and n < 8:
        board[m][n] = "."
        m += 1
        n += 1

    
    m, n = i - 1, j + 1
    while m >= 0 and n < 8:
        board[m][n] = "."
        m -= 1
        n += 1

    board[i][j] = "Q"
    return


def helper(board, rem):
    if rem == 0:
        for line in board:
            print("".join(line))
        quit()

    for i in range(8):
        for j in range(8):
            if board[i][j] == "
                _prev = copy.deepcopy(board)
                fill_board(board, i, j)
                helper(board, rem - 1)
                board = _prev  
    return


board = [["

K = int(input())
flag = False
for _ in range(K):
    i, j = [int(i) for i in input().split()]
    if board[i][j] == "
        fill_board(board, i, j)


helper(board, 8 - K)

Solution (Python):
import itertools
import copy

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

bord = [['.']*8 for _ in range(8)]

exclude_num = []
x_list = [i for i in range(8)]
y_list = [i for i in range(8)]

def queen_move(some_list):
    for x,y in some_list:
        
        for i in range(8):
            bord[x][i] = '.'
            bord[i][y] = '.'
        
        cnt = 1    
        while True:
            if x-cnt >= 0 and y-cnt >= 0:
                bord[x-cnt][y-cnt] = '.'
            else:
                break
            cnt += 1
            
        cnt = 1    
        while True:
            if x-cnt >= 0 and y+cnt <= 7:
                bord[x-cnt][y+cnt] = '.'
            else:
                break
            cnt += 1
    
        cnt = 1    
        while True:
            if x+cnt <= 7 and y+cnt <= 7:
                bord[x+cnt][y+cnt] = '.'
            else:
                break
            cnt += 1
    
        cnt = 1    
        while True:
            if x+cnt <= 7 and y-cnt >= 0:
                bord[x+cnt][y-cnt] = '.'
            else:
                break
            cnt += 1

def check_queen(k):
    check = 0
    for i in range(8):
        for j in range(8):
            if bord[i][j] == 'Q':
                check += 1
    if check == k:
        return True
    else:
        return False

queen_move(li)
        
for x,y in li:
    bord[x][y] = 'Q'
    x_list.remove(x)
    y_list.remove(y)
    
bord_original = copy.deepcopy(bord)

for numbers in itertools.permutations(y_list, 8-k):
    cnt = 0
    bord = copy.deepcopy(bord_original)
    for number in numbers:
        tmp_li = [[x_list[cnt], number]]
        queen_move(tmp_li)
        bord[tmp_li[0][0]][tmp_li[0][1]] = 'Q'
        cnt += 1
        if check_queen(k+cnt) == False:
            break
    else:
        for ans in bord:
            print(''.join(ans))
        break

Solution (Python):
from itertools import permutations

n = int(input())
q = [list(map(int, input().split())) for _ in range(n)]
for p in permutations(range(8), 8):
    if all(p[i] == j for i, j in q):
        m = [["."] * 8 for _ in range(8)]
        for i, j in enumerate(p):
            m[i][j] = "Q"
        b = True
        for i, j in enumerate(p):
            for k in range(1, 8):
                if 0 <= i + k < 8 and 0 <= j + k < 8:
                    if m[i + k][j + k] == "Q":
                        break
                if 0 <= i - k < 8 and 0 <= j + k < 8:
                    if m[i - k][j + k] == "Q":
                        break
                if 0 <= i + k < 8 and 0 <= j - k < 8:
                    if m[i + k][j - k] == "Q":
                        break
                if 0 <= i - k < 8 and 0 <= j - k < 8:
                    if m[i - k][j - k] == "Q":
                        break
            else:
                continue
            b = False
            break
        if b:
            for a in m:
                print(*a, sep="")
            exit()

Solution (Python):
from itertools import permutations

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

for x in permutations(range(8)):
    flag = False
    for i in rc:
        if x[i[1]] != i[0]:
            flag = True
            break
    if flag:
        continue
    
    for i in range(7):
        flag = False
        for j in range(i+1, 8):
            if abs(x[i] - x[j]) == abs(i-j):
                flag = True
                break
        if flag:
            break
    if flag:
        continue
    for i in range(8):
        for j in range(8):
            if i == x[j]:
                print('Q', end='')
            else:
                print('.', end='')
        print()
    break

Solution (Python):
def can_put(arr, point):
    for p in arr:
        if p[0] == point[0] or p[1] == point[1] or p[0]-p[1] == point[0]-point[1] or p[0]+p[1] == point[0]+point[1]:
            return False
    return True

K = int(input())
RC = [tuple(map(int,input().split())) for _ in range(K)]
def dfs(arr):
    if len(arr) == 8:
        se = set()
        for a in arr:
            se.add(a)
        for i in range(8):
            for j in range(8):
                if (i,j) in se:
                    print("Q", end="")
                else:
                    print(".", end="")
                if j == 7: print()
        exit()
    for i in range(8):
        for j in range(8):
            if can_put(arr, (i,j)):
                dfs(arr+[(i,j)])
dfs(RC)

Solution (Python):
import sys
from itertools import permutations


def in_board(r, c):
    return 0 <= r < 8 and 0 <= c < 8


def reachable_generator(r, c):
    
    i = 1
    while True:
        if not in_board(r - i, c - i):
            break
        yield r - i, c - i
        i += 1
    i = 1
    while True:
        if not in_board(r + i, c + i):
            break
        yield r + i, c + i
        i += 1
    
    i = 1
    while True:
        if not in_board(r - i, c + i):
            break
        yield r - i, c + i
        i += 1
    i = 1
    while True:
        if not in_board(r + i, c - i):
            break
        yield r + i, c - i
        i += 1


def solve(ini):
    for p in permutations(range(8)):
        s = set()
        for i, j in enumerate(p):
            s.add((i, j))
        if not ini <= s:
            continue
        for i, j in s:
            for k, l in reachable_generator(i, j):
                if (k, l) in s:
                    break
            else:
                continue
            break
        else:
            return s


def main():
    input = sys.stdin.buffer.readline
    k = int(input())
    
    ini = set()
    for _ in range(k):
        r, c = map(int, input().split())
        ini.add((r, c))
    s = solve(ini)

    board = [["."] * 8 for _ in range(8)]
    for i, j in s:
        board[i][j] = "Q"
    for i in range(8):
        print("".join(board[i]))


if __name__ == "__main__":
    main()

Solution (Python):
N=int(input())
L=[[0 for i in range(8)]for j in range(8)]

Q=[]

for i in range(N):
    h,w=map(int,input().split())
    Q.append((h,w))
    
if N==8:
    L=[["." for i in range(8)]for j in range(8)]
    for q in Q:
        
        L[q[0]][q[1]]="Q"
    for h in range(8):
        print("".join(L[h]))
    exit()
    
for i in range(len(Q)):
    H,W=Q[i]
    for j in range(1,8):
        if H+j>=8 or W+j>=8:
            break
        L[H+j][W+j]=1
    for j in range(1,8):
        if H+j>=8 or W-j<0:
            break
        L[H+j][W-j]=1
    for j in range(1,8):
        if W+j>=8 or H-j<0:
            break
        L[H-j][W+j]=1
    for j in range(1,8):
        if H-j<0 or W-j<0:
            break
        L[H-j][W-j]=1
    for j in range(1,8):
        if W+j>=8:
            break
        L[H][W+j]=1
    for j in range(1,8):
        if W-j<0:
            break
        L[H][W-j]=1
    for j in range(1,8):
        if H+j>=8:
            break
        L[H+j][W]=1
    for j in range(1,8):
        if H-j<0:
            break
        L[H-j][W]=1
for i in Q:
    L[i[0]][i[1]]="Q"


    
d=[]
for i in range(8):
    for j in range(8):
        if L[i][j]==0:
            d.append((i,j))

D=[{}for i in range(8)]
D[0][tuple(Q)]=d

import copy
for i in range(1,8-N):
    for k,v in D[i-1].items():
        K=list(k)
        for x in range(len(v)):
            l=[]
            for y in range(x+1,len(v)):
                if x==y:
                    continue
                if abs(v[x][0]-v[y][0])==abs(v[x][1]-v[y][1]) or (v[x][0]-v[y][0])*(v[x][1]-v[y][1])==0:
                    continue
                else:
                    l.append(v[y])
            
            D[i][tuple(K+[v[x]])]=l

for k,v in D[8-N-1].items():
    if len(v)==1:
        
        for i in k:
            L[i[0]][i[1]]="Q"
        L[v[0][0]][v[0][1]]="Q"
        for h in range(8):
            for w in range(8):
                if L[h][w]!="Q":
                    L[h][w]="."
        for h in range(8):
            print("".join(L[h]))
        exit()

Solution (Python):
import copy

dirs = [[-1, -1], [-1, 0], [-1, 1],
        [0, -1], [0, 1],
        [1, -1], [1, 0], [1, 1]]

def place(board, r, c):
    if board[r][c] != '.':
        return False
    board[r][c] = 'Q'
    for d in dirs:
        rr = r + d[0]
        cc = c + d[1]
        while rr >= 0 and rr < 8 and cc >= 0 and cc < 8:
            board[rr][cc] = 'x'
            rr += d[0]
            cc += d[1]
    return True

def solve(board_):
    board = copy.deepcopy(board_)
    for r in range(8):
        for c in range(8):
            if place(board, r, c):
                tmp = solve(board)
                if tmp:
                    return tmp
                else:
                    board = copy.deepcopy(board_)
    if sum([row.count('Q') for row in board]) == 8:
        return board

def disp(board, clean=False):
    for row in board:
        if clean:
            row = ['.' if i == 'x' else i for i in row]
        print(''.join(row))

board = [['.'] * 8 for i in range(8)]
N = int(input())
for _ in range(N):
    r, c = map(int, input().split())
    place(board, r, c)

board = solve(board)

disp(board, True)

Solution (Python):
import copy
import itertools

k=int(input())
pos = [['.' for _ in range(8)] for _ in range(8)]
rows = [i for i in range(8)]
cols = [i for i in range(8)]

for _ in range(k):
    r,c = map(int, input().split())
    pos[r][c] = 'Q'
    rows.remove(r)
    cols.remove(c)

for c in itertools.permutations(cols):

    temp_pos = copy.deepcopy(pos)
    
    for r_i, c_i in zip(rows, c):
        temp_pos[r_i][c_i] = 'Q'
        
    flg = True
    
    for r_i in range(8):
        for c_i in range(8):
            
            if temp_pos[r_i][c_i]=='Q':
                
                next_r,next_c = r_i,c_i
                while 0<=next_r+1<=7 and 0<=next_c+1<=7:
                    next_r+=1
                    next_c+=1
                    if temp_pos[next_r][next_c]=='Q':
                        flg = False
                        break
                    
                next_r,next_c = r_i,c_i
                while 0<=next_r-1<=7 and 0<=next_c+1<=7:
                    next_r-=1
                    next_c+=1
                    if temp_pos[next_r][next_c]=='Q':
                        flg = False
                        break
                
                next_r,next_c = r_i,c_i
                while 0<=next_r-1<=7 and 0<=next_c-1<=7:
                    next_r-=1
                    next_c-=1
                    if temp_pos[next_r][next_c]=='Q':
                        flg = False
                        break
                
                next_r,next_c = r_i,c_i
                while 0<=next_r+1<=7 and 0<=next_c-1<=7:
                    next_r+=1
                    next_c-=1
                    if temp_pos[next_r][next_c]=='Q':
                        flg = False
                        break
                        
            if not flg:
                break
        if not flg:
            break
    if flg:
        break

if flg:
    for rows in temp_pos:
        print(*rows, sep='')

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):
from itertools import permutations

n=int(input())
lst_ini=[list(map(int,input().split())) for _ in range(n)]
row=list(range(8))
col=list(range(8))
for x in lst_ini:
    row.remove(x[0])
    col.remove(x[1])

for x in permutations(col):
    work=lst_ini[:]
    for i in range(8-n):
        work.append([row[i],x[i]])
    
    
    for y in work:
        for i in range(8):
            if y[0]==i: continue
            if [i,y[1]-(y[0]-i)] in work : break
            if [i,y[1]+(y[0]-i)] in work : break
        else : continue
        break
    else : break

for i in range(8):
    out=""
    for j in range(8):
        if [i,j] in work : out+="Q"
        else : out+="."
    print(out)

Solution (Python):
K = int(input())
rc = [list(map(int, input().split())) for i in range(K)]

from itertools import permutations as per

ans = None
for pers in per(range(8)):
    flag = False
    
    for r, c in rc:
        if pers[r] != c:
            break
    else:
        flag = True
    
    for i in range(8):
        for j in range(1, 8):
            if i >= j:
                if pers[i] == pers[i-j]-j or pers[i] == pers[i-j]+j:
                    flag = False
                    break
    if flag:
        ans = pers
        break

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

Solution (Python):
import sys
from itertools import permutations

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    k = int(input())
    RC = [list(map(int, input().split())) for _ in range(k)]

    res = [["."] * 8 for _ in range(8)]
    for pattern in permutations(list(range(8))):
        XY = set(tuple((idx, num) for idx, num in enumerate(pattern)))
        flg = True
        for r, c in RC:
            if (r, c) not in XY:
                flg = False
                break
        if not flg:
            continue

        for x, y in XY:
            for i in range(1, 8):
                if (x + i, y + i) in XY or (x + i, y - i) in XY or (x - i, y + i) in XY or (x - i, y - i) in XY:
                    flg = False
                    break
            else:
                continue
            break
        if flg:
            for x, y in XY:
                res[x][y] = "Q"
            break

    for i in res:
        print("".join(i))


if __name__ == '__main__':
    resolve()

Solution (Python):
import pprint

inp = int(input())
N = 8
board = [ [0]*8 for _ in range(8) ]
defined = []
dic = {}
for _ in range(inp):
  x,y = map(int,input().split())
  board[x][y] = 1
  defined.append(x)
  dic[x] = y

def check(board, row, col):
  for i in range(8):
    if i==col: continue
    if board[row][i] == 1:
      return False

  for i in range(8):
    if i==row: continue
    if board[i][col] == 1:
      return False

  
  for i,j in zip(range(row, -1, -1), range(col, -1, -1)):
    if i==row and j==col: continue
    if board[i][j] == 1:
      return False

  
  for i,j in zip(range(row, N), range(col, -1, -1)):
    if i==row and j==col: continue
    if board[i][j] == 1:
      return False

  
  for i,j in zip(range(row, -1, -1), range(col, N)):
    if i==row and j==col: continue
    if board[i][j] == 1:
      return False

  
  for i,j in zip(range(row, N), range(col, N)):
    if i==row and j==col: continue
    if board[i][j] == 1:
      return False

  return True

def solve(board, row):
  if row >= 8:
    return True

  if row in defined:
    col = dic[row]
    if check(board, row, col):
      if solve(board, row+1):
        return True
  else:
    for col in range(8):
      if check(board, row, col):
        board[row][col] = 1
        if solve(board, row+1):
          return True
        board[row][col] = 0

  return False

solve(board, 0)

for row in board:
  print("".join(["Q" if r==1 else "." for r in row ]))

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

for i in permutations(range(8)):
    if len(set([j+k for j,k in enumerate(i)]))!=8:continue
    if len(set([j-k for j,k in enumerate(i)]))!=8:continue
    flag=1
    for x,y in A:
        if i[x]!=y:flag=0
    if flag:
        for num in i:
            point=["."]*8
            point[num]="Q"
            print("".join(point))

Solution (Python):
import itertools
l = itertools.permutations(range(8))
n = int(input())
r = [0] * n
c = [0] * n
for i in range(n):
    r[i], c[i] = map(int, input().split())
for a in l:
    m = [[0]* 8 for i in range(8)]
    for i in range(8):
        m[i][a[i]] = 1
    ok = 1
    for i in range(n):
        if m[r[i]][c[i]] != 1:
            ok = 0
    for j in range(8):
        if sum([m[i+j][i] for i in range(8-j)])>=2:
            ok = 0
        if sum([m[i][i+j] for i in range(8-j)])>=2:
            ok = 0
        if sum([m[i][j-i] for i in range(j+1)])>=2:
            ok = 0
        if sum([m[7-j+i][7-i] for i in range(j+1)])>=2:
            ok = 0
    if ok:
        for i in range(8):
            print(''.join(['Q' if m[i][j]==1 else '.' for j in range(8)]))