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 itertools

def sumdiag(board, k):
    if (k >= 0):
        s = 0
        for i in range(len(board) - k):
            s += board[i][i + k]
        return s
    else:
        k = -k
        s = 0
        for i in range(len(board) - k):
            s += board[i + k][i]
        return s
           
def fliplr(board):
    f_board = []
    for i in range(len(board)):
        f_board.append(board[i][::-1])
    return f_board

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

for queen in itertools.permutations(range(8)):
    flag = 1
    for q in qs:
        if (queen[q[0]] != q[1]):
            flag = 0
    if (flag == 0):
        continue
    board = [[0 for i in range(8)] for j in range(8)]
    for i, qu in enumerate(queen):
        board[i][qu] = 1

    for k in range(-7,8):
        if (sumdiag(board, k=k) > 1):
            flag = 0
    f_board = fliplr(board)
    for k in range(-7, 8):
        if (sumdiag(f_board, k=k) > 1):
            flag = 0
    if (flag == 1):
        for i in range(8):
            for j in range(8):
                if (board[i][j] == 0):
                    print('.', end='')
                else:
                    print('Q', end='')
            print()
        break

Submission status: Accepted

Solution code:
import itertools

k = int(input())
X = sorted([list(map(int, input().split())) for _ in range(k)])
for l in list(itertools.permutations(range(8))):
  flag = True
  for x in X:
    if l[x[0]] != x[1]:
      flag = False
  if flag:
    flag2= True
    check = []
    for i in range(8):
      for j in range(1,8-i):
        check.append([i+j,l[i]+j])
        check.append([i+j,l[i]-j])
    for c in check:
      if c[1] < 0 or c[1] > 8:
        continue
      else:
        if c in [[i,l[i]] for i in range(8)]:
          flag2 = False
    if flag2:
      #print(l)
      #print(X)
      #print(check)
      for i in range(8):
        tmp = ['.','.','.','.','.','.','.','.']
        tmp[l[i]] = 'Q'
        print(''.join(tmp))
      break

Submission status: Accepted

Solution code:
from copy import deepcopy
from itertools import permutations

def valid(r, c):
    if 0 <= r and r < 8 and 0 <= c and c < 8:
        return True
    else:
        return False

def print_board(board):
    for i in range(8):
        print(" ".join(map(lambda x: "T" if x else "F", board[i])))

board = [[False for _ in range(8)] for _ in range(8)]
# board = [False for _ in range(64)]
ldyx = [
    (0, 1),
    (1, 1),
    (1, 0),
    (1, -1),
    (-1, 0),
    (-1, -1),
    (0, -1),
    (-1, 1)
]

lR, lC = [], []
N = int(input())
for _ in range(N):
    r, c = map(int, input().split())
    lR.append(r)
    lC.append(c)
    board[r][c] = True

    # all directions put
    # for dxy in ldyx:
    #     nr, nc = r + dxy[1], c + dxy[0]
    #     while valid(nr, nc):
    #         board[nr][nc] = True
    #         nr, nc = nr + dxy[1], nc + dxy[0]

# test
for perm in permutations(range(8)):
    b = deepcopy(board)
    flag = True
    for i in range(N):
        if perm[lR[i]] != lC[i]:
            flag = False
            break
    
    if not flag:
        continue

    # print(perm)
    flag = True
    for i in range(8):
        if i in lR:
            continue

        ri, ci = i, perm[i]
        b[i][perm[i]] = True
        is_possible = True

        for dxy in ldyx:
            nr, nc = ri + dxy[1], ci + dxy[0]
            while valid(nr, nc):
                if b[nr][nc]:
                    is_possible = False
                    break
                else:
                    # b[nr][nc] = True
                    nr, nc = nr + dxy[1], nc + dxy[0]
            if not is_possible:
                flag = False
                break
    if flag:
        for i in perm:
            si = ['.' if k != i else 'Q' for k in range(8)]
            print("".join(si))

Submission status: Accepted

Solution code:
import sys
from itertools import permutations
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

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

