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
k = int(input())
coords = [tuple(map(int, input().split())) for _ in range(k)]

for item in itertools.permutations(range(8)):
    for x, y in coords:
        if item[x] != y:
            break
    else:
        for i, j in enumerate(item):
            for k in range(1, 8):
                if i+k < 8:
                    if item[i+k] == j+k: break
                    if item[i+k] == j-k: break
                if i-k >= 0:
                    if item[i-k] == j+k: break
                    if item[i-k] == j-k: break
            else:
                continue
            break
        else:
            break

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

Submission status: Accepted

Solution code:
import itertools
queen=[-1]*8
N=int(input())
de=[]
for i in range(N):
    x,y =list(map(int,input().split()))
    de.append(x)
    queen[x]=y
def check(n):#nはクイーンの個数
    for y in range(n):
        if crshu(queen[y],y):return False
    return True
def crshu(x,y):
    for y1 in range(y):
        x1=queen[y1]
        if x1-y1==x-y or x1+y1==x+y:return True
    return False
def board():
    king=[]
    for i in range(8):
        king.append([i,queen[i]])
    for i in range(8):
        for j in range(8):
            if [i,j] in king:
                print("Q",end="")
            else:
                print(".",end="")
        print()
    exit()

def search(n,y):
    if n==y:
        if check(8):
            board()
    else:
        if y in de:
            search(n,y+1)
        else:
            for i in range(n):
                if i not in queen :
                    queen[y]=i
                    search(n,y+1)
                    for l in range(y+1,8):
                        if l not in de:
                            queen[l]=-1
search(8,0)

Submission status: Accepted

Solution code:
import itertools

k = int(input())

area = [["."]*8 for i in range(8)]

X = set(range(8))
Y = set(range(8))
A = set()
B = set()

for i in range(k):
    x, y = map(int, input().split())
    area[x][y] = "Q"

    X.remove(x)
    Y.remove(y)
    A.add(x-y)
    B.add(x+y)
for v in itertools.permutations(Y):
    ok = 1
    A_ = A.copy()
    B_ = B.copy()
    for x, y in zip(X, v):
        if x-y in A_ or x+y in B_:
            ok = 0
            break

        A_.add(x-y)
        B_.add(x+y)
    
    if ok:
        for x, y in zip(X, v):
            area[x][y] = "Q"
        break

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

Submission status: Accepted

Solution code:
import itertools
K=int(input())
R=[]
C=[]
RCd={}
rflag=[ 0 for _ in range(8) ]
for i in range(K):
  r,c=map(int,input().split())
  R.append(r)
  C.append(c)
  RCd[r]=c
  rflag[r]=1

l=[ i for i in range(8) ]
P=itertools.permutations(l,8)
for p in P:
  p=list(p)
  flag=0
  for i in range(8):
    if rflag[i]==1 and p[i]!=RCd[i]:
      flag=1
      break
    for j in range(8):
      if i==j: continue
      if abs(i-j)==p[i]-p[j]:
        flag=1
        break
  #cleared
  if flag==1:continue
  for i in range(8):
    ans='........'
    print(ans[:p[i]]+'Q'+ans[p[i]+1:])
  exit()

Submission status: Accepted

Solution code:
from itertools import permutations

k = int(input())

points = {tuple(map(int, input().split())) for _ in range(k)}

for perm in permutations(range(8), 8):
    test = {(i, perm[i]) for i in range(8)}
    if test & points == points:
        flg = 0
        for x, y in test:
            diag = {(x - i, y - i) for i in range(1, min(x, y) + 1)} | {(x + i, y + i) for i in range(1, min(7 - x, 7 - y) + 1)} | {(x - i, y + i) for i in range(1, min(x, 7 - y) + 1)} | {(x - i, y + i) for i in range(1, min(7 - x, y) + 1)}
            if diag & test == set():
                flg += 1
        if flg == 8:
            ans = test
            break

