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

Solution (Python):
from sys import stdin
from itertools import permutations as per
def check(queen):
    for r1, c1 in queen:
        if not all((r1 == r2 and c1 == c2) or (r1 + c1 != r2 + c2 and r1 - c1 != r2 - c2) for r2, c2 in queen):
            return False
    return True
k = int(stdin.readline())
R, C = [[i for i in range(8)] for _ in range(2)]
q = []
for _ in range(k):
    r, c = map(int, stdin.readline().split())
    q.append((r, c))
    R.remove(r)
    C.remove(c)
for l in per(C):
    q_tmp = q[:] + [(r, c) for r, c in zip(R, l)]
    if check(q_tmp):
        for i, j in sorted(q_tmp):
            print("." * j + "Q" + "." * (8 - j - 1))
        break

Solution (Python):
from sys import stdin
from itertools import permutations as per
def check(queen):
    for r1, c1 in queen:
        if not all((r1 == r2 and c1 == c2) or (r1 + c1 != r2 + c2 and r1 - c1 != r2 - c2) for r2, c2 in queen):
            return False
    return True
k = int(stdin.readline())
R, C = [[i for i in range(8)] for _ in range(2)]
q = []
for _ in range(k):
    r, c = map(int, stdin.readline().split())
    q.append((r, c))
    R.remove(r)
    C.remove(c)
for l in per(C):
    q_tmp = q[:] + list(zip(R, l))
    if check(q_tmp):
        for i, j in sorted(q_tmp):
            print("." * j + "Q" + "." * (8 - j - 1))
        break

Solution (Python):


class Tree():
    def __init__(self, init_field):
        self.root = init_field

    def search(self, field_id, field):
        global final_queen_pos
        
        
        q_r = rest_row[field_id - n]
        if final_queen_pos:
            return None
        else:
            for q_c, cell in enumerate(field.state[q_r]):
                if cell == 0:
                    if final_queen_pos:
                        break
                    if field_id == 7:
                        field.queen_pos.append([q_r, q_c])
                        final_queen_pos = field.queen_pos
                        break
                    else:
                        next_field = Field(field_id + 1, field)
                        field.children.append(next_field)
                        next_field.update(q_r, q_c)
                        self.search(field_id + 1, next_field)
                else:
                    continue

class Field():
    def __init__(self, field_id, parent=None):
        self.id = field_id
        self.parent = parent
        self.children = []

        if field_id == 0:
            self.state = [[0 for _ in range(W)] for H in range(H)]
            self.queen_pos = []
        else:
            self.state = []
            self.queen_pos = []
            for row in self.parent.state:
                x = row.copy()
                self.state.append(x)
            for parent_queen_pos in self.parent.queen_pos:
                self.queen_pos.append(parent_queen_pos)

    def update(self, q_r, q_c):
        self.queen_pos.append([q_r, q_c])
        for i in range(8):
            self.state[q_r][i] = 1
            self.state[i][q_c] = 1
        summ = q_c + q_r
        diff = q_c - q_r
        for i in range(8):
            if (0 <= i + diff < 8):
                self.state[i][i + diff] = 1
            if (0 <= summ - i < 8):
                self.state[i][summ - i] = 1

    def print_field(self): 
        print("queen_pos:", self.queen_pos)
        for row in self.state:
            print(*row)


H, W = 8, 8
n = int(input())
init_field = Field(0)
tree = Tree(init_field)
field_list = [init_field]
rest_row = [i for i in range(8)]
queen_pos = []
final_queen_pos = None
final_result = [["." for _ in range(8)] for _ in range(8)]

for _ in range(n):
    r, c = map(int, input().split())
    queen_pos.append([r, c])
    rest_row.remove(r)

if n < 8:
    i = 0
    prev_field = init_field
    for q_r, q_c in queen_pos:
        i += 1
        field = Field(i, prev_field)
        field.update(q_r, q_c)
        field_list.append(field)
        prev_field.children = [field]
        prev_field = field

    tree.search(i, field)

    for q_r, q_c in final_queen_pos:
        final_result[q_r][q_c] = "Q"

    for row in final_result:
        print("".join(row), end = "\n")

else:
    for q_r, q_c in queen_pos:
        final_result[q_r][q_c] = "Q"

    for row in final_result:
        print("".join(row), end = "\n")

