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:

from collections import namedtuple

position = namedtuple("position","row column")
def input_queens():
    queens = []
    n = int(input())
    for _ in range(n):
        row,column = [int(x) for x in input().split()]
        queens.append(position(row,column))
    return queens

def output_board(queens):
    for r in range(8):
        for c in range(8):
            print("Q" if position(r,c) in queens else ".",end = "")
        print()

def atackable(p,queens):
    return(
        p.row in [q.row for q in queens]
        or p.column in [q.column for q in queens]
        or any([abs(p.row - q.row) == abs(p.column-q.column) for q in queens])
    )


def next_p(p):
    if p.column == 7:
        return position(p.row+1,0)
    else:
        return position(p.row,p.column+1)
def over(p):
    return p.row > 7
    
def all_queens(queens):
    def rec(p,queens):
        if len(queens) == 8:
            return queens
        elif over(p):
            return False
        elif atackable(p,queens):
            return rec(next_p(p),queens)
        else:
            result = rec(position(p.row+1,0),queens+[p])
            return result if result else rec(next_p(p),queens)
    return rec(position(0,0),queens)
    

queens = input_queens()
output_board(all_queens(queens))

Submission status: Accepted

Solution code:
import copy


def is_vaild(board, i, j):
    if "Q" in board[i]:
        return False

    for k in range(8):
        if board[k][j] == "Q":
            return False

    # fill cross(left-up)
    m, n = i - 1, j - 1
    while m >= 0 and n > 0:
        if board[m][n] == "Q":
            return False
        m -= 1
        n -= 1

    # fill cross(left-down)
    m, n = i + 1, j - 1
    while m < 8 and n >= 0:
        if board[m][n] == "Q":
            return False
        m += 1
        n -= 1

    # fill cross(right-down)
    m, n = i + 1, j + 1
    while m < 8 and n < 8:
        if board[m][n] == "Q":
            return False
        m += 1
        n += 1

    # fill cross(right-up)
    m, n = i - 1, j + 1
    while m >= 0 and n < 8:
        if board[m][n] == "Q":
            return False
        m -= 1
        n += 1

    return True


def fill_board(board, i, j):
    if not is_vaild(board, i, j):
        return

    # fill row
    for k in range(8):
        board[i][k] = "."

    # fill column
    for k in range(8):
        board[k][j] = "."

    # fill cross(left-up)
    m, n = i - 1, j - 1
    while m >= 0 and n >= 0:
        board[m][n] = "."
        m -= 1
        n -= 1

    # fill cross(left-down)
    m, n = i + 1, j - 1
    while m < 8 and n >= 0:
        board[m][n] = "."
        m += 1
        n -= 1

    # fill cross(right-down)
    m, n = i + 1, j + 1
    while m < 8 and n < 8:
        board[m][n] = "."
        m += 1
        n += 1

    # fill cross(right-up)
    m, n = i - 1, j + 1
    while m >= 0 and n < 8:
        board[m][n] = "."
        m -= 1
        n += 1

    board[i][j] = "Q"
    return


def helper(board, rem):
    if rem == 0:
        for line in board:
            print("".join(line))
        quit()

    for i in range(8):
        for j in range(8):
            if board[i][j] == "#" and is_vaild(board, i, j):
                _prev = copy.deepcopy(board)
                fill_board(board, i, j)
                helper(board, rem - 1)
                board = _prev  # BackTracking
    return


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

K = int(input())
flag = False
for _ in range(K):
    i, j = [int(i) for i in input().split()]
    if board[i][j] == "#" and is_vaild(board, i, j):
        fill_board(board, i, j)


helper(board, 8 - K)

Submission status: Accepted

Solution code:
import itertools
import copy

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

bord = [['.']*8 for _ in range(8)]

exclude_num = []
x_list = [i for i in range(8)]
y_list = [i for i in range(8)]

def queen_move(some_list):
    for x,y in some_list:
        
        for i in range(8):
            bord[x][i] = '.'
            bord[i][y] = '.'
        
        cnt = 1    
        while True:
            if x-cnt >= 0 and y-cnt >= 0:
                bord[x-cnt][y-cnt] = '.'
            else:
                break
            cnt += 1
            
        cnt = 1    
        while True:
            if x-cnt >= 0 and y+cnt <= 7:
                bord[x-cnt][y+cnt] = '.'
            else:
                break
            cnt += 1
    
        cnt = 1    
        while True:
            if x+cnt <= 7 and y+cnt <= 7:
                bord[x+cnt][y+cnt] = '.'
            else:
                break
            cnt += 1
    
        cnt = 1    
        while True:
            if x+cnt <= 7 and y-cnt >= 0:
                bord[x+cnt][y-cnt] = '.'
            else:
                break
            cnt += 1