for i in range(8):
    col = ""
    for j in range(8):
        if (i,j) in ans:
            col += "Q"
        else:
            col += "."
    print(col)

Submission status: Accepted

Solution code:
from itertools import permutations

k = int(input())
points = [tuple(map(int, input().split(' '))) for _ in range(k)]

indexes = set(range(8))
xs = indexes - {x for _, x in points}
ys = list(indexes - {y for y, _ in points})

result = None
for x_indexes in permutations(xs):
    selected = set(points)
    for i, x in enumerate(x_indexes):
        y = ys[i]
        for sy, sx in selected:
            if abs(sx - x) == abs(sy - y):
                break
        else:
            selected.add((y, x))
            continue
        break
    else:
        result = selected
        break

rows = []
for _ in range(8):
    row = ['.'] * 8
    rows.append(row)

for y, x in result:
    rows[y][x] = 'Q'

for row in rows:
    print(''.join(row))

Submission status: Accepted

Solution code:
board = [['#']*8 for i in range(8)]
n = int(input())
v1=[0]*8
v2=[0]*8
v3=[0]*16
v4=[0]*16


def dot(y,x):
    for j in range(8):
        board[y][j]='.'
        board[j][x]='.'
    for i in range(1,min(x,y)+1):
        board[y-i][x-i]='.'
    for i in range(1,min(7-x,y)+1):
        board[y-i][x+i]='.'
    for i in range(1,min(x,7-y)+1):
        board[y+i][x-i]='.'
    for i in range(1,min(7-x,7-y)+1):
        board[y+i][x+i]='.'
    board[y][x]='Q'
st=set()
ans=[]

def dfs(now,k,stock):
    if now == 8:
        ans.append(list(stock))
        return stock
    if not li[now]:
        dfs(now+1,k,stock)
    for i in li[now]:
        x,y1,y2=i
        if v2[x]==0 and v3[y1+7]==0 and v4[y2]==0:
            stock.add((now,x))
            v2[x]=1
            v3[y1+7]=1
            v4[y2]=1
            dfs(now+1,k,stock)
            v2[x]=0
            v3[y1+7]=0
            v4[y2]=0
            stock.remove((now,x))

for i in range(n):
    y , x = map(int, input().split())
    dot(y,x)
    v1[y]=1
    v2[x]=1
    v3[y-x+7]=1
    v4[y+x]=1

li=[[]for i in range(8)]
for i in range(8):
    for j in range(8):
        if board[i][j]=='#':
            li[i].append((j,i-j,j+i))

dfs(0,2,st)

for i in ans[0]:
    y,x=i
    dot(y,x)

for i in board:
    print(''.join(i))

Submission status: Accepted

Solution code:
from itertools import permutations


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


N = int(input())

# 0～7のリストを作成する
R = list(range(8))
C = list(range(8))

# R,Cから既にクイーンが置いてあるマス目を削除する
queen = []
for _ in range(N):
    r, c = map(int, input().split())
    queen.append((r, c))
    R.remove(r)
    C.remove(c)

# Rの全ての順列を作成する
for columns in permutations(C):
    # tmp_queenに8個のクイーンの位置を格納する
    tmp_queen = queen[:]
    for r, c in zip(R, columns):
        tmp_queen.append((r, c))
    for r1, c1 in tmp_queen:
        for r2, c2 in tmp_queen:
            if r1 == r2 and c1 == c2:
                continue
            else:
                if r1 == r2 or c1 == c2:
                    break
                if r1 + c1 == r2 + c2 or r1 - c1 == r2 - c2:
                    break
        else:
            continue
        break
    else:
        board = [''.join('Q' if (r, c) in tmp_queen else '.' for c in range(8))
                 for r in range(8)]
        print(*board, sep='\n')
        exit(0)

Submission status: Accepted

Solution code:
#from math import gcd

from math import factorial as f

