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:
#N = int(input())
# class Queen():
#     def __init__(self, x,y):
#         self.x =x
#         self.y = y
#         self.right = self.x + self.y
#         self.left = abs(self.x -self.y)
#
#
#
# queen_row = [False for _ in range(8)]
# queen_col = [False for _ in range(8)]
# ups = [False for _ in range(2 * 8 -1)]
# downs = [False for _ in range(2 * 8 -1)]
#
#
# for _ in range(N):
#     r,c = list(map(int,input().split()))
#     # queen_row.append(Queen(c,r))
#     queen_row[r] = c
#     queen_col[c] = True
#     ups[r+c] = True
#     downs[abs(r-c)] = True
#
# # queen_list = [Queen(c,r) in r,c range() ]
# def is_not_cross(q1:Queen,q2:Queen):
#     if q1.left != q2.left and q1.right != q2.right:
#         return True
#     else:
#         return False
#
#
# # def put_queen(queen_list:list):
# #     x_set = {i for i in range(8)} - {q.x for q in queen_list}
# #     y_set = {i for i in range(8)} - { q.y for q in queen_list}
# #     for i,x in enumerate(x_set):
# #         for y in y_set:
# #             q1 = Queen(x,y)
# #             for q2 in queen_list:
# #                 if is_not_cross(q1,q2):
# #                     queen_list.append(q1)
# #         print(i)
# #
# #     return queen_list
#
#
#     # return queen_list
#
#
# def put_queen(rows,col_no=0):
#     # search_rows = [ i  for i in range(8) ]
#     search_rows = [ i  for i, is_exist in zip(range(8), rows) if not is_exist ]
#     # print(search_rows)
#     # print(col_no)
#     for n in search_rows:
#         print({"queen_col": queen_col, "rows": rows, })
#
#         if not queen_col[col_no] and not ups[n + col_no] and not downs[abs(n- col_no)]:
#             print(f" success :row_no:{n},col_no:{col_no}")
#
#             queen_col[col_no] =True
#             ups[n + col_no] = True
#             downs[abs(n- col_no)] = True
#             rows[n] = col_no
#
#             if col_no + 1 >=N:
#                 print(f"終了 {queen_col}")
#                 # print(search_rows)
#
#                 return rows # 全探索終了
#             else:
#                 res = put_queen(rows,col_no + 1)
#                 print(f"row_no:{n},col_no:{col_no}")
#                 print(res)
#                 if res:
#                     return res
#                 else:
#                     rows[n] = False
#                     ups[n + col_no] = False
#                     downs[abs(n - col_no)] = False
#                     queen_col[col_no] = False
#                     rows = put_queen(rows,queen_col,ups,downs,col_no + 1)
#     return False
#
#
# def print_queen(rows):
#     board = [["." for _ in range(8)] for _ in range(8)]
#     for row,col in enumerate(rows):
#         board[row][col] = "Q"
#     for b_y in board:
#         for i, b in enumerate(b_y):
#             print(b, end="")
#             if i == 7:
#                 print("\n")
# queen_list = put_queen(queen_row,0)
# print(queen_list)
# print_queen(queen_list)
#
# def is_able_put(rows):
#     for row,col in
#
#
# def put_queen(rows,n=0,DEFAULT_ROW=queen_row):
#     search_rows = [i for i, is_exist in zip(range(8), rows) if not is_exist]
#     # 歯抜けになっている順列を生成(ついでに、斜め判定も行う)
#
#     if is_able_put():
#
#
#     if n ==/
#
# # class
#

N = int(input())
DEFAULT_TABLE = [False for _ in range(8)]
DEFAULT_UPS = [False for _ in range(15)]
DEFAULT_DOWNS = [False for _ in range(15)]
for i in range(N):
    r,c = list(map(int,input().split()))
    DEFAULT_TABLE[r] = c
    DEFAULT_DOWNS[r-c + 7] = True
    DEFAULT_UPS[r + c] = True


def exclude(data, idx):
    return [x for i, x in enumerate(data) if i not in idx]