for per in permutations(range(8), 8):
    board = [['.'] * 8 for _ in range(8)]
    flag = True
    for r, c in RC:
        if per[r] != c:
            flag = False
            break
    if flag:
        flag_ = True
        pos = []
        for i, p in enumerate(per):
            if any([abs(i - q[0]) == abs(p - q[1]) for q in pos]):
                flag_ = False
                break
            board[i][p] = 'Q'
            pos.append((i, p))
        if flag_:
            for r in board:
                print(''.join(r))

Submission status: Accepted

Solution code:
import itertools

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)] for _ in range(2)]
q = []
for _ in range(k):
    r, c = map(int, input().split())
    q.append((r, c))
    R.remove(r)
    C.remove(c)

for l in itertools.permutations(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:
n=int(input())
l=[tuple(int(i) for i in input().split()) for j in range(n)]
ll=[]
s=set(l)
sp=set()
sm=set()
sy=set()
for i,j in l:
    sp.add(i+j)
    sm.add(i-j)
    sy.add(j)
for i in range(8):
    tmp=[]
    for j in range(8):
        if (i,j) in s:
            tmp=[]
            break
        if i+j in sp or i-j in sm:
            continue
        if j in sy:
            continue
        tmp.append((i,j))
    if tmp:
        ll.append(tmp)

ln=[]
m=1
for i in range(8-n):
    ln.append(len(ll[i]))
    m*=len(ll[i])


def base(X):
    X_dumy = X
    out = ''
    for i in ln:
        out += str(X_dumy%i)
        X_dumy = int(X_dumy/i)
    return out

import copy
for i in range(m):
    s=base(i)
    b=False
    cp=copy.deepcopy(sp)
    cm=copy.deepcopy(sm)
    cy=copy.deepcopy(sy)
    tmp=copy.deepcopy(l)
    for j in range(8-n):
        p,q=ll[j][int(s[j])]
        if p+q in cp or p-q in cm or q in cy:
            b=True
            break
        else:
            tmp.append((p,q))
            cp.add(p+q)
            cm.add(p-q)
            cy.add(q)
    if b:
        continue
    else:
        tmp.sort()
        for x,y in tmp:
            s="."*y+"Q"+"."*(7-y)
            print(s)

Submission status: Accepted

Solution code:
row, col = [True] * 8, [True] * 8
d_pos, d_neg = [True] * 15, [True] * 15
board = [["."] * 8 for _ in range(8)]


def change_state(r: int, c: int, undo: bool = False) -> None:
    if undo:
        row[r] = col[c] = d_pos[r + c] = d_neg[r - c + 7] = True
        board[r][c] = "."
    else:
        row[r] = col[c] = d_pos[r + c] = d_neg[r - c + 7] = False
        board[r][c] = "Q"


def solve_eight_queens(r: int = 0) -> None:
    while r < 8 and not row[r]:
        r += 1
    if r == 8:
        for board_row in board:
            print(*board_row, sep="")
        return
    for c in range(8):
        if not col[c] or not d_pos[r + c] or not d_neg[r - c + 7]:
            continue
        change_state(r, c)
        solve_eight_queens(r + 1)
        change_state(r, c, undo=True)


def main():
    K, *RC = map(int, open(0).read().split())
    for r, c in zip(*[iter(RC)] * 2):
        row[r] = col[c] = d_pos[r + c] = d_neg[r - c + 7] = False
        board[r][c] = "Q"
    solve_eight_queens()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools


def hand_in_answer(v):
    base = [".", ".", ".", ".", ".", ".", ".", "."]
    for i in range(8):
        tmp = base.copy()
        tmp[v[i]] = "Q"
        print("".join(tmp))


def ifGoodPosition(position, v):
    yo = position[0]
    xo = position[1]

    x = xo
    y = yo
    x += 1
    y += 1
    while x < 8 and x >= 0 and y >= 0 and y < 8:
        if v[y] == x:
            return False
        x += 1
        y += 1

    x = xo
    y = yo
    x += 1
    y -= 1
    while x < 8 and x >= 0 and y >= 0 and y < 8:
        if v[y] == x:
            return False
        x += 1
        y -= 1

    x = xo
    y = yo
    x -= 1
    y += 1
    while x < 8 and x >= 0 and y >= 0 and y < 8:
        if v[y] == x:
            return False
        x -= 1
        y += 1

    x = xo
    y = yo
    x -= 1
    y -= 1
    while x < 8 and x >= 0 and y >= 0 and y < 8:
        if v[y] == x:
            return False
        x -= 1
        y -= 1

    return True


fixed_q_count = int(input())
x_choices = set([_ for _ in range(8)])
fixed_qs = []
for _ in range(fixed_q_count):
    y, x = map(int, input().split(" "))
    fixed_qs.append([y, x])

for v in itertools.permutations(x_choices, 8):
    flag2 = True
    for fixed_q in fixed_qs:
        if not v[fixed_q[0]] == fixed_q[1]:
            flag2 = False
            break

    if not flag2:
        continue

    flag = True
    for y in range(8):
        if not ifGoodPosition([y, v[y]], v):
            flag = False
            break

    if flag:
        hand_in_answer(v)
        break

Submission status: Accepted

Solution code:
def main():
    from copy import deepcopy
    from itertools import permutations
    import sys
    input=sys.stdin.readline

    k=int(input())
    stage=[[0]*8 for _ in range(8)]
    ans=[['.']*8 for _ in range(8)]
    ablex=[0,1,2,3,4,5,6,7]
    abley=[0,1,2,3,4,5,6,7]

    def q(x,y,stage):
        i,j=x,y
        while i>=0 and j>=0:
            stage[i][j]=1
            i-=1
            j-=1
        i,j=x,y
        while i<8 and j<8:
            stage[i][j]=1
            i+=1
            j+=1
        i,j=x,y
        while i>=0 and j<8:
            stage[i][j]=1
            i-=1
            j+=1
        i,j=x,y
        while i<8 and j>=0:
            stage[i][j]=1
            i+=1
            j-=1
        
    for i in range(k):
        x,y=map(int,input().split())
        q(x,y,stage)
        ans[x][y]='Q'
        ablex.remove(x)
        abley.remove(y)
    
    for ptr in permutations(abley):
        s=deepcopy(stage)
        flag=True
        for x,y in zip(ablex,ptr):
            if s[x][y]==1:
                flag=False
                break
            else:
                q(x,y,s)
        if flag:
            for x,y in zip(ablex,ptr):
                ans[x][y]='Q'
            for i in range(8):
                print(''.join(ans[i]))
            exit()
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
num_queen = 8

def check_puttable(candidate, queens):
    cx, cy = candidate
    for queen in queens:
        qx, qy = queen
        if cx == qx or cy == qy or abs(cx - qx) == abs(cy - qy):
            return False
    return True

def create_candidates(queens):
    return [(i, j) for i in range(num_queen) for j in range(num_queen)
            if check_puttable((i,j), queens)]

def add_queen(queens):
    if len(queens) == num_queen: return queens
    candidates = create_candidates(queens)
    for candidate in candidates:
        _queens = add_queen(queens | {candidate})
        if _queens: return _queens

def show_queens(queens):
    for i in range(num_queen):
        for j in range(num_queen):
            if (i, j) in queens:
                print("Q", end="")
            else:
                print(".", end="")
        print("")

N = int(input())
queens = set()
for _ in range(N):
    i, j = map(int, input().split())
    queens.add((i, j))

queens = add_queen(queens)
show_queens(queens)

Submission status: Accepted

Solution code:
import sys
import math
import fractions
import itertools
from collections import deque
import copy
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()
k = int(input())
rc = [tuple(map(int, input().split())) for _ in range(k)]
LIST = []
ans = [["." for _ in range(8)] for _ in range(8)]
ALL = list(itertools.permutations(range(8)))
for i in range(len(ALL)):
    for l in range(7):
        p = 0
        for k in range(l + 1, 8):
            if ALL[i][l] == ALL[i][k]:
                p = 1
                break
            elif l == k:
                p = 1
                break
            for s in range(-7, 8):
                if ALL[i][l] + s == ALL[i][k] and l + s == k:
                    p = 1
                    break
                elif ALL[i][l] - s == ALL[i][k] and l + s == k:
                    p = 1
                    break
            if p == 1:
                break
        if p == 1:
            break
        elif l == 6:
            LIST.append(ALL[i])
for i in range(len(LIST)):
    for k in range(len(rc)):
        p = 0
        for l in range(8):
            if LIST[i][l] == rc[k][0] and l == rc[k][1]:
                p = 1
                break
        if p == 0:
            break
        if p == 1 and k == len(rc) - 1:
            for m in range(8):
                ans[LIST[i][m]][m] = "Q"
            for m in ans:
                print("".join(m))
            sys.exit()

Submission status: Accepted

Solution code:
# 8 Queens Problem

import sys, itertools
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

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

def diagonal_positions(Q):
    output = set()
    output.add(Q)
    for i in range(8):
        output.add((Q[0] + i, Q[1] + i))
        output.add((Q[0] + i, Q[1] - i))
        output.add((Q[0] - i, Q[1] + i))
        output.add((Q[0] - i, Q[1] - i))
    return output

k = int(input())
row_indices = set(range(8))
col_indices = set(range(8))
Q_positions = set()
NG_positions = set()

for _ in range(k):
    r, c = map(int, input().split())
    row_indices.discard(r)
    col_indices.discard(c)
    Q_positions.add((r,c))
    NG_positions |= diagonal_positions((r,c))

for rows in list(itertools.permutations(row_indices)):
    for cols in list(itertools.permutations(col_indices)):
        Q_positions_tmp = Q_positions.copy()
        NG_positions_tmp = NG_positions.copy()
        putting_Q = set((rows[i], cols[i]) for i in range(8-k))

        for new_Q in putting_Q:
            if new_Q in NG_positions_tmp:
                break
            else:
                Q_positions_tmp.add(new_Q)
                NG_positions_tmp |= diagonal_positions(new_Q)
        else:
            for q in Q_positions_tmp:
                board[q[0]][q[1]] = "Q"
            for i in range(8):
                print("".join(board[i]))
            exit()

Submission status: Accepted

Solution code:
import itertools

def judge(board):
  ret=True
  pos=[]
  for i in range(8):
    for j in range(8):
      if board[i][j]=='Q':
        pos.append((i,j))
  for i in range(8):
    tx1,ty1=pos[i]
    for j in range(8):
      tx2,ty2=pos[j]
      if i==j:
        continue
      if ty1==ty2 or tx1==tx2 or abs(ty1-ty2)==abs(tx1-tx2):
        ret=False
  return ret

k=int(input())
board=[['.']*8 for _ in range(8)]
pos1=[0,1,2,3,4,5,6,7]
pos2=[0,1,2,3,4,5,6,7]
for _ in range(k):
  a,b=map(int,input().split())
  board[a][b]='Q'
  pos1.remove(b)
  pos2.remove(a)
for tpos in itertools.permutations(pos1):
  for i in range(len(tpos)):
    board[pos2[i]][tpos[i]]='Q'
  if judge(board)==True:
    break
  for i in range(len(tpos)):
    board[pos2[i]][tpos[i]]='.'
for i in range(8):
  print(''.join(board[i]))

Submission status: Accepted

Solution code:
import sys
import itertools
import copy
input = sys.stdin.readline

n = int(input())
q = [tuple(map(int,input().split())) for _ in range(n)]

px = [0,1,2,3,4,5,6,7]
py = [0,1,2,3,4,5,6,7]
for i in q:
    px.remove(i[0])
    py.remove(i[1])

for v in itertools.permutations(py):
    r_q = copy.deepcopy(q)
    for x,y in zip(px,v):
        for c_q in r_q:
            if c_q[0] == x or c_q[1] == y or abs(c_q[0] - x) == abs(c_q[1]-y):
                break
        else:
            r_q.append((x, y))
            continue
        break
    else:
        board = [['.' for _ in range(8)] for _ in range(8)]
        for i in range(8):
            board[r_q[i][0]][r_q[i][1]] = "Q"
        for i in range(8):
            for j in range(8):
                print (board[i][j],end='')
            print ('')
        exit (0)

Submission status: Accepted

Solution code:
class Field:

    def __init__(self, N):
        self.N = N
        self.row = [-1 for _ in range(N)]
        self.hold = []
        self.col = [0 for _ in range(N)]
        self.dpos = [0 for _ in range(2*N - 1)]
        self.dneg = [0 for _ in range(2*N - 1)]

    def putQueen(self, i):
        if i in self.hold:
            self.putQueen(i + 1)
            return 
        if i == self.N:
            self.printBoard()
            return
        for j in range(self.N):
            if self.col[j] or self.dpos[i+j] or self.dneg[i-j+self.N-1]:
                continue
            self.setQueen(i, j)
            self.putQueen(i + 1)
            self.col[j] = self.dpos[i+j] = self.dneg[i-j+self.N-1] = 0

    def setQueen(self, i, j):
        self.row[i] = j
        self.col[j] = self.dpos[i + j] = self.dneg[i - j + self.N - 1] = 1

    def printBoard(self):
        print('\n'.join("." * r + "Q" + "." * (self.N - r - 1) for r in self.row))


if __name__ == "__main__":
    field = Field(8)
    for _ in range(int(input())):
        i, j = (map(int, input().split()))
        field.setQueen(i, j)
        field.hold.append(i)
    field.putQueen(0)

Submission status: Accepted

Solution code:
from collections import deque

def nqueen(queen_rcs, n, k):
    def rc2idx(r, c):  # 7,7->88となる
        return (n + 2) * (r + 1) + c + 1

    queens = deque([])
    table = [None] * (n + 2) + ([None] + [-1] * n + [None]) * n + [None] * (n + 2)
    directions = [-(n + 3), -(n + 2), -(n + 1), -1, 1, n + 1, n + 2, n + 3]

    # queen_rcsに基づきqueenを入れ、おけない場所をマーク
    for queen_r, queen_c in queen_rcs:
        idx = rc2idx(queen_r, queen_c)
        table[idx] = idx
        for direction in directions:
            search_idx = idx
            while table[search_idx] is not None:
                if table[search_idx] == -1:
                    table[search_idx] = idx
                search_idx += direction

    idx = rc2idx(0, 0)
    max_idx = rc2idx(n - 1, n - 1)
    while len(queens) < n - k:
        # 配置できる場所を探す
        while idx <= max_idx and (table[idx] is None or table[idx] > -1):
            idx += 1
        if idx > max_idx:
            # 配置できる場所がなかった場合はバックトラック
            idx = queens.pop()
            for i in range((n + 2) * (n + 2)):
                if table[i] is not None and table[i] == idx:
                    table[i] = -1
            idx += 1
            continue
        # 配置できる場所があった場合は置く
        table[idx] = idx
        queens.append(idx)
        for direction in directions:
            search_idx = idx
            while table[search_idx] is not None:
                if table[search_idx] == -1:
                    table[search_idx] = idx
                search_idx += direction
        idx += 1
    return table


def print_table(table, n):
    def rc2idx(r, c):  # 7,7->88となる
        return (n + 2) * (r + 1) + c + 1
    for r in range(n):
        for c in range(n):
            idx = rc2idx(r, c)
            if table[idx] == idx:
                print("Q", end="")
            else:
                print(".", end="")
        print("\n", end="")

def main():
    queen_rcs = []
    k = int(input())
    for _ in range(k):
        line = input().split()
        r, c = list(map(int, line))
        queen_rcs.append((r, c))
    table = nqueen(queen_rcs, 8, k)
    print_table(table, 8)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:


N = 8
FREE = -1
NOT_FREE = 1


def printBoard():
    for i in range(N):
        for j in range(N):
            if X[i][j]:
                if not Y[i][j]:
                    return
    for i in range(N):
        for j in range(N):
            if Y[i][j]:
                print("Q", end = "")
            else:
                print(".", end = "")
        print("")

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

    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] = NOT_FREE
        col[j] = NOT_FREE
        dpos[i + j] = NOT_FREE
        dneg[i-j + N -1] = NOT_FREE
        Y[i][j] = True
        
            
        recursive(i + 1)
        
        row[i] = FREE
        col[j] = FREE
        dpos[i + j] = FREE
        dneg[i-j + N -1] = FREE
        Y[i][j] = False

