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:
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys
import random
import itertools

input = sys.stdin.readline
_NUMINT_ALL = list(range(10))
_START_TIME = time.time()


def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is not None:
        print(ans)


def solve():
    N = iip()[0]
    Q = iipt(N)

    d = [None] * 8

    for x, y in Q:
        d[x] = y

    #print(d)

    for pat in itertools.permutations(range(8)):
        flag = True
        xyl_p = [0] * 60
        xyl_m = [0] * 60

        for i, s in enumerate(pat):
            if d[i] is not None and d[i] != s: # 与えられた条件
                flag = False

                break
            else:
                #print(pat, "ok")
                pass


        for i, s in enumerate(pat):
            idp = i+s
            idm = i-s+14

            if xyl_p[idp] == 1 or xyl_m[idm] == 1:
                flag=False
                break

            xyl_p[idp] = 1
            xyl_m[idm] = 1


        if flag is True:
            for i in pat:
                print("."*(i) + "Q" + "."*(7-i))


    return



#####################################################ライブラリ集ここから




def kiriage_warizan(a, b):
    return -(-a//b)


def iip(listed=True):  # 数字のinputをlistで受け取る
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1 and listed is False:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=True, num_only=True):  # 縦向きに並んでいるデータをリストに落とし込む(iip利用)
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  # 最大公約数
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m

def time_debug_10percent():
    a = random.randint(0, 9)
    if a == 9:
        sys.exit()

def time_debug(t):
    time.sleep(_START_TIME + t - time.time())
    sys.exit()


def make_graph_edge_flat(N):  # グラフ作成のための辺をリストで返す
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  # タプルのリストを特定のインデックスでソートする
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  # リストの中身の個数を種類分けして辞書で返す
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  # listの中身を取り出す時、listからはみ出たり
    if index >= len(l):                      # マイナスインデックスになったりするのを防ぐ
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  # 文字列をソートする
    return "".join(sorted(s))


def iip_ord(startcode="a"):  # 文字列を数字の列に変換する(数字と文字は1:1対応)
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  # TrueFalseや1, 0をYesNoに変換する
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  # リストを平たくしてprintする(二次元リストを見やすくしたりとか)
    for i in s:
        print(i)


def bitall(N):  # ビット全探索用のインデックスを出力
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  # リストの中身をスペース区切りで出力する
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  # リストの中身を改行区切りで出力する
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  # 素因数分解
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  # nCrをmodを使って計算する
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):  #  modnにおける逆元を計算
    return power(n, mod - 2)


def power(n, p, mod_=mod):  # 繰り返し二乗法でn**p % modを計算
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left"): # 関数を二分探索
    l = left
    r = right
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if func(x) == target:
            return x
        elif func(x) > target:
            r = x
        else:
            l = x

    if side == "left" or func(x) == target:
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  # リストを二分探索
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                #for i in path: # 経路圧縮
                #    self.parent[i] = cur
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 8クイーン問題
from itertools import permutations
k = int(input())
S = set(tuple(map(int, input().split())) for _ in [0]*k)
A = set()

dirs = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
QUEEN = 2

for r, c in S:
    A.add((r, c))
    for dy, dx in dirs:
        y, x = r, c
        while 0 <= x+dx < 8 and 0 <= y+dy < 8:
            y += dy
            x += dx
            A.add((y, x))

for I in permutations(range(8)):
    T = set(s for s in S)

    for r, c in enumerate(I):
        if (r, c) in S:
            continue
        elif (r, c) in T or (r, c) in A:
            break

        for dy, dx in dirs:
            y, x = r, c
            while 0 <= x+dx < 8 and 0 <= y+dy < 8:
                y += dy
                x += dx
                if (y, x) in T:
                    break
            else:
                continue
            break
        else:
            T.add((r, c))
            continue
        break
    else:
        S = T
        break


for y in range(8):
    for x in range(8):
        if (y, x) in S:
            print('Q', end='')
        else:
            print('.', end='')
    print()

Submission status: Accepted

Solution code:
import math
import copy
import sys
import fractions
# import numpy as np
# import statistics
import decimal
import heapq
import collections
import itertools


# from operator import mul

# sys.setrecursionlimit(100001)


# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputIntList():
    outputDataList = []
    inputData = input().split()
    outputDataList = [int(n) for n in inputData]

    return outputDataList

def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

n = int(input())
obj = getSomeInputListInt(n)

data = [[] for _ in range(8)]
for x in range(8):
    for y in range(8):
        flg = True
        for o in obj:
            tmpx = o[0]-x
            tmpy = o[1]-y
            if tmpx == 0 or tmpy == 0 or abs(tmpx) == abs(tmpy):
                flg = False
                break

        if flg:
            data[x].append([x,y])



def checker(a, b_list):
    flg = True
    for b in b_list:
        tmpx = b[0] - a[0]
        tmpy = b[1] - a[1]
        if tmpx == 0 or tmpy == 0 or abs(tmpx) == abs(tmpy):
            flg = False
            break

    return flg

def printer(l):
    for x in range(8):
        for y in range(8):
            if [x,y] in l:
                print("Q", end="")
            else:
                print(".", end="")
        print("")


def search(cnt, candidate):
    if cnt == 8:
        printer(candidate)
        exit(0)
    if len(data[cnt]) == 0:
        search(cnt+1, candidate)


    for d in data[cnt]:
        if checker(d, candidate):
            tmp = copy.deepcopy(candidate)
            tmp.append(d)
            search(cnt+1, tmp)


search(0, obj)

Submission status: Accepted

Solution code:
N = 8
flag_row = [False]*N
flag_col = [False]*N
flag_diag_right = [False]*(2*N-1)
flag_diag_left  = [False]*(2*N-1)
B = [ [False for n in range(N)] for n in range(N)]

def ShowBoard():
    for i in range(N):
        for j in range(N):
            if B[i][j] :
                if flag_row[i] != j:
                    return

    for i in range(N):
        for j in range(N):
            if flag_row[i] == j:
                print("Q", end = "")
            else:
                print(".", end = "")
        print()

def SetQueen(i):
    if i == N  :
        ShowBoard()
        return

    for j in range(N):
        if flag_col[j] == False and flag_diag_left[i + j] == False and flag_diag_right[i - j + (N -1)] == False :

            flag_row[i] = j
            flag_col[j] = True
            flag_diag_left[i + j] = True
            flag_diag_right[i - j + (N -1)] = True

            SetQueen(i + 1)

            flag_row[i] = False
            flag_col[j] = False
            flag_diag_left[i + j] = False
            flag_diag_right[i - j + (N -1)] = False

def Main():
    K = int(input())

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

    SetQueen(0)

Main()

Submission status: Accepted

Solution code:
queenExists = [[False] * 8 for _ in range(8)]

n = int(input())
for _ in range(n):
    x, y = map(int, input().split())
    queenExists[y][x] = True


def dfs(queenExists, c):
    if c >= 8:
        return True

    # check if queen exists in column c
    isQueen = False
    for r in range(8):
        if queenExists[r][c] is True:
            isQueen = True
    if isQueen is True:
        return dfs(queenExists, c + 1)

    for r in range(8):

        # check if queen can be put on [r][c]
        checkOk = True
        # check horizon
        for i in range(8):
            if queenExists[r][i] is True:
                checkOk = False
                break
        # check diagonal
        d = [[1, 1], [1, -1], [-1, 1], [-1, -1]]
        for dx, dy in d:
            n_r, n_c = r + dy, c + dx
            while 0 <= n_r < 8 and 0 <= n_c < 8:
                if queenExists[n_r][n_c] is True:
                    checkOk = False
                    break
                n_r, n_c = n_r + dy, n_c + dx
        if checkOk is False:
            continue

        # now that we can put queen on [r][c]
        queenExists[r][c] = True
        if dfs(queenExists, c + 1):
            return True
        queenExists[r][c] = False


dfs(queenExists, 0)

for i in range(8):
    for j in range(8):
        if queenExists[j][i] is True:
            print("Q", end="")
        else:
            print(".", end="")
    print()

Submission status: Accepted

Solution code:
from itertools import permutations

BLANK = 0
Q = 1
WALL = 2

def to_board_pos(x, y):
    return x * 10 + y