Solution (Python):


class Tree():
    def __init__(self, init_field):
        self.root = init_field

    def search(self, field_id, field):
        global final_queen_pos
        
        
        q_r = rest_row[field_id - n]
        if final_queen_pos:
            return None
        else:
            for q_c, cell in enumerate(field.state[q_r]):
                if cell == 0:
                    if final_queen_pos:
                        break
                    if field_id == 7:
                        field.queen_pos.append([q_r, q_c])
                        final_queen_pos = field.queen_pos
                        break
                    else:
                        next_field = Field(field_id + 1, field)
                        field.children.append(next_field)
                        next_field.update(q_r, q_c)
                        self.search(field_id + 1, next_field)
                else:
                    continue

class Field():
    def __init__(self, field_id, parent=None):
        self.id = field_id
        self.parent = parent
        self.children = []

        if field_id == 0:
            self.state = [[0 for _ in range(W)] for H in range(H)]
            self.queen_pos = []
        else:
            self.state = []
            self.queen_pos = []
            for row in self.parent.state:
                x = row.copy()
                self.state.append(x)
            for parent_queen_pos in self.parent.queen_pos:
                self.queen_pos.append(parent_queen_pos)

    def update(self, q_r, q_c):
        self.queen_pos.append([q_r, q_c])
        for i in range(8):
            self.state[q_r][i] = 1
            self.state[i][q_c] = 1
        summ = q_c + q_r
        diff = q_c - q_r
        for i in range(8):
            if (0 <= i + diff < 8):
                self.state[i][i + diff] = 1
            if (0 <= summ - i < 8):
                self.state[i][summ - i] = 1

    def print_field(self): 
        print("queen_pos:", self.queen_pos)
        for row in self.state:
            print(*row)


H, W = 8, 8
n = int(input())
init_field = Field(0)
tree = Tree(init_field)
field_list = [init_field]
rest_row = [i for i in range(8)]
queen_pos = []
final_queen_pos = None
final_result = [["." for _ in range(8)] for _ in range(8)]

for _ in range(n):
    r, c = map(int, input().split())
    queen_pos.append([r, c])
    rest_row.remove(r)

if n < 8:
    i = 0
    prev_field = init_field
    for q_r, q_c in queen_pos:
        i += 1
        field = Field(i, prev_field)
        field.update(q_r, q_c)
        field_list.append(field)
        prev_field.children = [field]
        prev_field = field

    tree.search(i, field)

    for q_r, q_c in final_queen_pos:
        final_result[q_r][q_c] = "Q"

    for row in final_result:
        print("".join(row), end = "\n")

else:
    for q_r, q_c in queen_pos:
        final_result[q_r][q_c] = "Q"

    for row in final_result:
        print("".join(row), end = "\n")

Solution (Python):
n = int(raw_input())
N = 8
data = [['.' for i in range(N)] for j in range(N)]
row = [0 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)]
for i in range(n):
    tmp = map(int, raw_input().split())
    data[tmp[0]][tmp[1]] = 'Q'
    row[tmp[0]] = 1; col[tmp[1]] = 1
    dpos[tmp[0]+tmp[1]] = 1
    dneg[tmp[0]-tmp[1]+N-1] = 1
    
def printBoard(dt):
    for i in range(N):
        print ''.join(map(str, dt[i]))
        
def recursive(i, r, l, pos, neg, dt):
    if i == N:
        printBoard(dt)
        return
    if r[i] == 1:
        recursive(i+1, r, l, pos, neg, dt)
        return
    for j in range(N):
        if l[j] == 1 or pos[i+j] == 1 or neg[i-j+N-1] == 1:
            continue
        r[i] = 1; l[j] = 1
        pos[i+j] = 1; neg[i-j+N-1] = 1; dt[i][j] = 'Q'
        recursive(i+1, r, l, pos, neg, dt)
        r[i] = 0;l[j] = 0
        pos[i+j] = 0; neg[i-j+N-1] = 0; dt[i][j] = '.'
recursive(0, row, col, dpos, dneg, data)

Solution (Python):
row = [True] * 8
col = [True] * 8
dpos = [True] * 15
dneg = [True] * 15