row = [FREE] * N
col = [FREE] * N
dpos = [FREE] * (2 * N - 1)
dneg = [FREE] * (2 * N - 1)
X = [[False for i in range(N)] for j in range(N)]
Y = [[False for i in range(N)] for j in range(N)]

n = int(input())
for i in range(n):
    nums=list(map(int,input().split()))
    X[nums[0]][nums[1]] = True



recursive(0)

Submission status: Accepted

Solution code:
def printBorad():
    for i in range(8):
        s = ['.'] * 8
        s[row[i]] = 'Q'
        print(''.join(s))

def putQueen(i, j):
    row[i] = j
    col[j] = True
    left[i+j] = True
    right[7+i-j] = True

def removeQueen(i, j):
    row[i] = False
    col[j] = False
    left[i+j] = False
    right[7+i-j] = False
    


def recursive(i):
    if i == 8:
        printBorad()
        return
    
    if row[i] is not False:
        putQueen(i, row[i])
        recursive(i + 1)
    else:
        for j in range(8):        
            if col[j] or left[i+j] or right[7+i-j]:
                continue
            putQueen(i, j)
            recursive(i + 1)
            removeQueen(i, j)


if __name__ == "__main__":
    row = [False for i in range(8)]
    col = [False for i in range(8)]
    left = [False for i in range(15)]
    right = [False for i in range(15)]
    n = int(input())
    for _ in range(n):
        i, j = map(int, input().split())
        putQueen(i, j)
    
    recursive(0)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