def place_queen(pos, board):
    assert board[pos] != WALL
    if board[pos] == Q:
        return False, None

    board[pos] = Q
    directions = [-10, -9, 1, 11, 10, 9, -1, -11]
    for d in directions:
        restrict_board(pos, d, board)
    
    return True, board

def restrict_board(pos, direction, board):
    cur = pos+direction
    while board[cur] != WALL:
        board[cur] = Q
        cur += direction

def check(pattern, board):
    b = board[:]
    for i, p in enumerate(pattern):
        ok, b = place_queen(to_board_pos(i+1, p), b)
        if not ok:
            return False

    return True

def print_board(board):
    for i in range(10):
        for j in range(10):
            pos = to_board_pos(i, j)
            print(str(board[pos]) + " ", end="")
        print("")

    
n = int(input())
initial_queens = [(0, 0) for i in range(n)]
for i in range(n):
    x, y = map(int, input().split())
    initial_queens[i] = (x, y)

board = [BLANK] * 100
for i, _ in enumerate(board):
    if 0 <= i <= 9 or 90 <= i <= 99:
        board[i] = WALL
        continue

    if i % 10 == 0 or i % 10 == 9:
        board[i] = WALL
        continue

perm_seed = [i+1 for i in range(8)]
patterns = permutations(perm_seed)

ans = [0] * 8
for pattern in patterns:
    init_ok = True
    for iq in initial_queens:
        if pattern[iq[0]] != iq[1] + 1:
            init_ok = False
            break

    if init_ok:
        if check(pattern, board):
            ans = pattern
            break

for i, a in enumerate(ans):
    board[to_board_pos(i+1, a)] = Q

for i in range(1, 9):
    for j in range(1, 9):
        pos = to_board_pos(i, j)
        if board[pos] == BLANK:
            print(".", end="")
        elif board[pos] == Q:
            print("Q", end="")
    print("")

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    k = int(input())
    rc = [list(map(int, input().split())) for _ in range(k)]
 
    def dfs(d, perm):
        if d==8:
            ok = True
            for i in rc:
                if perm[i[0]]!=i[1]:
                    ok = False
            if ok:
                okok = True
                for j in range(7):
                    for k in range(j+1, 8):
                        if j-perm[j]==k-perm[k] or j+perm[j]==k+perm[k]:
                            okok = False
                if okok:
                    for j in range(8):
                        pos = perm[j]
                        print('.'*pos+'Q'+'.'*(7-pos))
            return perm
        else:
            for i in range(8):
                if i not in perm:
                    dfs(d+1, perm+[i])
    dfs(0, [])

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/13
import itertools


def check(Queens, L):
    # row
    for i in range(L):
        cnt = 0
        for j in range(L):
            if (i, j) in Queens:
                cnt += 1
        if cnt != 1:
            return False

    # colmn
    for j in range(L):
        cnt = 0
        for i in range(L):
            if (i, j) in Queens:
                cnt += 1
        if cnt != 1:
            return False

    # diagonally
    for i in range(L):
        cnt = 0
        for i in range(L):
            if (i, j) in Queens:
                cnt += 1
        if cnt != 1:
            return False

    for queen in Queens:
        i = queen[0] - 1
        j = queen[1] - 1
        while 0 <= i and 0 <= j:
            if (i, j) in Queens:
                return False
            i -= 1
            j -= 1
        i = queen[0] - 1
        j = queen[1] + 1
        while 0 <= i and j < 8:
            if (i, j) in Queens:
                return False
            i -= 1
            j += 1
        i = queen[0] + 1
        j = queen[1] - 1
        while i < 8 and 0 <= j:
            if (i, j) in Queens:
                return False
            i += 1
            j -= 1
        i = queen[0] + 1
        j = queen[1] + 1
        while i < 8 and j < 8:
            if (i, j) in Queens:
                return False
            i += 1
            j += 1

    return True


def print_result(Queens, L):
    for i in range(L):
        for j in range(L):
            if (i, j) in Queens:
                print('Q', end='')
            else:
                print('.', end='')
        print()