board = [['.', '.', '.', '.', '.', '.', '.', '.'] for i in range(8)]

import sys

file_input = sys.stdin

k = int(file_input.readline())

for line in file_input:
    r, c = map(int, line.split())
    row[r] = "INIT"
    col[c] = "INIT"
    dpos[r + c] = False
    dneg[r + (7 - c)] = False
    board[r][c] = 'Q'

def dfs(i = 0):
    if i == 8:
        for line in board:
            print(*line, sep='')
        return
    if row[i] == "INIT":
        dfs(i + 1)
    elif row[i]:
        for j in range(8):
            if col[j] == "INIT":
                pass
            elif col[j] and dpos[i + j] and dneg[i + (7 - j)]:
                row[i] = False
                col[j] = False
                dpos[i + j] = False
                dneg[i + (7 - j)] = False
                board[i][j] = 'Q'
                dfs(i + 1)
                row[i] = True
                col[j] = True
                dpos[i + j] = True
                dneg[i + (7 - j)] = True
                board[i][j] = '.'

dfs()

Solution (Python):
def place(board, x, y, num, answer):
    width = len(board[0])
    r_dx = (x + 1) % width
    r_dy = (y + 1) % width
    for i in range(width - 1):
        board[y][(x + i + 1) % width] += num
        board[(y + i + 1) % width][x] += num
    div = [1,1,-1,-1]
    for i in range(4):
        x_i = div[(0 + i) % 4]
        y_i = div[(1 + i) % 4]
        l_dx = x + x_i
        l_dy = y + y_i
        while l_dx >= 0 and l_dy >= 0 and l_dx < width and l_dy < width:
            board[l_dy][l_dx] += num
            l_dx += x_i
            l_dy += y_i
    board[y][x] += num
    if num == 1:
        answer[y][x] = "Q"
    else:
        answer[y][x] = "."

def track(placed_num, board, answer):
    width = len(board)
    if placed_num == width:
        return True
    for x in range(width):
        for y in range(width):
            if not board[y][x]:
                place(board, x, y, 1, answer)
                if track(placed_num + 1, board, answer):
                    return True
                place(board, x, y, -1, answer)
    return False

board = [[0 for n in range(8)] for m in range(8)]
answer = [["." for n in range(8)] for m in range(8)]
placed_num = int(input())
for _ in range(placed_num):
    y, x = (int(n) for n in input().split(" "))
    place(board, x, y, 1, answer)
track(placed_num, board, answer)
for i in range(8):
    print("".join(answer[i]))

Solution (Python):
import sys

def print_board(board):
    for y in xrange(8):
        for x in xrange(8):
            if x == board[y]:
                sys.stdout.write("Q")
            else:
                sys.stdout.write(".")
        print ""




def check_threat(board, col, row):
    for y in xrange(8):
        if board[y] == col:
            return True

    for y in xrange(8):
        if board[y] < 0:
            continue

        is_on_line = (row - y == col - board[y])
        is_on_line = is_on_line or (row - y == -col + board[y])
        if is_on_line:
            return True

    return False

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


def place(board, row):
    if row == 8:
        print_board(board)
        return

    if board[row] >= 0:
        place(board, row + 1)
        return

    for i in xrange(8):
        if check_threat(board, i, row):
            continue

        board[row] = i
        place(board, row + 1)
        board[row] = -1


def solve():
    board = [-1 for i in xrange(8)]

    num_qs = int(raw_input())
    for _ in xrange(num_qs):
        x, y = map(int, raw_input().split())
        board[x] = y

    place(board, 0)


if __name__ == "__main__":
    solve()

Solution (Python):
n = int(input())
nt = []

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

for i in range(n):
    y, x = map(int, input().split())
    board[y][x] = "Q"
    nt.append(y)

def output():
    for row in board:
        print("".join(row), sep=None)

def check(x, y):
    for i in range(8):
        for j in range(8):
            if i == y and j == x:
                continue
            elif i == y and board[i][j] == "Q":
                return False
            elif j == x and board[i][j] == "Q":
                return False
            elif abs(i-y) == abs(j-x) and board[i][j] == "Q":
                return False
    return True

def dfs(row):
    if row == 8:
        output()
        return
    if row in nt:
        dfs(row+1)
        return

    for i in range(8):
        board[row][i] = "Q"
        if not check(i, row):
            board[row][i] = "."
            continue
        else:
            dfs(row+1)
            board[row][i] = "."