col = []
row = []
rd = []
lu = []
board = [['.'] * 8 for _ in range(8)]

def put(r, c):
    global col, row, rd, lu, board
    col.append(c)
    row.append(r)
    rd.append(c-r)
    lu.append(r+c)
    board[r][c] = 'Q'

def canPut(i, j):
    if i not in row and j not in col and j-i not in rd and i+j not in lu:
        return True
    else:
        return False

def unput(i, j):
    global col, row, rd, lu, board
    col.remove(j)
    row.remove(i)
    rd.remove(j-i)
    lu.remove(i+j)
    board[i][j] = '.'

def rec(i):
    if i > 7:
        for p in range(8):
            print(''.join(board[p]))
        exit(0)
    # print("i: ", i)
    for j in range(8):
        if canPut(i, j):
            put(i, j)
            # print("put: ", i, j)
            k = i+1
            while k in row:
                k += 1
            rec(k)
            unput(i, j)

def main():
    global col, row, rd, lu
    n = int(input().strip())

    for i in range(n):
        r, c = list(map(int, input().strip().split()))
        put(r, c)
    k = 0
    while k in row:
        k += 1
    rec(k)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = 8
grid = list2d(N, N, '.')
# 横襲撃済
row = [False] * N
# 縦襲撃済
col = [False] * N
# 左下・右上襲撃済
dpos = [False] * (N*2-1)
# 左上・右下襲撃済
dneg = [False] * (N*2-1)