def permutationListRecursive(data, r, progress):
    # r = r if r > 0 else len(data) - len(exclued)

    if r == 0:
        # result.append(progress)
        table = DEFAULT_TABLE.copy()
        ups  =DEFAULT_UPS.copy()
        downs = DEFAULT_DOWNS.copy()

        for i,t in enumerate(table):
            if t is False:
                col = progress.pop()
                # print(table,progress, col)

                if ups[i+ col] or downs[i- col + 7]:
                    return False
                table[i]=col
                ups[i+col ] = True
                downs[i-col + 7] = True
            else:
                continue
        # print(f"progressis {progress}, ups :{ups} downs:{downs} ,table is {table}")

        result = table
        return result
    for i in range(len(data)):
        # progress= progress + [data[i]]
        res = permutationListRecursive(exclude(data, [i]), r - 1, progress + [data[i]])
        if res:
            return res
data =list(range(8))

for x in DEFAULT_TABLE:
    if x is not False:
        data.remove(x)
res_table= permutationListRecursive(data,len(data),[])
# print(res_table)
for i in range(8):
    for j in range(8):
        if res_table[i] == j:
            print("Q",end="")
        else:
            print(".",end="")
    print()

Submission status: Accepted

Solution code:
# 8 queens
import itertools


# x座標が全部異なる
# y座標が全部異なる
# 8C2でx座標の差分とy座標の差分が異なる
# 列挙して含まれるものを挙げる

def check(queens):
    for r1, c1 in queens:
        for r2, c2 in queens:
            # 同じ座標の時は気にしない
            if r1 == r2 and c1 == c2:
                continue
            if (r1 == r2) or (c1 == c2):
                return False
            if abs(r1 - r2) == abs(c1 - c2):
                return False
    return True


k = int(input())
queens = []
row, col = list(range(8)), list(range(8))
for _ in range(k):
    r, c = map(int, input().split())
    queens.append((r, c))
    row.remove(r)
    col.remove(c)

# colを順列化する
for l in itertools.permutations(col):
    tmp_queens = queens.copy()
    # rowは固定 どうせ全てにおかれる。
    for r, c in zip(row, l):
        tmp_queens.append((r, c))
    if check(tmp_queens):
        board = [''.join('Q' if (r, c) in tmp_queens else '.' for c in range(8)) for r in range(8)]
        print(*board, sep='\n')
        break

Submission status: Accepted

Solution code:
import sys
import copy

k = int(input())


class Chessboard:
    def __init__(self):
        self.row = [True] * 8
        self.col = [True] * 8
        self.dpos = [True] * 15
        self.dneg = [True] * 15
        return

    def put(self, r, c):
        # queen が r, c に配置されたときに攻撃されるマスの記録
        self.row[r] = False
        self.col[c] = False
        self.dpos[r + c] = False  # 左下が攻撃される
        self.dneg[r + 7 - c] = False  # 右下が攻撃される
        return

    def safe(self, r, c):
        # r, c が攻撃されていないか確認する　攻撃されていないときTrue を返す
        return self.row[r] and self.col[c] and self.dpos[r + c] and self.dneg[r + 7 - c]

    def is_row(self, r):
        return self.row[r]


board = Chessboard()
ans = [['.'] * 8 for _ in range(8)]
for _ in range(k):
    r, c = map(int, sys.stdin.readline().strip().split())
    board.put(r, c)
    ans[r][c] = 'Q'
final_ans = None


def search(r=0, board=board, ans=ans):
    global final_ans
    if r == 8:  # 最終行を終了し探索する行が存在しないときに終了する
        final_ans = ans
        return ans
    if not board.is_row(r):
        # すでに Q が配置されている行の探索はスキップする
        search(r=r+1, board=board, ans=ans)

    for c in range(8):
        board_temp = copy.deepcopy(board)
        ans_temp = copy.deepcopy(ans)
        if board_temp.safe(r, c):
            board_temp.put(r, c)
            ans_temp[r][c] = 'Q'
            search(r=r+1, board=board_temp, ans=ans_temp)
        else:
            continue