dfs(0)

Solution (Python):
def changeBoard(board, i, j, d):
    n = 8
    for k in range(n):
        board[i][k] += d
        board[k][j] += d
    if i > j:
        for k in range(n - i + j):
            board[k + i - j][k] += d
    else:
        for k in range(n - j + i):
            board[k][k + j - i] += d
    if i + j < n:
        for k in range(i + j):
            board[i + j -k][k] += d
    else:
        for k in range(i + j - n + 1, n):
            board[i + j -k][k] += d

def checkQueen(queen, initial):
    for r in initial.keys():
        if queen[r] != initial[r]:
            return False
    return True

def printQueen(queen):
    for c in queen:
        line = list("........")
        line[c] = "Q"
        print("".join(line))

def setQueen(queen, board, i, initial):
    n = 8
    if i == n:
        if checkQueen(queen, initial):
            printQueen(queen)
        return
    for j in range(n):
        if board[i][j] == 0:
            queen[i] = j
            changeBoard(board, i, j, 1)
            setQueen(queen, board, i + 1, initial)
            changeBoard(board, i, j, -1)

b = [[0 for i in range(8)] for j in range(8)]
q = [-1 for i in range(8)]
q_ini = {}

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

setQueen(q, b, 0, q_ini)

Solution (Python):
from itertools import product
from copy import deepcopy, copy
class QueenMAP():
    def __init__(self):
        self.yoko = set()
        self.tate = set()
        self.naname1 = set()
        self.naname2 = set()
        self.MAP = [["."] * 8 for _ in range(8)]
    def add(self, y, x):
        self.MAP[y][x] = "Q"
        self.yoko.add(y)
        self.tate.add(x)
        self.naname1.add(y - x)
        self.naname2.add(x + y)
    def check(self, y, x):
        if y in self.yoko or x in self.tate or (y - x) in self.naname1 or (x + y) in self.naname2:
            return False
        return True
    def allcheck(self):
        for i in range(8):
            if not "Q" in self.MAP[i]:
                return False
        return True
def nuri(m, a, b):
    for i in range(8):
        m[a][i] = "1"
        m[i][b] = "1"
    if a + b < 8:
        y = a + b
        x = 0
        l = a + b + 1
    else:
        y = 7
        x = a + b - 7
        l = 15 - a - b
    for i in range(l):
        m[y - i][x + i] = "1"
    if a <= b:
        ny = 0
        nx = b - a
        l = 8 - (b + a)
    else:
        ny = a - b
        nx = 0
        l = 8 - (a - b)
    for i in range(l):
        m[ny + i][nx + i] = "1"
    return m
def solve(MAP0, MAP, n):
    dp = [(deepcopy(MAP0), deepcopy(MAP), n)]
    while dp:
        m0, m, cnt = dp.pop()
        if cnt == 8:
            flg = True
            for r in range(8):
                if "".join(map(str, m0[r])).find("0"):
                    flg = False
                    break
            if flg:
                return m
        for i in range(8):
            for j in range(8):
                if m0[i][j] == "0":
                    dp.append((nuri(deepcopy(m0), i, j), deepcopy(m), cnt + 1))
    return m
def MAIN():
    f = lambda M: "\n".join("".join(map(str, m)) for m in M)
    QM = QueenMAP()
    n = int(input())
    for _ in range(n):
        a, b = map(int, input().split())
        QM.add(a, b)
    dp = [(deepcopy(QM), n)]
    while dp:
        Q, cnt = dp.pop()
        if cnt == 8:
            if Q.allcheck():
                print(f(Q.MAP))
                break
            continue
        cnt += 1
        for i in range(8):
            for j in range(8):
                if Q.check(i, j):
                    CQ = deepcopy(Q)
                    CQ.add(i, j)
                    dp.append((CQ, cnt))
MAIN()

