Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

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...



Sample input:
2
2 2
5 3


Sample output:
......Q.
Q.......
..Q.....
.......Q
.....Q..
...Q....
.Q......
....Q...

Submission status: Accepted

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

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


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


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


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


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

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

search_place(board)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
import itertools

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

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


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

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

    return False



# main

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


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

Submission status: Accepted

Solution code:
from __future__ import division
import sys

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

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

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

Submission status: Accepted

Solution code:
from __future__ import division
import sys

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

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

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

Submission status: Accepted

Solution code:
from itertools import permutations


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


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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from itertools import product

class Board(object):
    def __init__(self):
        self.queen_pos = []  # ???????????????????????????????????? (y, x)????????????
        self.status = []  # ????´??????????????????¶??? 'Q'??????????????????'.'???????????????
        for i in range(8):
            self.status.append(['.'] * 8)
        self.situation = []  # ????????????????????±?????????????§£??????????????? 'Q'??????????????????'x'????????????????????±????????????'.'???????????????
        for i in range(8):
            self.situation.append(['.'] * 8)

    def clear(self):
        # print('clear: {0}'.format(self.queen_pos))
        temp = self.queen_pos[:]
        for q in temp:
            # print('removing {0}'.format(q))
            self.remove_queen(q)

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

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

    def put_queen(self, pos):
        if pos not in self.queen_pos:
            y, x = pos
            # print('put_queen: {0}, {1}'.format(y, x))
            if self.situation[y][x] != '.':
                return False
            self.status[y][x] = 'Q'
            self.queen_pos.append(pos)
            self.update_situation()
            return True
        else:
            # print('put failed')
            return False

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

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


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

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

    def get_availability(self):
        # ????????????????????????????????§??????????????????????????¨?????????????????¢??§??????
        results = []  # ??¨?????????????§£?????????
        for y in range(8):
            available = []  # ???????????§???????????????????????±
            for x in range(8):
                if self.situation[y][x] == '.':
                    available.append((y, x))
            if available:  # ????????´????????????????????????(itertools.product?????????????????????????????§)
                results.append(available)
        return results

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

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



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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
2
2 2
5 3

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

import sys

N = 8
FREE, NOT_FREE = -1, 1


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

    return init_q_check


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

    return None


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

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

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

        recursive(i + 1)

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

    return q_check


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

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

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

    ans = recursive(0)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
2
2 2
5 3

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

import sys

N = 8
FREE, NOT_FREE = -1, 1


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

    return init_q_check


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

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

    return None


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

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

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

        recursive(i + 1)

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

    return q_check


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

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

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

    ans = recursive(0)

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
# coding=utf-8

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

    def search(self, field_id, field):
        global final_queen_pos
        #print("field_id:", field_id)
        #field.print_field()
        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): #for debug
        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")

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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]))