ans = search()
for r_ans in final_ans:
    print(''.join(r_ans))

Submission status: Accepted

Solution code:
import itertools

def check_p(p):
    #(a, b)の左上から右下への斜め線は(k, k+(b-a))
    for i in range(8):
        for j in range(i+1, 8):
            if p[j] - j == p[i] - i:
                return 0
    
    #(a, b)の右上から左下への斜め線は(a, b)について和一定
    for i in range(8):
        for j in range(i+1, 8):
            if p[j] + j == p[i] + i:
                return 0

    return 1

def print_p(p):
    for i in range(8):
        q = p[i]
        for j in range(8):
            if j != q:
                print(".", end = "")
            else:
                print("Q", end = "")
    
        print()
    return 0

k = int(input())
put_Q = list()
for i in range(k):
    put_Q.append(list(map(int, input().split())))

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

error = 0
for p in itertools.permutations(list(range(8))):
    # print(p)
    for i in range(k):
        if p[put_Q[i][0]] != put_Q[i][1]:
            error = 1

    if error == 0:
        if check_p(p) == 1:
            print_p(p)
            break
    
    error = 0

Submission status: Accepted

Solution code:
# k = int(input())
# init_q = [tuple(map(int, input().split(' '))) for _ in range(k)]
cin = open(0).read().strip().split('\n')
k = int(cin[0])
init_q = [tuple(map(int, a.split(' '))) for a in cin[1:]]

import itertools, copy

# ↓これは[0]のlistオブジェクトの同じIDを持つ要素を使い回すので、init_b[0][1] = 1したときにバグる
# init_b = [[0] * 8] * 8
init_b = [[0 for _ in range(8)] for _ in range(8)]
for q in init_q:
    init_b[q[0]][q[1]] = 1

def culc_diag(list2d, k=0, r2l=False):
    """正方行列のみ"""
    n = len(list2d)

    ret = 0
    if r2l:
        if k > 0:
            ret = sum(list2d[i][n-1-k-i] for i in range(n-k))
        else:
            ret = sum(list2d[i-k][n-1-i] for i in range(n+k))
    else:
        if k > 0:
            ret = sum(list2d[i][i+k] for i in range(n-k))
        else:
            ret = sum(list2d[i-k][i] for i in range(n+k))

    return ret

for cases in itertools.permutations(range(8)):
    b = copy.deepcopy(init_b)
    for idx, c in enumerate(cases):
        if 1 != sum(b[idx]):
            b[idx][c] = 1

    if all([sum(a) for a in b]):
        t_b = [list(x) for x in zip(*b)]
        if all([sum(a) for a in t_b]):
            flg = True
            for i in range(8):
                if (culc_diag(b, k=i, r2l=False) > 1) or (culc_diag(b, k=i, r2l=True) > 1) or (culc_diag(b, k=-1*i, r2l=False) > 1) or (culc_diag(b, k=-1*i, r2l=True) > 1):
                    flg = False
            if flg:
                for row in b:
                    new_b = []
                    for ad in row:
                        new_b.append('.' if ad == 0 else 'Q')
                    print(''.join(new_b))
                break

Submission status: Accepted

Solution code:
from itertools import permutations
from copy import deepcopy
board = [["."] * 8 for _ in range(8)]
N = int(input())

def check(r, c, board):
    # 4つのループで8方向のblockを移動不可にする
    for i in range(8):
        if board[i][c] == "Q": return False
        if board[r][i] == "Q": return False
    for i in range(-8,8):
        if 0 <= i + c < 8 and 0 <= i + r < 8:
            if board[i+r][i+c] == "Q": return False
        if 0 <= c+(-i) < 8 and 0 <= i + r < 8:
            if board[i+r][-i+c] == "Q": return False
    return True

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

def main():
    for p in permutations(range(8)):
        tmp = deepcopy(board)
        for i, v in enumerate(p):
            tmp[i][v] = "Q"
        if not all(tmp[rc[i][0]][rc[i][1]] == "Q" for i in range(N)): continue
        judge = True
        for i, v in enumerate(p):
            tmp[i][v] = "."
            if check(i, v, tmp):
                pass
            else:
                judge = False
                break
            tmp[i][v] = "Q"
        if judge: return tmp
       