Solution (Python):
from itertools import product
from copy import deepcopy, copy
class QueenMAP():
    __slots__ = ["yoko", "tate", "naname1", "naname2", "MAP"]
    def __init__(self):
        self.yoko = set()
        self.tate = set()
        self.naname1 = set()
        self.naname2 = set()
        self.MAP = [["."] * 8 for _ in range(8)]
    def add(self, y, x):
        self.MAP[y][x] = "Q"
        self.yoko.add(y)
        self.tate.add(x)
        self.naname1.add(y - x)
        self.naname2.add(x + y)
    def check(self, y, x):
        if y in self.yoko or x in self.tate or (y - x) in self.naname1 or (x + y) in self.naname2:
            return False
        return True
    def allcheck(self):
        for i in range(8):
            if not "Q" in self.MAP[i]:
                return False
        return True
def MAIN():
    f = lambda M: "\n".join("".join(map(str, m)) for m in M)
    QM = QueenMAP()
    n = int(input())
    for _ in range(n):
        a, b = map(int, input().split())
        QM.add(a, b)
    dp = [(deepcopy(QM), n)]
    while dp:
        Q, cnt = dp.pop()
        if cnt == 8:
            if Q.allcheck():
                print(f(Q.MAP))
                break
            continue
        cnt += 1
        for i in range(8):
            for j in range(8):
                if Q.check(i, j):
                    CQ = deepcopy(Q)
                    CQ.add(i, j)
                    dp.append((CQ, cnt))
MAIN()

Solution (Python):
from copy import deepcopy, copy
class QueenMAP():
    __slots__ = ["yoko", "tate", "naname1", "naname2", "MAP"]
    def __init__(self):
        self.yoko = set()
        self.tate = set()
        self.naname1 = set()
        self.naname2 = set()
        self.MAP = [["."] * 8 for _ in range(8)]
    def add(self, y, x):
        self.MAP[y][x] = "Q"
        self.yoko.add(y)
        self.tate.add(x)
        self.naname1.add(y - x)
        self.naname2.add(x + y)
    def check(self, y, x):
        if x in self.tate or (y - x) in self.naname1 or (x + y) in self.naname2:
            return False
        return True
    def allcheck(self):
        for i in range(8):
            if not "Q" in self.MAP[i]:
                return False
        return True
def MAIN():
    f = lambda M: "\n".join("".join(map(str, m)) for m in M)
    QM = QueenMAP()
    n = int(input())
    for _ in range(n):
        a, b = map(int, input().split())
        QM.add(a, b)
    dp = [(deepcopy(QM), n)]
    while dp:
        Q, cnt = dp.pop()
        if cnt == 8:
            if Q.allcheck():
                print(f(Q.MAP))
                break
            continue
        cnt += 1
        for i in range(8):
            if i in Q.yoko:
                continue
            for j in range(8):
                if Q.check(i, j):
                    CQ = deepcopy(Q)
                    CQ.add(i, j)
                    dp.append((CQ, cnt))
MAIN()

Solution (Python):
from copy import deepcopy, copy
class QueenMAP():
    __slots__ = ["yoko", "tate", "naname1", "naname2", "MAP"]
    def __init__(self):
        self.yoko = set()
        self.tate = set()
        self.naname1 = set()
        self.naname2 = set()
        self.MAP = [["."] * 8 for _ in range(8)]
    def add(self, y, x):
        self.MAP[y][x] = "Q"
        self.yoko.add(y)
        self.tate.add(x)
        self.naname1.add(y - x)
        self.naname2.add(x + y)
    def check(self, y, x):
        if y in self.yoko or x in self.tate or (y - x) in self.naname1 or (x + y) in self.naname2:
            return False
        return True
    def allcheck(self):
        for i in range(8):
            if not "Q" in self.MAP[i]:
                return False
        return True
def MAIN():
    f = lambda M: "\n".join("".join(m) for m in M)
    QM = QueenMAP()
    n = int(input())
    for _ in range(n):
        a, b = map(int, input().split())
        QM.add(a, b)
    dp = [(deepcopy(QM), n)]
    while dp:
        Q, cnt = dp.pop()
        if cnt == 8:
            if Q.allcheck():
                print(f(Q.MAP))
                break
            continue
        cnt += 1
        for i in range(8):
            for j in range(8):
                if Q.check(i, j):
                    CQ = deepcopy(Q)
                    CQ.add(i, j)
                    dp.append((CQ, cnt))
MAIN()