def check_queen(k):
    check = 0
    for i in range(8):
        for j in range(8):
            if bord[i][j] == 'Q':
                check += 1
    if check == k:
        return True
    else:
        return False

queen_move(li)
        
for x,y in li:
    bord[x][y] = 'Q'
    x_list.remove(x)
    y_list.remove(y)
    
bord_original = copy.deepcopy(bord)

for numbers in itertools.permutations(y_list, 8-k):
    cnt = 0
    bord = copy.deepcopy(bord_original)
    for number in numbers:
        tmp_li = [[x_list[cnt], number]]
        queen_move(tmp_li)
        bord[tmp_li[0][0]][tmp_li[0][1]] = 'Q'
        cnt += 1
        if check_queen(k+cnt) == False:
            break
    else:
        for ans in bord:
            print(''.join(ans))
        break

Submission status: Accepted

Solution code:
from itertools import permutations

n = int(input())
q = [list(map(int, input().split())) for _ in range(n)]
for p in permutations(range(8), 8):
    if all(p[i] == j for i, j in q):
        m = [["."] * 8 for _ in range(8)]
        for i, j in enumerate(p):
            m[i][j] = "Q"
        b = True
        for i, j in enumerate(p):
            for k in range(1, 8):
                if 0 <= i + k < 8 and 0 <= j + k < 8:
                    if m[i + k][j + k] == "Q":
                        break
                if 0 <= i - k < 8 and 0 <= j + k < 8:
                    if m[i - k][j + k] == "Q":
                        break
                if 0 <= i + k < 8 and 0 <= j - k < 8:
                    if m[i + k][j - k] == "Q":
                        break
                if 0 <= i - k < 8 and 0 <= j - k < 8:
                    if m[i - k][j - k] == "Q":
                        break
            else:
                continue
            b = False
            break
        if b:
            for a in m:
                print(*a, sep="")
            exit()

Submission status: Accepted

Solution code:
from itertools import permutations

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

for x in permutations(range(8)):
    flag = False
    for i in rc:
        if x[i[1]] != i[0]:
            flag = True
            break
    if flag:
        continue
    # 斜めの処理
    for i in range(7):
        flag = False
        for j in range(i+1, 8):
            if abs(x[i] - x[j]) == abs(i-j):
                flag = True
                break
        if flag:
            break
    if flag:
        continue
    for i in range(8):
        for j in range(8):
            if i == x[j]:
                print('Q', end='')
            else:
                print('.', end='')
        print()
    break

Submission status: Accepted

Solution code:
def can_put(arr, point):
    for p in arr:
        if p[0] == point[0] or p[1] == point[1] or p[0]-p[1] == point[0]-point[1] or p[0]+p[1] == point[0]+point[1]:
            return False
    return True

K = int(input())
RC = [tuple(map(int,input().split())) for _ in range(K)]
def dfs(arr):
    if len(arr) == 8:
        se = set()
        for a in arr:
            se.add(a)
        for i in range(8):
            for j in range(8):
                if (i,j) in se:
                    print("Q", end="")
                else:
                    print(".", end="")
                if j == 7: print()
        exit()
    for i in range(8):
        for j in range(8):
            if can_put(arr, (i,j)):
                dfs(arr+[(i,j)])
dfs(RC)

Submission status: Accepted

Solution code:
import sys
from itertools import permutations


def in_board(r, c):
    return 0 <= r < 8 and 0 <= c < 8


def reachable_generator(r, c):
    # 斜め(左上-右下)
    i = 1
    while True:
        if not in_board(r - i, c - i):
            break
        yield r - i, c - i
        i += 1
    i = 1
    while True:
        if not in_board(r + i, c + i):
            break
        yield r + i, c + i
        i += 1
    # 斜め(右上-左下)
    i = 1
    while True:
        if not in_board(r - i, c + i):
            break
        yield r - i, c + i
        i += 1
    i = 1
    while True:
        if not in_board(r + i, c - i):
            break
        yield r + i, c - i
        i += 1