tmp = main()
for t in tmp:
    print(''.join("Q" if i == "Q" else "." for i in t))

Submission status: Accepted

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

def solve():
    import itertools
    import copy

    K = int(input())
    grid = [[0 for i in range(8)] for j in range(8)]

    def put_queen(grid, r, c):
        for j in range(8):
            grid[r][j] = -1
        for i in range(8):
            grid[i][c] = -1
        # 左上
        i, j = r-1, c-1
        while i >= 0 and j >= 0:
            grid[i][j] = -1
            i, j = i-1, j-1
        # 左下
        i, j = r+1, c-1
        while i < 8 and j >= 0:
            grid[i][j] = -1
            i, j = i+1, j-1
        # 右上
        i, j = r-1, c+1
        while i >= 0 and j < 8:
            grid[i][j] = -1
            i, j = i-1, j+1
        # 右下
        i, j = r+1, c+1
        while i < 8 and j < 8 :
            grid[i][j] = -1
            i, j = i+1, j+1
        grid[r][c] = 1


    for i in range(K):
        r, c = list(map(int, input().split()))
        put_queen(grid, r, c)

    # 8!を全探索
    ps = itertools.permutations([i for i in range(8)], r=8)
    for p in ps:
        ans_grid = copy.deepcopy(grid)
        is_ok = True
        for i in range(8):
            if ans_grid[i][p[i]] == 1:
                continue
            if ans_grid[i][p[i]] == -1:
                is_ok = False
                break
            put_queen(ans_grid, i, p[i])
        if is_ok:
            break

    # ans_gridを出力して終了
    for i in range(8):
        s = ""
        for j in range(8):
            if ans_grid[i][j] == 1:
                s += "Q"
            else:
                s += "."
        print(s)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces


def permutation(ret: list, leftovers: list) -> list:
    if len(leftovers) == 0:
        yield ret
    
    for left in leftovers:
        leftoverscopy = [i for i in leftovers]
        leftoverscopy.remove(left)
        yield from permutation(ret+[left], leftoverscopy)


def canAssign(xs, ys):
    for i in range(7):
        for j in range(i+1,8):
            if abs(xs[i]-xs[j]) == abs(ys[i]-ys[j]):
                return False
    return True


def displayChessboard(xs, ys):
    board = [['.']*8 for i in range(8)]
    for i in range(8):
        board[ys[i]][xs[i]] = 'Q'
    for i in range(8):
        for j in range(8):
            print(board[i][j], end='')
        print()
    return


def main():
    k = ni()
    queens = [na() for _ in range(k)]
    xqueens = []
    yqueens = []
    xs = [x for x in range(8)]
    ys = [y for y in range(8)]
    for queen in queens:
        xs.remove(queen[1])
        ys.remove(queen[0])
        xqueens.append(queen[1])
        yqueens.append(queen[0])
    
    for yspernm in permutation([],ys):
        if canAssign(xqueens+xs, yqueens+yspernm):
            displayChessboard(xqueens+xs, yqueens+yspernm)
            return
    
    print("Can't make chessboard.")
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations

k = int(input())
r = [0] * k; c = [0] * k;
for i in range(k):
    r[i], c[i] = [int(a) for a in input().split()]

r_avail = list(range(8))
c_avail = list(range(8))

for i in range(k):
    r_avail.remove(r[i])
    c_avail.remove(c[i])

cperms = list(permutations(c_avail, 8 - k))

for perm in cperms:
    Q = [(r[i], c[i]) for i in range(k)] + list(zip(r_avail, perm))
    for a in range(8):
        for b in range(a + 1, 8):
            rdiff = Q[a][0] - Q[b][0]
            cdiff = Q[a][1] - Q[b][1]
            if abs(rdiff) == abs(cdiff):
                break # 斜めの線上にある
        else:
            continue
        break
    else: # 斜めの線上にあるQueenは無い
        break