Solution (Python):
from itertools import product
from copy import deepcopy, copy
class QueenMAP():
    __slots__ = ["yoko", "tate", "naname1", "naname2", "MAP"]
    def __init__(self):
        self.yoko = set()
        self.tate = set()
        self.naname1 = set()
        self.naname2 = set()
        self.MAP = [["."] * 8 for _ in range(8)]
    def add(self, y, x):
        self.MAP[y][x] = "Q"
        self.yoko.add(y)
        self.tate.add(x)
        self.naname1.add(y - x)
        self.naname2.add(x + y)
    def check(self, y, x):
        if y in self.yoko or x in self.tate or (y - x) in self.naname1 or (x + y) in self.naname2:
            return False
        return True
    def allcheck(self):
        for i in range(8):
            if not "Q" in self.MAP[i]:
                return False
        return True
    def show(self):
        print("\n".join("".join(m) for m in self.MAP))
def MAIN():
    f = lambda M: "\n".join("".join(m) for m in M)
    QM = QueenMAP()
    n = int(input())
    for _ in range(n):
        a, b = map(int, input().split())
        QM.add(a, b)
    dp = [(deepcopy(QM), n)]
    while dp:
        Q, cnt = dp.pop()
        if cnt == 8:
            if Q.allcheck():
                Q.show()
                break
            continue
        cnt += 1
        for i, j in product(range(8), repeat=2):
            if Q.check(i, j):
                CQ = deepcopy(Q)
                CQ.add(i, j)
                dp.append((CQ, cnt))
MAIN()

Solution (Python):
N = 8
board = [['.'] * N for i in range(N)]
k = int(input())
for i in range(k):
    pos = list(map(int, input().split()))
    board[pos[0]][pos[1]] = 'Q'


def is_safe(board, row, col):
    for i in range(N):
        if board[row][i] == 'Q':
            return False

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

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

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

    return True

def solve(board, col):
    if col >= N:
        return True

    for i in range(N):
        if board[i][col] == 'Q':
            return solve(board, col + 1)
        
    for i in range(N):
        if is_safe(board, i, col):
            board[i][col] = 'Q'
            if solve(board, col + 1):
                return True
            board[i][col] = '.'

    return False


solve(board, 0)
for i in range(N):
    print(''.join(board[i]))

Solution (Python):