if __name__ == "__main__":

    num_of_queen = 8
    L = 8
    k = int(input())

    GivenQueens = set()
    for i in range(k):
        r, c = map(int, input().split())
        GivenQueens.add((r, c))

    A = [i for i in range(L)]
    for pernutated in itertools.permutations(A, L-k):
        Queens = set(GivenQueens)
        row = 0
        i = 0
        while len(Queens) < num_of_queen:
            if row not in list(map(lambda queen: queen[0], Queens)):
                Queens.add((row, pernutated[i]))
                i += 1
            row += 1

        if check(Queens, L):
            print_result(Queens, L)
            break

Submission status: Accepted

Solution code:
import itertools
import math
k = int(input())
# めんどくさいので最初に8クイーンが成立するパターンを計算しといて、入力にマッチするパターンを出力する
lis = [x for x in range(8)]
permutations_lis = itertools.permutations(lis)
ans = []
for zahyo in permutations_lis:
  #クイーンi は x,y = i,zahyo[i]にいる
  #nC2でabs(x1-x2)=abs(y1-y2) を検証
  ok =0
  for i in range(7):
    for j in range(i+1,8):
      if abs(i-j) != abs(zahyo[i]-zahyo[j]):
        ok += 1
      else: break
  if ok == 28:
    ans.append(zahyo)
    #print(ok,zahyo)
#print(len(ans))
input_zahyo = [-1] * 8
for i in range(k):
  x,y = map(int,input().split())
  input_zahyo[x] = y
for zahyo in ans:
  ok = 0
  for j in range(8):
    if input_zahyo[j] != -1 and zahyo[j] == input_zahyo[j]:
      ok += 1
  #print(ok,zahyo,input_zahyo)
  if ok == k:
    for i in range(8):
      for j in range(8):
        if zahyo[i] == j: print("Q",end="")
        else: print(".",end="")
      print("")
    exit()

Submission status: Accepted

Solution code:

import itertools
import collections

k = int(input())

Z = []

for kk in range(k):
    x, y = map(int, input().split())
    Z.append((x, y))

a = ()

for v in itertools.permutations(range(8)):
    X = []
    Y = []
    V = []
    for i, vv in enumerate(v):
        V.append((i, vv))
    flag = False
    for kk in range(k):
        if Z[kk] not in V:
            flag = True
            break
    if flag:
        continue
    for i, vv in enumerate(v):
        X.append(i+vv)
        Y.append(i-vv)
    x = collections.Counter(X)
    y = collections.Counter(Y)
    if x.most_common()[0][1] >= 2 or y.most_common()[0][1] >= 2:
        continue
    a = v
    break

for i in range(8):
    print('.'*a[i] + 'Q' + '.'*(7-a[i]))

Submission status: Accepted

Solution code:
import itertools

n = int(input())
x = [[0]*2 for _ in range(n)]
for i in range(n):
    x[i][0],x[i][1] = map(int,input().split())
y = []
    
a = [i for i in range(8)]
r = list(itertools.permutations(a,len(a)))

for i in r:
    fl = 1
    for j in range(n):
        if i[x[j][0]] != x[j][1]: 
            fl = 0
    if fl == 1:
        an = 1
        for j in range(8):
            for k in range(8):
                if j == k:
                    continue
                else:
                    if i[j]+j == i[k]+k:
                        an = 0
                    if k-j == i[k] - i[j]:
                        an = 0
        if an == 1:
            y = list(i)
            break
            
ans = [['.']*8 for i in range(8)]
for i in range(8):
    ans[i][y[i]] = 'Q'
    print(''.join(ans[i]))

Submission status: Accepted

Solution code:
import itertools
import copy


def is_safe(qweens):
    x = []
    y = []
    for q in qweens:
        x.append(q[0])
        y.append(q[1])
    if len(set(x)) + len(set(y)) != len(qweens) * 2:
        return False
    for q1, q2 in itertools.combinations(qweens, 2):
        slope = (q1[0] - q2[0]) / (q1[1] - q2[1])
        if slope == 1 or slope == -1:
            return False
    return True


def print_boad(qweens):
    for r in range(8):
        for c in range(8):
            if (r, c) in qweens:
                print('Q', end='')
            else:
                print('.', end='')
        print('')


k = int(input())
cand = [[(r, c) for c in range(8)] for r in range(8)]
init_qweens = []
for _ in range(k):
    pos = tuple(map(int, input().split()))
    for r in range(8):
        for c in range(8):
            try:
                cand[r].remove((pos[0], c))
            except ValueError:
                pass
            try:
                cand[r].remove((r, pos[1]))
            except ValueError:
                pass
    init_qweens.append(pos)