# クイーンを置く
def putQ(i, j):
    row[i] = True
    col[j] = True
    dpos[i+j] = True
    dneg[i-j+N-1] = True
    grid[i][j] = 'Q'

# クイーンを取り除く
def delQ(i, j):
    row[i] = False
    col[j] = False
    dpos[i+j] = False
    dneg[i-j+N-1] = False
    grid[i][j] = '.'

# 置ける状態か確認
def check(i, j):
    return not (row[i] or col[j] or dpos[i+j] or dneg[i-j+N-1])

qcnt = INT()
for i in range(qcnt):
    r, c = MAP()
    putQ(r, c)

def rec(i, j, cnt):
    if cnt == 8:
        return True
    for k in range(8):
        for l in range(8):
            if check(k, l):
                putQ(k, l)
                if rec(k, l, cnt+1):
                    return True
                else:
                    # うまくいかなかったら状態を元に戻す
                    delQ(k, l)
    return False

for i in range(8):
    for j in range(8):
        if rec(i, j, qcnt):
            [print(''.join(row)) for row in grid]
            exit()

Submission status: Accepted

Solution code:
import itertools
k = int(input())
Q = []
for i in range(k):
    r,c = map(int, input().split( ))
    Q.append([r,c])
Q.sort()
#print(Q)
for p in itertools.permutations(range(8)):
    flag = True
    Qall = [[i,p[i]] for i in range(8)]
    for q in Q:
        if q[1] != p[q[0]]:
            flag = False
            break
    for j in range(8):
        for l in range(j+1,8):
            if abs(j-l) == abs(p[j]-p[l]):
                flag = False
                break
    if flag:
        break