ans = [['.' for _ in range(8)] for _ in range(8)]
for i in range(8):
    ans[Q[i][0]][Q[i][1]] = 'Q'

for i in range(8):
    print("".join(ans[i]))

Submission status: Accepted

Solution code:
from itertools import permutations as per
z=int(input())
chk=[]
for i in range(z):
    chk.append([int(i) for i in input().split()])
a=list(range(8))
pera=list(per(a))
k=0
for i in pera:
    st1=set() ; st2=set() ; flag=0
    for j in range(z):
        if i[chk[j][0]]!=chk[j][1]:
            flag=1
            break
    if flag==1: continue
    for j in range(8):
        if i[j]-j not in st1:
            st1.add(i[j]-j)
        else: break
        if i[j]+j not in st2:
            st2.add(i[j]+j)
        else: 
            break
    if len(st1)==8 and len(st2)==8:
        ans=[['.']*8 for i in range(8)]
        for j in range(8):
            ans[j][i[j]]='Q'
        for le in range(8):
            print(''.join(ans[le]))
        break

Submission status: Accepted

Solution code:
import itertools
p = list(itertools.permutations(range(8)))
n = int(input())
k = [list(map(int,input().split())) for i in range(n)]
for d in p:
    f = True
    for r,c in k:
        if d[r]!=c:
            f = False
    if not f:continue
    for i in range(8):
        for j in range(8):
            if i==j:continue
            if i+d[i]==j+d[j]:
                f = False
            if i-d[i]==j-d[j]:
                f = False
    if f:
        for i in d:
            s = ['.']*8
            s[i]='Q'
            print(''.join(s))

Submission status: Accepted

Solution code:
from itertools import permutations as per
from copy import deepcopy
k = int(input())
b = [["."]*8 for _ in range(8)]
st = [[False]*8 for _ in range(8)]

def setQueen(r,c):
    if st[r][c]: return False
    for i in range(8):
        st[i][c] = True
        st[r][i] = True
    d = abs(r-c)
    y,x = d,0
    if r < c: y,x = x,y
    for i in range(8-d): st[y+i][x+i] = True
    d = abs(7-r-c)
    y,x = d,0
    if 7-r < c: y,x = x,y
    for i in range(8-d): st[7-y-i][x+i] = True
    b[r][c] = "Q"
    return True

sr = [True]*8
sc = [True]*8
for _ in range(k):
    r,c = map(int,input().split())
    b[r][c] = "Q"
    setQueen(r,c)
    sr[r] = False
    sc[c] = False

row = [i for i in range(8) if sr[i]]
col = [i for i in range(8) if sc[i]] 

tmpb = b
tmpst = st
for p in per(row):
    b = deepcopy(tmpb)
    st = deepcopy(tmpst)
    for r,c in zip(p,col):
        if not setQueen(r,c): break
    else:
        for i in range(8): print("".join(b[i]))
        break

Submission status: Accepted

Solution code:
from itertools import permutations
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    k,*rc = map(int, read().split())

    tmp = []
    ng_list_add = []
    ng_list_sub = []
    for pattern in permutations(range(8)):
        flag = True
        for r, c in enumerate(pattern):
            if r + c in ng_list_add or r - c in ng_list_sub:
                flag = False
                break
            ng_list_add.append(r+c)
            ng_list_sub.append(r-c)
        if flag:
            tmp.append(pattern)
        ng_list_add = []
        ng_list_sub = []
    
    RC = []
    for r, c in zip(*[iter(rc)]*2):
        RC.append((r, c))

    ans_place = None
    for p in tmp:
        flag = True
        for r, c in RC:
            if p[r] != c:
                flag = False
                break
        if flag:
            ans_place = p
            break

    ans = []
    for i in ans_place:
        line = "." * i + "Q" + "." * (7-i)
        ans.append(line)

    print("\n".join(ans))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
vert = [False] * 8
hori = [False] * 8
topright = [False] * (8 * 2 - 1)
topleft = [False] * (8 * 2 - 1)
queens = []
skip_row = []