for r in range(7, -1, -1):
    if cand[r] == []:
        cand.pop(r)

qweens = []
for per in itertools.permutations([i for i in range(8 - k)]):
    qweens = copy.deepcopy(init_qweens)
    for r, c in enumerate(per):
        qweens.append(cand[r][c])

    if is_safe(qweens):
        break

print_boad(qweens)

Submission status: Accepted

Solution code:
from itertools import permutations as perm
from copy import deepcopy as copy


def inpl():
    return tuple(map(int, input().split()))


def dfs(XY, flag):
    # print(len(XY), XY, sum(f.count(True) for f in flag))
    if len(XY) == 8:
        # print("here")
        return XY

    for i in range(8*8):
        x = i // 8
        y = i % 8
        if flag[x][y] is False:
            continue
        f, new_f = toFalse(x, y, flag, XY)
        if f is False:
            continue
        tmp = copy(XY)
        tmp.add((x, y))
        # print(tmp)
        ret = dfs(tmp, new_f)
        if ret is None:
            continue
        else:
            return ret
    return None


def toFalse(x, y, f, XY):
    flag = copy(f)
    ddd = [[1, 1], [-1, -1], [1, -1], [-1, 1]]
    for i in range(8):
        # print(x, y, i, flag)
        if (i, y) in XY or (x, i) in XY:
            return False, flag
        else:
            flag[i][y] = False
            flag[x][i] = False

        if i == 0:
            continue
        for dx, dy in ddd:
            if not(0 <= x + i*dx < 8 and 0 <= y + i*dy < 8):
                continue
            elif (x+i*dx, y+i*dy) in XY:
                return False, flag
            else:
                flag[x+i*dx][y+i*dy] = False
    return True, flag


N = int(input())
XY = [inpl() for _ in range(N)]


flag = [[True for _ in range(8)] for i in range(8)]
# print(flag)
for x, y in XY:
    f, flag = toFalse(x, y, flag, set())

ans = dfs(set(XY), flag)

# print(ans)
chess = [["."]*8 for i in range(8)]
for x, y in ans:
    chess[x][y] = "Q"
for c in chess:
    print("".join(c))

Submission status: Accepted

Solution code:
# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd

def resolve():
    N = 8

    # すでに配置されたクイーンの効きが及ばない位置であればTrueを返す
    def check(row, FR):
        # まず横の効きで取られないかチェックする
        # すでにクイーンの配置された行だとダメ
        if row in FR:
            return False

        # 次に斜めの効きで取られないかチェックする
        # enumerate関数により、リストFRの添字fc(filled_column)と要素fr(filled_row)を取得
        for fc, fr in enumerate(FR):
            # distだけ離れた列fcが着目されている
            dist = len(FR) - fc
            # 左上あるいは左下にクイーンがあったらアウト
            if (row == fr - dist) or \
                    (row == fr + dist):
                return False
        return True

    # クイーンの可能な配置をすべてprintする関数
    def search(FR):
        # FRはFilled Rowsの略。
        # 第column列のFR[column]行目にすでにクイーンが配置済みであることを意味する。

        # すべての列に配置でき次第出力。クイーンのある位置を黒く塗りつぶす
        if len(FR) == N:
            for i in range(M):
                if FR[X[i]] != Y[i]:
                    break
                elif i==M-1:
                    for k in range(N):
                        for j in range(N):
                            print('Q' if FR[k] == j else '.', end='')
                        print()
                    return

        # クイーンを配置した行数を格納するリストFRを作成
        for row in range(N):
            if check(row, FR):
                FR.append(row)
                # 再帰的に探索する。「以下同様」という意味。
                search(FR)
                # どの行に入れても無理だと判明したら、
                # 最後の行をpopし、もう１回ループを回して別の行でいけないかと模索する
                FR.pop()


    M=int(input())
    X,Y = [0] * M, [0] * M
    for i in range(M):
        X[i], Y[i] = map(int, input().split())

    search([])


resolve()

Submission status: Accepted

Solution code:
import itertools