def solve(ini):
    for p in permutations(range(8)):
        s = set()
        for i, j in enumerate(p):
            s.add((i, j))
        if not ini <= s:
            continue
        for i, j in s:
            for k, l in reachable_generator(i, j):
                if (k, l) in s:
                    break
            else:
                continue
            break
        else:
            return s


def main():
    input = sys.stdin.buffer.readline
    k = int(input())
    # ini:初期条件
    ini = set()
    for _ in range(k):
        r, c = map(int, input().split())
        ini.add((r, c))
    s = solve(ini)

    board = [["."] * 8 for _ in range(8)]
    for i, j in s:
        board[i][j] = "Q"
    for i in range(8):
        print("".join(board[i]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N=int(input())
L=[[0 for i in range(8)]for j in range(8)]

Q=[]

for i in range(N):
    h,w=map(int,input().split())
    Q.append((h,w))
    #L[h][w]="Q"
if N==8:
    L=[["." for i in range(8)]for j in range(8)]
    for q in Q:
        #print(q)
        L[q[0]][q[1]]="Q"
    for h in range(8):
        print("".join(L[h]))
    exit()
    
for i in range(len(Q)):
    H,W=Q[i]
    for j in range(1,8):
        if H+j>=8 or W+j>=8:
            break
        L[H+j][W+j]=1
    for j in range(1,8):
        if H+j>=8 or W-j<0:
            break
        L[H+j][W-j]=1
    for j in range(1,8):
        if W+j>=8 or H-j<0:
            break
        L[H-j][W+j]=1
    for j in range(1,8):
        if H-j<0 or W-j<0:
            break
        L[H-j][W-j]=1
    for j in range(1,8):
        if W+j>=8:
            break
        L[H][W+j]=1
    for j in range(1,8):
        if W-j<0:
            break
        L[H][W-j]=1
    for j in range(1,8):
        if H+j>=8:
            break
        L[H+j][W]=1
    for j in range(1,8):
        if H-j<0:
            break
        L[H-j][W]=1
for i in Q:
    L[i[0]][i[1]]="Q"
#print(L)
#for i in range(8):
    #print(L[i])
d=[]
for i in range(8):
    for j in range(8):
        if L[i][j]==0:
            d.append((i,j))

D=[{}for i in range(8)]
D[0][tuple(Q)]=d
#print(D)
import copy
for i in range(1,8-N):
    for k,v in D[i-1].items():
        K=list(k)
        for x in range(len(v)):
            l=[]
            for y in range(x+1,len(v)):
                if x==y:
                    continue
                if abs(v[x][0]-v[y][0])==abs(v[x][1]-v[y][1]) or (v[x][0]-v[y][0])*(v[x][1]-v[y][1])==0:
                    continue
                else:
                    l.append(v[y])
            #print(v[x][0],v[x][1])
            D[i][tuple(K+[v[x]])]=l
#print(D[8-N-1])
for k,v in D[8-N-1].items():
    if len(v)==1:
        
        for i in k:
            L[i[0]][i[1]]="Q"
        L[v[0][0]][v[0][1]]="Q"
        for h in range(8):
            for w in range(8):
                if L[h][w]!="Q":
                    L[h][w]="."
        for h in range(8):
            print("".join(L[h]))
        exit()

Submission status: Accepted

Solution code:
import copy

dirs = [[-1, -1], [-1, 0], [-1, 1],
        [0, -1], [0, 1],
        [1, -1], [1, 0], [1, 1]]

def place(board, r, c):
    if board[r][c] != '.':
        return False
    board[r][c] = 'Q'
    for d in dirs:
        rr = r + d[0]
        cc = c + d[1]
        while rr >= 0 and rr < 8 and cc >= 0 and cc < 8:
            board[rr][cc] = 'x'
            rr += d[0]
            cc += d[1]
    return True

def solve(board_):
    board = copy.deepcopy(board_)
    for r in range(8):
        for c in range(8):
            if place(board, r, c):
                tmp = solve(board)
                if tmp:
                    return tmp
                else:
                    board = copy.deepcopy(board_)
    if sum([row.count('Q') for row in board]) == 8:
        return board

def disp(board, clean=False):
    for row in board:
        if clean:
            row = ['.' if i == 'x' else i for i in row]
        print(''.join(row))

board = [['.'] * 8 for i in range(8)]
N = int(input())
for _ in range(N):
    r, c = map(int, input().split())
    place(board, r, c)

board = solve(board)

disp(board, True)

Submission status: Accepted

Solution code:
import copy
import itertools

k=int(input())
pos = [['.' for _ in range(8)] for _ in range(8)]
rows = [i for i in range(8)]
cols = [i for i in range(8)]

for _ in range(k):
    r,c = map(int, input().split())
    pos[r][c] = 'Q'
    rows.remove(r)
    cols.remove(c)

for c in itertools.permutations(cols):
# for c in [(6,0,7,5,1,4)]:
    temp_pos = copy.deepcopy(pos)
    
    for r_i, c_i in zip(rows, c):
        temp_pos[r_i][c_i] = 'Q'
        
    flg = True
    
    for r_i in range(8):
        for c_i in range(8):
            
            if temp_pos[r_i][c_i]=='Q':
                
                next_r,next_c = r_i,c_i
                while 0<=next_r+1<=7 and 0<=next_c+1<=7:
                    next_r+=1
                    next_c+=1
                    if temp_pos[next_r][next_c]=='Q':
                        flg = False
                        break
                    
                next_r,next_c = r_i,c_i
                while 0<=next_r-1<=7 and 0<=next_c+1<=7:
                    next_r-=1
                    next_c+=1
                    if temp_pos[next_r][next_c]=='Q':
                        flg = False
                        break
                
                next_r,next_c = r_i,c_i
                while 0<=next_r-1<=7 and 0<=next_c-1<=7:
                    next_r-=1
                    next_c-=1
                    if temp_pos[next_r][next_c]=='Q':
                        flg = False
                        break
                
                next_r,next_c = r_i,c_i
                while 0<=next_r+1<=7 and 0<=next_c-1<=7:
                    next_r+=1
                    next_c-=1
                    if temp_pos[next_r][next_c]=='Q':
                        flg = False
                        break
                        
            if not flg:
                break
        if not flg:
            break
    if flg:
        break

if flg:
    for rows in temp_pos:
        print(*rows, sep='')

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())
row, col = list(range(8)), list(range(8)) #まだ置ける
queen = []
for _ in range(n):
    r, c = map(int, input().split())
    queen.append((r, c))
    row.remove(r) #もう置けない所を削除
    col.remove(c)
for l in permutations(col):
    queen_tmp = queen[:]
    for r, c in zip(row, l):
        queen_tmp.append((r, c))
    if check(queen_tmp):
        board = [''.join('Q' if (r, c) in queen_tmp else '.' for c in range(8)) for r in range(8)]
        print(*board, sep='\n')
        break

Submission status: Accepted

Solution code:
from itertools import permutations

n=int(input())
lst_ini=[list(map(int,input().split())) for _ in range(n)]
row=list(range(8))
col=list(range(8))
for x in lst_ini:
    row.remove(x[0])
    col.remove(x[1])

for x in permutations(col):
    work=lst_ini[:]
    for i in range(8-n):
        work.append([row[i],x[i]])
    
    #対角方向チェック
    for y in work:
        for i in range(8):
            if y[0]==i: continue
            if [i,y[1]-(y[0]-i)] in work : break
            if [i,y[1]+(y[0]-i)] in work : break
        else : continue
        break
    else : break

for i in range(8):
    out=""
    for j in range(8):
        if [i,j] in work : out+="Q"
        else : out+="."
    print(out)

Submission status: Accepted

Solution code:
K = int(input())
rc = [list(map(int, input().split())) for i in range(K)]

from itertools import permutations as per

ans = None
for pers in per(range(8)):
    flag = False
    # 指定された配置にできない場合はスキップ
    for r, c in rc:
        if pers[r] != c:
            break
    else:
        flag = True
    # 斜めで競合する場合はスキップ
    for i in range(8):
        for j in range(1, 8):
            if i >= j:
                if pers[i] == pers[i-j]-j or pers[i] == pers[i-j]+j:
                    flag = False
                    break
    if flag:
        ans = pers
        break

for i in range(8):
    for j in range(8):
        if ans[i] == j:
            print('Q', sep='', end='')
        else:
            print('.', sep='', end='')
    print('')

Submission status: Accepted

Solution code:
import sys
from itertools import permutations

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    k = int(input())
    RC = [list(map(int, input().split())) for _ in range(k)]

    res = [["."] * 8 for _ in range(8)]
    for pattern in permutations(list(range(8))):
        XY = set(tuple((idx, num) for idx, num in enumerate(pattern)))
        flg = True
        for r, c in RC:
            if (r, c) not in XY:
                flg = False
                break
        if not flg:
            continue

        for x, y in XY:
            for i in range(1, 8):
                if (x + i, y + i) in XY or (x + i, y - i) in XY or (x - i, y + i) in XY or (x - i, y - i) in XY:
                    flg = False
                    break
            else:
                continue
            break
        if flg:
            for x, y in XY:
                res[x][y] = "Q"
            break

    for i in res:
        print("".join(i))


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import pprint

inp = int(input())
N = 8
board = [ [0]*8 for _ in range(8) ]
defined = []
dic = {}
for _ in range(inp):
  x,y = map(int,input().split())
  board[x][y] = 1
  defined.append(x)
  dic[x] = y

def check(board, row, col):
  for i in range(8):
    if i==col: continue
    if board[row][i] == 1:
      return False

  for i in range(8):
    if i==row: continue
    if board[i][col] == 1:
      return False

  # left upper
  for i,j in zip(range(row, -1, -1), range(col, -1, -1)):
    if i==row and j==col: continue
    if board[i][j] == 1:
      return False

  # left lower
  for i,j in zip(range(row, N), range(col, -1, -1)):
    if i==row and j==col: continue
    if board[i][j] == 1:
      return False

  # right upper
  for i,j in zip(range(row, -1, -1), range(col, N)):
    if i==row and j==col: continue
    if board[i][j] == 1:
      return False

  # right lower
  for i,j in zip(range(row, N), range(col, N)):
    if i==row and j==col: continue
    if board[i][j] == 1:
      return False

  return True

def solve(board, row):
  if row >= 8:
    return True

  if row in defined:
    col = dic[row]
    if check(board, row, col):
      if solve(board, row+1):
        return True
  else:
    for col in range(8):
      if check(board, row, col):
        board[row][col] = 1
        if solve(board, row+1):
          return True
        board[row][col] = 0

  return False

solve(board, 0)

for row in board:
  print("".join(["Q" if r==1 else "." for r in row ]))

Submission status: Accepted

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

for i in permutations(range(8)):
    if len(set([j+k for j,k in enumerate(i)]))!=8:continue
    if len(set([j-k for j,k in enumerate(i)]))!=8:continue
    flag=1
    for x,y in A:
        if i[x]!=y:flag=0
    if flag:
        for num in i:
            point=["."]*8
            point[num]="Q"
            print("".join(point))

Submission status: Accepted

Solution code:
import itertools
l = itertools.permutations(range(8))
n = int(input())
r = [0] * n
c = [0] * n
for i in range(n):
    r[i], c[i] = map(int, input().split())
for a in l:
    m = [[0]* 8 for i in range(8)]
    for i in range(8):
        m[i][a[i]] = 1
    ok = 1
    for i in range(n):
        if m[r[i]][c[i]] != 1:
            ok = 0
    for j in range(8):
        if sum([m[i+j][i] for i in range(8-j)])>=2:
            ok = 0
        if sum([m[i][i+j] for i in range(8-j)])>=2:
            ok = 0
        if sum([m[i][j-i] for i in range(j+1)])>=2:
            ok = 0
        if sum([m[7-j+i][7-i] for i in range(j+1)])>=2:
            ok = 0
    if ok:
        for i in range(8):
            print(''.join(['Q' if m[i][j]==1 else '.' for j in range(8)]))

Submission status: Accepted

Solution code:
from itertools import permutations
n=int(input())
q=[list(map(int,input().split())) for _ in range(n)]
l=list(range(8))
Q=list(permutations(l,8))
def OK(s):
    a=list(s)
    b=list(s)
    for i in range(len(s)):
        a[i]-=i
        b[i]+=i
    for i,j in enumerate(a[:-1]):
        if j in a[i+1:]:
            return False
    for i,j in enumerate(b[:-1]):
        if j in b[i+1:]:
            return False
    return True
for i in Q:
    chk=i
    for x,y in q:
        if i[x]!=y:
            chk=[]
            break
    if chk:
        if OK(i):
            A=i
            break
ans=[['.']*8 for _ in range(8)]
for i,j in enumerate(A):
    ans[i][j]='Q'
    print(''.join(map(str,ans[i])))

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


k = int(input())
pos = []
for i in range(k):
    x, y = map(int, input().split())
    pos.append((x, y))

N = 8
p = [i for i in range(N)]

def check(qs):
    board = [[0] * 8 for _ in range(8)]
    for q in qs:
        x, y = q
        board[x][y] = 1
    dirs = [(1, 1), (-1, -1), (1, -1), (-1, 1)]
    for q in qs:
        for d in dirs:
            dx, dy = q
            dx += d[0]
            dy += d[1]
            while (dx >= 0 and dy >= 0) and (dx < 8 and dy < 8):
                if board[dx][dy] == 1:
                    return False
                dx += d[0]
                dy += d[1]
    for i in range(8):
        for j in range(8):
            if board[i][j]:
                print("Q", end="")
            else:
                print(".", end="")
        print()
    return True

def perm(start):
    if start == N:
        qs = set((i, p[i]) for i in range(N))
        for x in pos:
            if not x in qs:
                break
        else:
            check(qs)
        return
    
    for i in range(start, N):
        p[i], p[start] = p[start], p[i]
        perm(start + 1)
        p[i], p[start] = p[start], p[i]

perm(0)

Submission status: Accepted

Solution code:
k=int(input())
l=[]


for _ in range(k):
  l.append(list(map(int, input().split())))
import itertools
for s in itertools.permutations(range(8)):
  t=[]
  for _ in range(8):
    t.append(([s[_], _]))
  for z in l:
    if not (z in t):
      break
  else:
    #print(t)
    for a in range(7):
      for b in range(a+1, 8): # 2つの点を探してのループ
        if abs(t[a][0]-t[b][0])==abs(t[a][1]-t[b][1]):
          break
      else:
        continue
      break
    else:
      tt=sorted(t)
      #print(sorted(t))
      for _ in range(8):
        if tt[_][1]==0:
          print("Q.......")
        else:
          print("."*tt[_][1]+"Q"+"."*(7-tt[_][1]))
    continue

Submission status: Accepted

Solution code:
from itertools import permutations

n = int(input())
li = [list(map(int,input().split())) for _ in range(n)]
chess = [["." for i in range(8)]for j in range(8)]

for i in range(8):
    chess[i][i] = "Q"

point = 0

# 行のchessの並べ方を探索
for patern in permutations(chess):
    for y,x in li:
        if patern[y][x] != "Q":
            break
    else:
        # 斜めにもQが一つしかないかを判定
        ld = [0]*15 # i+jの合計を記録（左下斜め方向）
        rd = [0]*15 # 7-i+jの合計を記録（右下斜め方向）
        for i in range(8):
            for j in range(8):
                if patern[i][j] == "Q":
                    ld[i+j] += 1
                    rd[i+(7-j)] += 1
        for k in range(15):
            # 斜め方向には１つしかQがあってはならない
            if rd[k] > 1 or ld[k] > 1:
                break
        else:
            for l in patern:
                print("".join(l))

Submission status: Accepted

Solution code:
import copy as cp
N = 8
ans = []

def out(M):
    for i in range(N):
        for j in range(N):
            print(M[i][j], end="")
        print("")
    
def DFS(r,c,dp,dn,qn):
    global ans
    if qn == N:
        for h in range(N):
            for w in range(N):
                if r[h] & c[w] & dp[h+w] & dn[w-h+7]:
                    ans.append([h,w])
                    return True
        return False

    for h in range(N):
        for w in range(N):
            if r[h] & c[w] & dp[h+w] & dn[w-h+7]:
                new_r = cp.deepcopy(r)
                new_c = cp.deepcopy(c)
                new_dp = cp.deepcopy(dp)
                new_dn = cp.deepcopy(dn)
                new_r[h],new_c[w],new_dp[h+w],new_dn[w-h+7] = False,False,False,False
                if DFS(new_r,new_c,new_dp,new_dn,qn+1):
                    ans.append([h,w])
                    return True
    return False


def main():
    row = [True]*N
    col = [True]*N
    dp = [True]*(2*N-1)
    dn = [True]*(2*N-1)
    k = int(input())
    MAP = [["." for _ in range(N)] for __ in range(N)]
    for _ in range(k):
        h,w = map(int,input().split())
        MAP[h][w] = "Q"
        row[h] = False
        col[w] = False
        dp[w+h] = False
        dn[w-h+7] = False
    
    DFS(row,col,dp,dn,k+1)

    
    for h,w in ans:
        MAP[h][w] = "Q"

    out(MAP)

main()

Submission status: Accepted

Solution code:
import itertools
K = int(input())
RC = [list(map(int,input().split())) for _ in range(K)]
P = list(itertools.permutations([0,1,2,3,4,5,6,7]))
PP = []
for p in P:
    for rc in RC:
        if p[rc[0]] != rc[1]:
            break
    else:
        PP.append(p)
for pp in PP:
    for i in range(8):
        for j in range(1,8):
            if i+j <= 7 and (pp[i]+j == pp[i+j] or pp[i]-j == pp[i+j]):
                break
            if i-j >= 0 and (pp[i]+j == pp[i-j] or pp[i]-j == pp[i-j]):
                break
        else:
            continue
        break
    else:
        ppp = pp
        break
for p in ppp:
    print('.......'[:p] + 'Q' + '.......'[p:])

Submission status: Accepted

Solution code:
# 17
# ALDS_13_A-8 クイーン問題

import itertools
import copy

k = int(input())
q_l = [[int(x) for x in input().split()] for y in range(k)]

x_l = list(range(8))
y_l = list(range(8))
plus_l = []
minus_l = []
for i in range(k):
    x_l.remove(q_l[i][1])
    y_l.remove(q_l[i][0])
    plus_l.append(q_l[i][0] + q_l[i][1])
    minus_l.append(q_l[i][0] - q_l[i][1])
    
per = itertools.permutations(x_l)
per2 = itertools.permutations(x_l)

for order in per:
    _p_l = copy.deepcopy(plus_l)
    _m_l = copy.deepcopy(minus_l)
    _x_l = list(order)
    for i,_y in enumerate(y_l):
        _p_l.append(_y + _x_l[i])
        _m_l.append(_y - _x_l[i])
    if len(set(_p_l)) == 8 and len(set(_m_l)) == 8:
        ans_l = [["."]*8 for j in range(8)]
        for j in range(k):
            ans_l[q_l[j][0]][q_l[j][1]] = "Q"
        for j in range(8-k):
            ans_l[y_l[j]][_x_l[j]] = "Q"
        for j in range(8):
            print(*(ans_l[j]), sep="")

Submission status: Accepted

Solution code:
from itertools import permutations

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

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

# 列
column = [i for i in range(8)]
# 行
row = [i for i in range(8)]

for r, perm_column in rc:
    column.remove(perm_column)
    row.remove(r)

    field[r][perm_column] = "Q"

dir_r = [1, 1, -1, -1]
dir_c = [1, -1, -1, 1]


def queen_check(field, perm_column):
    for i, j in zip(row, perm_column):
        for dr, dc in zip(dir_r, dir_c):
            r, c = i, j
            while True:
                r += dr
                c += dc

                if r < 0 or r >= 8 or c < 0 or c >= 8:
                    break

                if field[r][c] == "Q":
                    return False

    return True


for perm_column in permutations(column):
    for i, j in zip(row, perm_column):
        field[i][j] = "Q"

    if queen_check(field, perm_column):
        for f in field:
            print("".join(f))
    for i, j in zip(row, perm_column):
        field[i][j] = "."

Submission status: Accepted

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

#すでにクイーンがある位置
#[-1, -1, 2, -1, -1, 3, -1, -1]なら(2, 2)と(5, 3)にあることを示す
xy = [-1] * 8
for i in range(k):
  y, x = list(map(int, input().split()))
  xy[y] = x
#print(xy)

#どの列にあるか全て試す順列全探索
lis = [x for x in range(8)] # 0から7までのリスト 
permutations_lis = itertools.permutations(lis)# 全ての場合のリストを生成
# 以下出力
asn = [-1] * 8
for one_case in permutations_lis: 
  wrong = 0
  #print(one_case)
  for i in range(8):
    if (xy[i] != -1) and (xy[i] != one_case[i]):
      #すでにあるクイーンの位置に反してないか
      wrong = 1
      break
    for j in range(i + 1, 8):#下の行と被りがあるか
      #縦と斜め2方向で合計3方向
      if one_case[i] == one_case[j]:
        wrong = 1
      elif abs(one_case[i] - one_case[j]) == abs(i - j):
        wrong = 1
  if wrong == 0:
    ans = one_case
    
#print(ans)    
for i in range(8):
  for j in range(8):
    if ans[i] == j:
      print("Q", end = "")
    else:
      print(".", end = "")
  print("")