#print(flag,Qall)    
for i in range(8):
    for j in range(8):
        if [i,j] not in Qall:
            print(".", end = "")
        else:
            print("Q",end="")
    print()

Submission status: Accepted

Solution code:
from collections import namedtuple

State = namedtuple("State", "queen row col dpos dneg")


def put_queen(s, r, c):
    s.queen[r] = c
    s.row[r] = s.col[c] = s.dpos[r + c] = s.dneg[r - c + 8 - 1] = True


def unput_queen(s, r, c):
    s.queen[r] = None
    s.row[r] = s.col[c] = s.dpos[r + c] = s.dneg[r - c + 8 - 1] = False


def read_board(s):
    k = int(input())
    for _ in range(k):
        r, c = [int(x) for x in input().split()]
        put_queen(s, r, c)
    return s


def print_board(s):
    for r in range(8):
        for c in range(8):
            print("Q" if s.queen[r] == c else ".", end="")
        print()


def eight_queens(s):
    def rec(r, s):
        if r == 8:
            return s
        elif s.queen[r] is not None:
            return rec(r + 1, s)
        else:
            for c in range(8):
                if s.col[c] or s.dpos[r + c] or s.dneg[r - c + 8 - 1]:
                    continue
                new_s = State(
                    s.queen[:], s.row[:], s.col[:], s.dpos[:], s.dneg[:]
                )
                put_queen(new_s, r, c)
                result = rec(r + 1, new_s)
                if result:
                    return result
            return False

    return rec(0, s)


