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:
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 ""

# y = x - col + row
# y = - x + col + row

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# 8 Queens Problem
[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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

N = 8 # クイーンの数
n = int(input())

raw = [-1 for i in range(N)]
col = [0 for i in range(N)] # FREE: 0, NOT_FREE: 1
dpos = [0 for i in range(2*N-1)] # FREE: 0, NOT_FREE: 1
dneg = [0 for i in range(2*N-1)] # FREE: 0, NOT_FREE: 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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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): # i はrow番号
    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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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