def put_queen(x, y):
    vert[x] = True
    hori[y] = True
    topright[x + y] = True
    topleft[7 + (x - y)] = True
    queens.append((x, y))


def elim_queen(x, y):
    vert[x] = False
    hori[y] = False
    topright[x + y] = False
    topleft[7 + (x - y)] = False
    queens.remove((x, y))


def is_blank(x, y):
    if not vert[x] and not hori[y] and not topright[x+y] and not topleft[7+(x-y)]:
        return True


def search_blank_in_row(y):
    blanks = []
    for x in range(8):
        if is_blank(x, y):
            blanks.append(x)
    return blanks


def put_queen_in_row(y):
    #print("put_queen_row",y, queens)
    if y == 8:
        return True     # 8 Queens have already been existed; reached the solution.
    if y in skip_row:
        return put_queen_in_row(y + 1)   # skip rows where a queen already exists as the precondition

    for x in search_blank_in_row(y):
        put_queen(x, y)
        if put_queen_in_row(y + 1):
            return True
        else:
            elim_queen(x, y)    # can't put next queen; eliminate it
    return False    # all candidate blanks are failed


def main():
    # prepare
    n = int(input())
    for i in range(n):
        x, y = map(int, input().split())
        put_queen(x, y)
        skip_row.append(y)

    # 8 queen main
    put_queen_in_row(0)

    # draw queens
    board = [list('........') for x in range(8)]
    for q_x, q_y in queens:
        board[q_x][q_y] = 'Q'
    [print(''.join(x)) for x in board]
    return


main()

Submission status: Accepted

Solution code:
from itertools import permutations, product
from copy import deepcopy
k = int(input())
rc = [tuple(map(int, input().split())) for _ in range(k)]

for i in permutations(range(8), 8):#product(rx, ry):
    se = set(rc)
    bitmap = [0]*8
    #for i in bitmap: print(f'{i:08b}')
    for y,x in enumerate(i):
        bitmap[y] = 128>>x

    flag = False
    for i in se:
        if not (bitmap[i[0]] & 128>>i[1]):
            flag = True
            break
    if flag:
        continue
    left,down,right = 0,0,0
    for i in bitmap:
        if (left | down | right) & i:
            break
        left = (left | i)<<1
        down = down | i
        right = (right | i)>>1
    else:
        for i in bitmap:
            print('{:08b}'.format(i).replace('0','.').replace('1','Q'))

Submission status: Accepted

Solution code:
import itertools
import math
n = int(input())

placed = []

for i in range(n):
    a = list(map(int,input().split()))
    placed.append(a)

l = list(range(8))
perm = tuple(itertools.permutations(l))

for v in perm:
    flag = True
    
    for j in range(len(placed)):
        if v[placed[j][0]] != placed[j][1]:
            flag = False
            break 
    if flag == False:
        continue
    for i in range(8):
        k = 1
        # print(i)
        while  i+k<=7:
            # print(v,i,v[i],k,len(v))
            if i+k<=7:
                # print(i+k)
                if v[i+k] == v[i]+k or v[i+k] == v[i]-k:
                    flag = False
                    break
                # if v[i+k] == v[i]-k:
                #     flag = False
                #     break
            k += 1
        if flag == False:
            break
            
    if flag == True:
        # print(v)
        for r in range(8):
            for c in range(8):
                if c == v[r]:
                    print("Q",end = "")
                else:
                    print(".",end = "")
            print("")
                
        break
  
    # print(v[4],v)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from itertools import permutations

k = int(input())
queens_input = []
for _ in range(k):
    r, c = map(int, input().split())
    queens_input.append([r, c])
# print(k, queens_input)


def create_square(queens):
    square = [['.' for col in range(8)] for row in range(8)]
    for r, c in queens:
        square[r][c] = 'Q'
    return square


def print_square(square):
    for row in range(8):
        for col in range(8):
            print(square[row][col], end='')
        print('')


def includes(queens, queens_input):
    for q in queens_input:
        if q not in queens:
            return False
    return True