k = int(input())
rc_sub = {}
for _ in range(k):
    r, c = [int(i) for i in input().split()]
    rc_sub[r] = c
board = [["."]*8 for _ in range(8)]

for pp in itertools.permutations(range(8), 8):
    rc = {i: p for (i, p) in enumerate(pp)}
    ok = True
    # 初期配置条件を満たさない場合スキップ
    for k, v in rc_sub.items():
        if rc[k] != v:
            ok = False
            break
    if not ok:
        continue

    # 配置条件（斜め）を満たさない場合スキップ
    for (p1, p2) in itertools.combinations(rc.items(), 2):
        if (p2[0] - p1[0]) / (p2[1] - p1[1]) in (1, -1):
            ok = False
            break

    if ok:
        for k, v in rc.items():
            board[k][v] = "Q"
        break

for line in board:
    print(*line, sep="")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from itertools import permutations
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    mx=[1,1,-1,-1]
    my=[1,-1,1,-1]
    def check(tmp_board):
        for y,x in enumerate(tmp_board):
            d=[1,1]
            for j in range(7):
                for k in range(4):
                    c=[y+d[0]*my[k],x+d[1]*mx[k]]
                    if 0<=c[0]<=7 and 0<=c[1]<=7 and tmp_board[c[0]]==c[1]:
                        return False
                d[0]+=1
                d[1]+=1
        return True
    
    
    k=int(input())
    c=[['.']*8 for _ in range(8)]
    for i in range(k):
        R,C=map(int,input().split())
        c[R][C]='Q'
    yoko=list(range(8))
    tate=list(range(8))
    board=[-1]*8
    try:
        for y,l in enumerate(c):
            for x,s in enumerate(l):
                if s=='Q':
                    tate.remove(y)
                    yoko.remove(x)
                    board[y]=x
        for p in permutations(yoko):
            tmp_board=board[:]
            for i,x in enumerate(tate):
                tmp_board[x]=p[i]
            if check(tmp_board):
                for x in tmp_board:
                    ans=['.']*8
                    ans[x]='Q'
                    print(''.join(ans))
                break
        else:
            raise Exception
    except:
        print('No Answer')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
A = [tuple(int(i) for i in input().split()) for _ in range(n)]

ban = [['.'] * 8 for i in range(8)]

# for i in A:
#     ban[i[0]][i[1]] = '.'

for i in itertools.permutations(range(8)):
    flg = 0
    for j in A:
        if(i[j[0]] != j[1]):
            flg = 1
            break
    if flg:
        continue

    nc = []
    nc2 = []
    for k,j in enumerate(i):
        nc.append(k + j)
        nc2.append(k-j)
    
    if(len(set(nc)) != 8) |(len(set(nc2)) != 8) :
        continue

    else:
        for k,j in enumerate(i):
            ban[k][j] = 'Q'
        break
    

for i in ban:
    for j in i:
        print(j,end='')
    print('')

Submission status: Accepted

Solution code:
import itertools
K = int(input())
Q = [[int(i) for i in input().split()] for _ in range(K)]
li = list(range(8))
P = itertools.permutations(li, 8)

for p in P:
    is_ok = True
    for row, col in Q:
        if(p[row]!=col):
            is_ok = False
            break
    else:
        for ind,i in enumerate(p):
            for x in range(8):
                if(ind==x):
                    continue
                if(p[x]==i+x-ind or p[x]==i-(x-ind)):
                    is_ok = False
    if(is_ok):
        break
ans = [['.']*8 for _ in range(8)]
for ind, i in enumerate(p):
    ans[ind][i] = 'Q'
    print(*ans[ind], sep='')

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    k = I()
    n = 8
    a = [-1]*n
    for i in range(k):
        y,x = LI()
        a[y] = x
    for p in permutations(range(n)):
        f = 0
        for i in range(n):
            if a[i] >= 0 and a[i] != p[i]:
                f = 1
                break
            for j in range(i):
                if abs(i-j) == abs(p[i]-p[j]):
                    f = 1
                    break
            if f:
                break
        if f:
            continue
        ans = [["Q" if p[i] == j else "." for j in range(n)] for i in range(n)]
        for i in ans:
            print(*i,sep="")
        return
    return

#Solve
if __name__ == "__main__":
    solve()