from math import ceil,floor,sqrt


import bisect
import re
import heapq


from copy import deepcopy
import itertools
from itertools import permutations

from sys import exit

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


yes = "Yes"
no = "No"




def main():
    n = ii()
    donelist = []
    for i in range(n):
        tmp = li()
        donelist.append(tmp)

    anslist = [['.' for i in range(8)] for j in range(8)]


    for i in permutations(range(8)):
        lli = list(i)
        flag = False
        for tmp in donelist:
            if lli[tmp[0]] != tmp[1]:
                flag = True
        if flag:
            continue

        wa = []
        sa = []
        for e,tmp in enumerate(lli):
            if (tmp-e in sa) or (tmp+e in wa):
                flag = True
                break
            wa.append(tmp+e)
            sa.append(tmp-e)
        if not flag:
            for e,tmp in enumerate(lli):
                anslist[e][tmp] = 'Q'
                print(''.join(anslist[e]))
            exit()









main()

Submission status: Accepted

Solution code:
import sys
import itertools


input = sys.stdin.readline


def cannot_attack(Q):
    for i in range(7):
        sx, sy = Q[i]
        for j in range(i+1, 8):
            tx, ty = Q[j]
            if abs(tx-sx) == abs(ty-sy):
                return False
    return True


def include_fq(sq):
    for e in fq:
        if e not in sq:
            return False
    return True


def main():
    Q = []
    for p in itertools.permutations(range(8)):
        Q = [(i, p[i]) for i in range(8)]
        if cannot_attack(Q) and include_fq(set(Q)):
            break
    for y, x in Q:
        print("."*x+"Q"+"."*(7-x))


if __name__ == "__main__":
    K = int(input())
    fq = [tuple(map(int, input().split())) for _ in range(K)]
    main()

Submission status: Accepted

Solution code:
def putQueen(i):
    while i < 8 and row[i]:i += 1
    if i == 8:
        for i in range(8):
            print(''.join(queen[i]))
    for j in range(8):
        if col[j] or dpos[i+j] or dneg[i-j+7]: continue
        queen[i][j] = 'Q'
        row[i] = col[j] = dpos[i+j] = dneg[i-j+7] = 1
        putQueen(i+1)
        queen[i][j] = '.'
        row[i] = col[j] = dpos[i+j] = dneg[i-j+7] = 0

k = int(input())
row = [0] * 8
col = [0] * 8
dpos = [0] * 15
dneg = [0] * 15
queen = [['.' 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] = 1
    queen[r][c] = 'Q'

putQueen(0)

Submission status: Accepted

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

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

X = [[False for _ in range(N)] for _ in range(N)]

def printBoard():
    i,j = 0, 0
    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):
            print("Q" if row[i]==j else ".", end='')
        print()
            

def recursive(i):
    j = 0

    if i==N:
        printBoard()
    
    else:
        for j in range(N):
            if NOT_FREE == col[j] or \
               NOT_FREE == dpos[i+j] or \
               NOT_FREE == dneg[i-j+N-1]:
               continue
            row[i] = j; col[j] = dpos[i+j] = dneg[i-j+N-1] = NOT_FREE
            recursive(i+1)
            row[i] = col[j] = dpos[i+j] = dneg[i-j+N-1] = FREE

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

recursive(0)

Submission status: Accepted