def main():
    s = State(
        [None] * 8,
        [False] * 8,
        [False] * 8,
        [False] * (2 * 8 - 1),
        [False] * (2 * 8 - 1),
    )

    print_board(eight_queens(read_board(s)))


main()

Submission status: Accepted

Solution code:
import copy
from typing import List, Tuple


def _fill_forbidden_pos(board: List[List[int]], pos: Tuple[int, int]) -> None:
    row, col = pos[0], pos[1]
    # Horizontal.
    for i in range(8):
        board[row][i] = 1
    # Vertical.
    for i in range(8):
        board[i][col] = 1
    # Diagonal.
    for i in range(min(row, col) + 1):
        board[row - i][col - i] = 1
    for i in range(min(7 - row, 7 - col) + 1):
        board[row + i][col + i] = 1
    for i in range(min(row, 7 - col) + 1):
        board[row - i][col + i] = 1
    for i in range(min(7 - row, col) + 1):
        board[row + i][col - i] = 1


def set_queens(board: List[List[int]], num_rest_q: int) -> bool:
    global queens_list
    if 0 == num_rest_q:
        return True
    board_copied = copy.deepcopy(board)
    for row in range(8):
        for col in range(8):
            if 1 != board_copied[row][col]:
                _fill_forbidden_pos(board_copied, (row, col))
                if set_queens(board_copied, num_rest_q - 1):
                    queens_list.append((row, col))
                    return True
                else:
                    board_copied = copy.deepcopy(board)
    return False


if __name__ == "__main__":
    board = [[0] * 8 for _ in range(8)]
    queens_list = []

    num_init_Q = int(input())
    for _ in range(num_init_Q):
        (row, col) = map(lambda x: int(x), input().split())
        queens_list.append((row, col))
        _fill_forbidden_pos(board, (row, col))

    num_rest_q = 8 - num_init_Q
    set_queens(board, num_rest_q)

    for q_pos in queens_list:
        board[q_pos[0]][q_pos[1]] = -1
    for one_row in board:
        print("".join(["Q" if -1 == pos else "." for pos in one_row]))

Submission status: Accepted

Solution code:
N = 8
FREE = 1
NOT_FREE = -1


row = [FREE] * N
col = [FREE] * N
dpos = [FREE] * (2 * N - 1)
dneg = [FREE] * (2 * N - 1)

board = [[False] * N for _ in range(N)]

k = int(input())

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


def slove(i):
    if i == N:
        print_board()
        return

    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] = NOT_FREE
        dpos[i + j] = NOT_FREE
        dneg[i - j + N - 1] = NOT_FREE

        slove(i + 1)

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

def print_board():
    for i in range(N):
        for j in range(N):
            if board[i][j] and row[i] != j:
                return
    
    for i in range(N):
        for j in range(N):
            if row[i] == j:
                mark = "Q"
            else:
                mark = "."
            print(mark, end="")
        print()

slove(0)