if __name__ == '__main__':

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

    k = int(input())
    for _ in range(k):
        i, j = map(int, input().split())
        X[i][j] = "Q"
        row[i] = col[j] = dpos[i + j] = dneg[i - j + N - 1] = NOT_FREE

    def printBoard(X):
        for i in range(N):
            print("".join(X[i]))

    def recursive(i):
        if i == N:
            printBoard(X)
            return
        if "Q" in X[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:
                X[i][j] = "Q"
                row[i] = col[j] = dpos[i + j] = dneg[i - j + N - 1] = NOT_FREE
            recursive(i + 1)
            X[i][j] = "."
            row[i] = col[j] = dpos[i + j] = dneg[i - j + N - 1] = FREE

    recursive(0)

Solution (Python):


import sys


BOARD_SIZE_W = 8
BOARD_SIZE_H = 8


def set_queen(board, queen_point):
    """
    クイーンを指定座標に配置した後、残りの配置可能な位置の配列を返す
    """
    return filter(create_queen_filter(queen_point), board)


def create_queen_filter(queen_point):
    """
    指定位置にクイーンを配置したことにより、対象座標へ配置不可能にならないかを確認する関数を返す
    """

    def queen_filter(new_point):
        return new_point[1] != queen_point[1] and \
            new_point[0] != queen_point[0] and \
            new_point[0] != new_point[1] + queen_point[0] - queen_point[1] and \
            new_point[0] != -new_point[1] + queen_point[0] + queen_point[1]
    return queen_filter


def get_board_string(queen_points):
    """
    クイーンの位置座標の配列を指定出力形式に変換する
    """
    queen_points_set = set(list(map(lambda point: "{}:{}".format(point[1], point[0]), queen_points)))
    board_string_lines = []
    for y in range(BOARD_SIZE_H):
        line = ""
        for x in range(BOARD_SIZE_W):
            if "{}:{}".format(x, y) in queen_points_set:
                line += "Q"
            else:
                line += "."
        board_string_lines.append(line)
    return "\n".join(board_string_lines)


def get_all_queen_points(board, queen_points):
    if len(queen_points) >= 8:
        return queen_points
    elif not board:
        return []
    for empty_point in board:
        new_queen_points = [empty_point]
        new_queen_points.extend(queen_points)
        new_queen_points = get_all_queen_points(list(set_queen(board, empty_point)), new_queen_points)
        if new_queen_points:
            return get_all_queen_points(list(set_queen(board, empty_point)), new_queen_points)


def main():
    inputStr = sys.stdin.read()
    lines = inputStr.split("\n")
    lines = list(filter(lambda line: line, lines))
    if len(lines) <= 1:
        lines = []
    else:
        lines = lines[1:]
    queen_points = list(map(lambda line: list(map(int, line.split(" "))), lines))
    board = [[i % BOARD_SIZE_W, i // BOARD_SIZE_H] for i in range(BOARD_SIZE_H * BOARD_SIZE_W)]
    for queen_point in queen_points:
        board = list(set_queen(board, queen_point))
    sys.stdout.write(get_board_string(get_all_queen_points(board, queen_points)) + "\n")


if __name__ == '__main__':
    main()

Solution (Python):
import sys;

def putQueen(i, row, col, dpos, dneq):
    global finding
    if(finding == 0):
        return
        
    if(i == 8):
        finding = 0
        printBoard(row[0:])
        return
    

    for j in range(8):
        if i in myset:
            putQueen(i+1,row[0:], col[0:], dpos[0:], dneq[0:])
            continue
        if(col[j] == 1 or dpos[i+j] == 1 or dneq[i-j+7] == 1):
            continue
        row[i] = j
        col[j] = dpos[i+j] = dneq[i-j+7] = 1
        putQueen(i+1,row[0:], col[0:], dpos[0:], dneq[0:])
        col[j] = dpos[i+j] = dneq[i-j+7] = 0

def printBoard(row):
    for k in range(8):
        if(row[k] == 0):
            print("Q.......")
        elif(row[k] == 1):
            print(".Q......")
        elif(row[k] == 2):
            print("..Q.....")
        elif(row[k] == 3):
            print("...Q....")
        elif(row[k] == 4):
            print("....Q...")
        elif(row[k] == 5):
            print(".....Q..")
        elif(row[k] == 6):
            print("......Q.")
        else:
            print(".......Q")

n = (int)(input());
row = [0 for i in range(8)]
col = [0 for i in range(8)]
dpos = [0 for i in range(15)]
dneq = [0 for i in range(15)]

myset = set()

for i in range(n):
    r,c = map(int, input().split());
    myset.add(r)
    row[r] = c
    col[c] = 1
    dpos[r+c] = 1
    dneq[r-c+7] = 1

finding = 1

putQueen(0,row, col, dpos, dneq)

Solution (Python):

[N, FREE, NOT_FREE] = [8, -1, 1]
initial_Q = [FREE for i in range(N)]
row = [FREE for i in range(N)]
col = [FREE for i in range(N)]
dneg = [FREE for i in range(N*2 - 1)]
dpos = [FREE for i in range(N*2 - 1)]

k = int(input())
for i in range(k):
    [r, c] = list(map(int, input().split()))
    initial_Q[r] = NOT_FREE
    row[r] = c
    [col[c], dpos[r + c], dneg[r - c + N - 1]] = [NOT_FREE, NOT_FREE, NOT_FREE]

def printBoard():
    global N, row
    for i in range(N):
        row_data = ["." for i in range(N)]
        row_data[row[i]] = "Q"
        print("".join(row_data))
    
def putQueen(i):
    global N, FREE, NOT_FREE
    global initial_Q
    global row, col, dneg, dpos
    if i == N:
        printBoard()
        return 1
    
    if initial_Q[i] != FREE:
        if putQueen(i + 1) == 1:
            return 1
        else:
            return 0
    else:
        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
            row[i] = j
            [col[j], dpos[i + j], dneg[i - j + N - 1]] = [NOT_FREE, NOT_FREE, NOT_FREE]
            if putQueen(i + 1) == 1:
                return 1
            row[i] = FREE
            [col[j], dpos[i + j], dneg[i - j + N - 1]] = [FREE, FREE, FREE]

    return 0

putQueen(0)