Solution code:
class eight_Q:
    #Free = 'Free', NOT_Free = 'NotFree'
    N = 8

    def __init__(self):
        #self.position = [['Free' for i in range(self.N)] for j in range(self.N)]
        self.row = [-1 for _ in range(self.N)]
        self.col = ['Free' for _ in range(self.N)]
        self.dpos = ['Free' for _ in range(self.N*2 -1)]
        self.dneg = ['Free' for _ in range(self.N*2 -1)]
        self.initial = [-1 for _ in range(self.N)]

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

    def putQueen(self, i):
        for j in range(self.N):
            #print(j)
            if i == self.N:
                return 'Success'
            if self.initial[i] == j:
                if self.putQueen(i+1) == 'Success':
                    return 'Success'
                else:
                    continue
            if self.col[j] == 'Free' and self.dpos[i+j] == 'Free' and self.dneg[i-j+(self.N-1)] == 'Free':
                #put queen at (i, j)
                self.row[i] = j
                self.col[j] = 'NotFree'
                self.dpos[i+j] = 'NotFree'
                self.dneg[i-j+(self.N-1)] = 'NotFree'
                #try the next row
                if i == self.N-1:
                    return 'Success'
                else:
                    if self.putQueen(i+1) == 'Success':
                        return 'Success'
                    #remove the queen at (i, j) for backtracking
                    else:
                        self.row[i] = -1
                        self.col[j] = 'Free'
                        self.dpos[i+j] = 'Free'
                        self.dneg[i-j+(self.N-1)] = 'Free'

        return 'Fail'

    def printBoard(self):
        #print(self.row)
        for i in range(self.N):
            for j in range(self.N):
                if self.row[i] == j:
                    print("Q",end='')
                elif self.initial[i] == j:
                    print("Q",end='')
                else:
                    print(".",end='')
            print()


if __name__ == "__main__":
    eightQueen = eight_Q()
    k = int(input())

    for i in range(k):
        _i, _j = (int(z) for z in input().split())
        eightQueen.initQueen(_i, _j)
    if eightQueen.putQueen(0) == 'Success':
        eightQueen.printBoard()
        #print(eightQueen.row)
    else:
        print("Fail to put queen")
        #print(eightQueen.row)

Submission status: Accepted

Solution code:
# バックトラック法
class EightQueens:
    def __init__(self,p):
        self.p = p
        # 前提 8*8の盤
        self.N = 8
        # 下準備
        # row[k] : k行目におけるクイーンの列番号
        self.row = [None] * 8
        # col[n] : n列目上にクイーンがなければFREE,あればNOT_FREE,それが8列分
        self.col = ['FREE'] * 8
        # 8 * 8 のマスに対角線を引いていくと15本引くことができる
        # dpos : 45度方向の対角線　dneg : 135度方向の対角線
        self.dpos = ['FREE'] * 15
        self.dneg = ['FREE'] * 15

        # 入力された位置にクイーンを置く
        i = 0
        while i < len(p):
            self.row[p[i][0]] = p[i][1]
            self.col[p[i][1]] = self.dpos[p[i][0] + p[i][1]] = self.dneg[p[i][0] - p[i][1] + self.N - 1] = 'NOT_FREE'
            i = i + 1


        # self.printBoard()

    """
    盤面の状態を表示
    """
    def printBoard(self):
        i = 0
        while i < self.N:
            j = 0
            while j < self.N:
                if j == self.row[i]:
                    print("Q", end="")
                # elif self.col[j] == 'NOT_FREE' or self.dpos[i+j] == 'NOT_FREE' or self.dneg[i-j + self.N-1] == 'NOT_FREE':
                    # print("N ", end="")
                else:
                    print(".", end="")
                    #print("F ", end="")
                j = j + 1
            print()
            i = i + 1
        return

    def putQueen(self,i):
        N = self.N

        # 初期化で置かれたクイーンだったらスキップ
        k = 0
        while k < len(self.p):
            if i == self.p[k][0]:
                i = i + 1
                k = 0
            k = k + 1


        # iが8(9行目)に到達したら終了
        if i == N:
            # print("解を発見")
            self.printBoard()
            return

        j = 0
        while j < N :
            # print(str(i)+", "+str(j))
            # self.printBoard()

            # 置こうとした位置がそれ以前の行のクイーンの領域だったら次の列へスキップ
            if self.col[j] == 'NOT_FREE' or self.dpos[i+j] == 'NOT_FREE' or self.dneg[i-j + N-1] == 'NOT_FREE':
                # print("置けません")
                j = j + 1
                continue

            # クイーンを(i,j)に置く
            self.row[i] = j

            # print()
            self.col[j] = self.dpos[i+j] = self.dneg[i-j+N-1] = 'NOT_FREE'
            # 次の行にクイーンを置くことを試みる（ダメだったら戻る）
            self.putQueen(i+1)
            # バックトラックキングのために(i,j)からクイーンを取り除く
            self.col[j] = self.dpos[i+j] = self.dneg[i-j+N-1] = 'FREE'
            j = j + 1
        return