def calc_direction(queen):
    row, col = queen
    v, h, d_r, d_l = [], [], [[row, col]], [[row, col]]
    for i in range(8):
        v.append([i, col])
        h.append([row, i])
    for i in range(1, 8):
        if row - i >= 0 and col + i < 8:
            d_r.append([row - i, col + i])
        if row + i < 8 and col - i >= 0:
            d_r.append([row + i, col - i])
        if row - i >= 0 and col - i >= 0:
            d_l.append([row - i, col - i])
        if row + i < 8 and col + i < 8:
            d_l.append([row + i, col + i])
    return v, h, d_r, d_l


def count(direction, queens):
    res = 0
    for queen in queens:
        res += direction.count(queen)
    return res


def is_valid(queens):
    for queen in queens:
        v, h, d_r, d_l = calc_direction(queen)
        v_c, h_c = count(v, queens), count(h, queens)
        d_r_c, d_l_c = count(d_r, queens), count(d_l, queens)
        if not (v_c == 1 and h_c == 1 and d_r_c == 1 and d_l_c == 1):
            return False
    return True


perms = list(map(list, permutations(list(range(8)), 8)))
for perm in perms:
    queens = []
    for row in range(8):
        queens.append([row, perm[row]])
    if includes(queens, queens_input):
        if is_valid(queens):
            # print(f"queens = {queens}")
            square = create_square(queens)
            print_square(square)
            break

Submission status: Accepted

Solution code:
from itertools import permutations
k = int(input())


# 8*8行の間で何行目に何があるか
start_exists = [[] for _ in range(8)]
exists_rows = []
for _ in range(k):
    r, c = map(int, input().split())
    exists_rows.append(r)
    start_exists[r].append(c)

# print(start_exists)


def check_valid_positions(exist_positions):
    valid = True
    for start_position in exist_positions:
        for check_position in exist_positions:
            if start_position == check_position:
                continue
            if start_position[0] == check_position[0]:
                valid = False
            if start_position[1] == check_position[1]:
                valid = False
            if (start_position[0] - start_position[1]) == (check_position[0] - check_position[1]):
                valid = False
            if (start_position[0] + start_position[1]) == (check_position[0] + check_position[1]):
                valid = False
    return valid


# これですでに存在している行は除く
# [(7, 6, 5, 2, 1, 3, 4, 0), (7, 6, 5, 2, 1, 4, 0, 3)....]
queens_row_permutations = permutations(range(8))
ans = []
for queens_row_permutation in queens_row_permutations:
    exist_positions = []
    for i, row in enumerate(queens_row_permutation):
        if i in exists_rows:
            exist_positions.append([i, start_exists[i][0]])
        else:
            exist_positions.append([i, row])
    # print(exist_positions)
    # print(check_valid_positions(exist_positions))
    if check_valid_positions(exist_positions):
        ans = exist_positions
        break
    # squares = [[0 for _ in range(8)] for _ in range(8)]
    # for i, row in enumerate(queens_row_permutation):
    #     if i in exists_rows:
    #         squares[i][start_exists[i][1]] = 1
    #     else:
    #         squares[i][row] = 1
    # for j in range(8):
for position in ans:
    print(
        ''.join(['Q' if position[1] == i else '.' for i in range(8)]))

Submission status: Accepted

Solution code:
from copy import copy,deepcopy
import itertools
k=int(input())
b=[['.']*8 for i in range(8)]
R=set(range(8))
C=set(range(8))
p=set()
m=set()
for i in range(k):
    r,c=map(int,input().split())
    b[r][c]='Q'
    R.remove(r);C.remove(c)
    p.add(r+c)
    m.add(r-c)
for x in itertools.permutations(C):
    P=p.copy()
    M=m.copy()
    ok=True
    for r,c in zip(R,x):
        if r+c in P:
            ok=0
        P.add(r+c)
        if r-c in M:
            ok=0
        M.add(r-c)
    if(ok):
        for r,c in zip(R,x):
            b[r][c]='Q'
        break
for i in range(8):
    print(''.join(b[i]))