def main():
    p = []  ##appendのために宣言が必要
    # 入力受付
    k = int(input())
    i = 0
    while i < k:
        try:
            p.append(list(map(int, input().split())))
            i = i + 1
        except:
            break;

    # 読み込み完了
    # pを行でソート
    p.sort()
    q = EightQueens(p)
    q.putQueen(0)
    return






if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
# sys.stdin = open('input.txt')

def print_board(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:
                print('Q', end='')
            else:
                print('.', end='')
        print('')

def set_queen(i, j):
    row[i] = j
    col[j] = NOT_FREE
    dpos[i+j] = NOT_FREE
    dneg[i-j+n-1] = NOT_FREE

def remove_queen(i, j):
    row[i] = FREE
    col[j] = FREE
    dpos[i+j] = FREE
    dneg[i-j+n-1] = FREE

def recursive(i):
    if i == n:
        print_board(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
        set_queen(i, j)
        recursive(i+1)
        # 以下の行は、i+1 行目にクイーンを配置できなかったときのみ実行される
        remove_queen(i, j)
    # for を最後まで実行できた場合、クイーンの配置ができなかったことになる (i 行目についてすべての列 (j) を試したが NG)


n = 8
FREE = -1
NOT_FREE = 1

col = []
row = []
dpos = []
dneg = []
board = [[False] * n for i in range(n)]

for i in range(n):
    col.append(FREE)
    row.append(FREE)
for i in range(2 * n - 1):
    dpos.append(FREE)
    dneg.append(FREE)

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

recursive(0)

Submission status: Accepted

Solution code:
import itertools
def I(): return int(input())
def LI(): return list(map(int,input().split()))
k = I()
rc = [LI() for _ in range(k)]
for a in itertools.permutations(range(8)):
    XY = [[x,y] for x,y in enumerate(a)]
    if len(set([x+y for x,y in XY])) !=8 or len(set([x-y for x,y in XY])) !=8:
        continue
    count = 0
    for r,c in rc:
        if [r,c] in XY:
            count += 1
    if count !=k:
        continue
    board = [['.' for _ in range(8)] for _ in range(8)]
    for x,y in XY:
        board[x][y] = 'Q'
    break
for b in board:
    print(*b,sep='')

Submission status: Accepted

Solution code:
N = int(input())

board_size = 8
board = [[ '.' for _ in range(board_size)] for _ in range(board_size)]

def print_board(board):
    for bb in board:
        line = ""
        for b in bb:
            line = line + b
        print(line)

#print_board(board)

Q_list = list()
for _ in range(N):
 Q_list.append(tuple(map(int, input().split() )) )
#print(Q_list)

skip_raws = list()
for (r,c) in Q_list:
    board[r][c] = "Q"
    skip_raws.append(r)


def is_enable_put(r, c, board):
    ok = True
    
    for i in range(board_size):
        # horizontal search
        if board[r][i] == "Q" and i != c:
            ok = False
            break
        # vertical search
        if board[i][c] == "Q" and i != r:
            ok = False
            break
        #
        if i > 0:
            if r-i >= 0 and c-i >= 0 \
            and board[r-i][c-i] == "Q":
                ok = False
                break
            if i+r < board_size and i+c < board_size \
            and board[i+r][i+c] == "Q":
                ok = False
                break
            if r-i >= 0 and c+i < board_size \
            and board[r-i][c+i] == "Q":
                ok = False
                break
            if r+i < board_size and c-i >= 0 \
            and board[r+i][c-i] == "Q":
                ok = False
                break
    return ok

import copy
def queen(r, qboard):
    # print("---", r)
    # print_board(qboard)
    if r == board_size:
        print_board(qboard)
        return
    elif r in skip_raws:
        queen(r+1,qboard)
        return

    else:
        for c in range(board_size):
            if is_enable_put(r, c, qboard) == False: continue
            else:
                tmp_board = copy.deepcopy(qboard)
                tmp_board[r][c] = "Q"
                queen(r+1, tmp_board)

queen(0,board)

Submission status: Accepted

Solution code:
k = int(input())
q = [list(map(int, input().split())) for _ in range(k)]
import itertools

row = list(range(0,8))
for i in q:
    row.remove(i[0])
col = list(range(0,8))
for i in q:
    col.remove(i[1])

for i in itertools.permutations(list(range(0,8-k)),8-k):
    queens = []
    for j in range(k):
        queens.append(q[j])
    for j in range(8-k):
        queens.append([row[j],col[i[j]]])
    flg = True
    for j in itertools.combinations(queens,2):
        if abs((j[0][0]-j[1][0])/(j[0][1]-j[1][1])) == 1:
            flg = False
    if flg == True:
        break

# print(queens)
lit = [[]  for _ in range(8)]
for i in range(8):
    for j in range(8):
        lit[i].append('.')
for i in queens:
    lit[i[0]][i[1]] = 'Q'

for i in range(8): print(''.join(map(str,lit[i])))

Submission status: Accepted

Solution code:
from itertools import product

def setq(ri,ci,krc):
    for ir in range(8):
        if ir!=ri:
            if krc[ir*8+ci]=="Q":
                return False,krc
            else:
                krc[ir*8+ci]="X"
    for ic in range(8):
        if ic!=ci:
            if krc[ri*8+ic]=="Q":
                return False,krc
            else:
                krc[ri*8+ic]="X"
    for ix in range(-7,7,1):
        ir=ri+ix
        ic=ci+ix
        if 0<=ir and ir<=7 and ir!=ri:
            if 0<=ic and ic<=7 and ic!=ci:
                if krc[ir*8+ic]=="Q":
                    return False,krc
                else:
                    krc[ir*8+ic]="X"
        ir=ri-ix
        ic=ci+ix
        if 0<=ir and ir<=7 and ir!=ri:
            if 0<=ic and ic<=7 and ic!=ci:
                if krc[ir*8+ic]=="Q":
                    return False,krc
                else:
                    krc[ir*8+ic]="X"
    return True,krc

def chki(i,krc):
    krc=[""]*64
    for j in range(8):
        krc[j*8+i[j]]="Q"
        bl,krc=setq(j,i[j],krc)
#        print(j,bl)
#        prk(krc)
        if not bl :
#            print(bl,i,"-------------------")
#            prk(krc)
            return False
#    print(bl,i,"-------------------")
#    prk(krc)
    return True

        
def prk(krc2):
    for i in range(8):
        print(krc2[i*8:(i+1)*8])        
    

icase=0
kr=[[] for i in range(8)]

if icase==0:
    k=int(input())
    krc=[""]*64
    for i in range(k):
        ri,ci=map(int,input().split())
        krc[ri*8+ci]="Q"
        setq(ri,ci,krc)
        kr[ri].append(ci)
elif icase==1:
    k=2
    krc=[""]*64
    ri,ci=2,2
    krc[ri*8+ci]="Q"
    setq(ri,ci,krc)
    kr[ri].append(ci)
    ri,ci=5,3
    krc[ri*8+ci]="Q"
    setq(ri,ci,krc)
    kr[ri].append(ci)
                
#prk(krc)

icnt=0

for ir in range(8):
    for ic in range(8):
        i=ir*8+ic
        if krc[i]=="":
            kr[ir].append(ic)
            
for i in product(kr[0],kr[1],kr[2],kr[3],kr[4],kr[5],kr[6],kr[7]):
    yn=""
    krc2=[""]*64
    if not chki(i,krc2):
        yn="no"
        continue
    else:
        break
if yn!="no":
    for ir in range(8):
        sti=["."]*8
        sti[i[ir]]="Q" 
        stii="".join(sti)
        print(stii)

Submission status: Accepted

Solution code:
from itertools import groupby, accumulate, product, permutations, combinations
from copy import copy, deepcopy
def solve():
    k = int(input())
    minus = []
    plus = []
    dic = {}
    for i in range(k):
        r,c = map(int, input().split())
        dic[r] = c
        minus.append(r-c)
        plus.append(r+c)
    for p in permutations(range(8),8):
        mi = copy(minus)
        pl = copy(plus)
        for i in range(8):
            if i in dic:
                if dic[i]!=p[i]:
                    break
                else:
                    continue
            mi.append(i-p[i])
            pl.append(i+p[i])
        else:
            if len(set(mi))==8 and len(set(pl))==8:
                break
    ans = []
    for i in p:
        row = ['.']*8
        row[i] = 'Q'
        ans.append(''.join(row))
    return ans
print(*solve(),sep='\n')

Submission status: Accepted

Solution code:
def main():
    import itertools

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

    eight_lis = [x for x in range(8)]
    per_lis = itertools.permutations(eight_lis)



    for test in per_lis:
        #print(test)
        cnt = 0
        tmp = 0
        for queen_in in cr_lis:
            if test[queen_in[0]] != queen_in[1]:
                cnt += 1
        if cnt > 0:
            continue
        zero_lis_1 = [0 for _ in range(8)]
        zero_lis_2 = [0 for _ in range(8)]
        zero_lis_3 = [0 for _ in range(8)]
        zero_lis_4 = [0 for _ in range(8)]
        zero_lis_5 = [0 for _ in range(8)]
        zero_lis_6 = [0 for _ in range(8)]
        zero_lis_7 = [0 for _ in range(8)]
        zero_lis_8 = [0 for _ in range(8)]

        check_lis = []
        dot_lis_1 = ["." for _ in range(8)]
        dot_lis_2 = ["." for _ in range(8)]
        dot_lis_3 = ["." for _ in range(8)]
        dot_lis_4 = ["." for _ in range(8)]
        dot_lis_5 = ["." for _ in range(8)]
        dot_lis_6 = ["." for _ in range(8)]
        dot_lis_7 = ["." for _ in range(8)]
        dot_lis_8 = ["." for _ in range(8)]


        check_lis.append(zero_lis_1)
        check_lis.append(zero_lis_2)
        check_lis.append(zero_lis_3)
        check_lis.append(zero_lis_4)
        check_lis.append(zero_lis_5)
        check_lis.append(zero_lis_6)
        check_lis.append(zero_lis_7)
        check_lis.append(zero_lis_8)

        ans_lis = []
        ans_lis.append(dot_lis_1)
        ans_lis.append(dot_lis_2)
        ans_lis.append(dot_lis_3)
        ans_lis.append(dot_lis_4)
        ans_lis.append(dot_lis_5)
        ans_lis.append(dot_lis_6)
        ans_lis.append(dot_lis_7)
        ans_lis.append(dot_lis_8)


        retsu = -1
        #print(check_lis)
        for c in test:
            retsu += 1
            check_lis[c][retsu] = 1
        #print(check_lis)

        retsu = -1
        for c in test:
            retsu += 1
            cnt_retsu = retsu
            cnt_c = c

            while 7>= cnt_retsu > 0 and 7>= cnt_c > 0: #左上へ
                if check_lis[cnt_c - 1][cnt_retsu - 1] == 1:
                    tmp += 1
                cnt_c -= 1
                cnt_retsu -= 1
            cnt_retsu = retsu
            cnt_c = c
            while 0<= cnt_retsu < 7 and 7>= cnt_c > 0: #右上へ
                if check_lis[cnt_c - 1][cnt_retsu + 1] == 1:
                    tmp +=1
                cnt_c -= 1
                cnt_retsu += 1
            cnt_retsu = retsu
            cnt_c = c
            while 7 >= cnt_retsu > 0 and 0<= cnt_c < 7: #左下へ
                #print(cnt_c, cnt_retsu)
                if check_lis[cnt_c + 1][cnt_retsu - 1] == 1:
                    tmp += 1
                cnt_c += 1
                cnt_retsu -= 1
            cnt_retsu = retsu
            cnt_c = c
            while 0<= cnt_retsu < 7 and 0<= cnt_c < 7: #右下へ
                if check_lis[cnt_c + 1][cnt_retsu + 1] == 1:
                    tmp += 1
                cnt_c += 1
                cnt_retsu += 1
        #print(check_lis)
        if tmp > 1:
            pass
        else:
            for i in range(8):
                ans_lis[i][test[i]] = "Q"
                for ans in ans_lis[i]:
                    if ans == "Q":
                        pass
                    else:
                        ans = "."
            for ans in ans_lis:
                print(''.join(map(str, ans)))
            exit()




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu May  7 22:24:11 2020

@author: Kanaru Sato
"""

import itertools
import copy

def setdanger(Map,r,c):
    Map[r][c] == 0
    for i in range(8):#縦横
        Map[r][i] = 0
        Map[i][c] = 0
    for i in range(max(r-7,-c),min(r,7-c)+1):#右上がり斜め
        Map[r-i][c+i] = 0
    for i in range(max(-c,-r),min(7-c,7-r)+1):#左上がり斜め
        Map[r+i][c+i] = 0

def dfs(i,Map,ans):#i個をmapに配置するやり方を深さ優先探索し、存在したら座標を追加、Trueを返す
    if i == 0:
        return True
    else:
        for pointtuple in itertools.product([i for i in range(8)], repeat=2):
            point = list(pointtuple)
            if Map[point[0]][point[1]]:
                currentMap = copy.deepcopy(Map)
                setdanger(currentMap,point[0],point[1])
                if dfs(i-1,currentMap,ans):
                    ans.append(point)
                    return True
                    break
    
k = int(input())

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

Map = [[1 for i in range(8)] for j in range(8)]
for i in range(k):
    setdanger(Map,ans[i][0],ans[i][1])

dfs(8-k,Map,ans)

for i in range(8):
    row = []
    for j in range(8):
        if [i,j] in ans:
            row.append("Q")
        else:
            row.append(".")
    print("".join(row))

Submission status: Accepted

Solution code:
k = int(input())
Qs = [tuple(map(int, input().split())) for _ in range(k)]
from itertools import permutations
Lis = [(i, j) for i in range(8) for j in range(8)]

def dfs(idx, lis):
    if idx==8:
        return lis
    Xs = set([x for x, y in lis])
    Ys = set([y for x, y in lis])
    Dif = set([x-y for x, y in lis])
    xDif = set([(8-x)-y for x, y in lis])
    ans = False
    for i in range(8):
        if i in Xs: continue
        for j in range(8):
            if j in Ys: continue
            if i-j in Dif: continue
            if (8-i)-j in xDif: continue
            lis.append((i, j))
            ans = dfs(idx+1, lis)
            if ans:
                return ans
            lis.pop()
    else:
        return False

chess = [['.']*8 for _ in range(8)]
for x, y in dfs(k, Qs):
    chess[x][y] = 'Q'
for i in range(8):
    print(''.join(chess[i]))