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:
NOT_FREE = 1
FREE = 0
 
q = [0 for i in range(8)]
row = [0 for i in range(8)]
col = [0 for i in range(8)]
dneg = [0 for i in range (16)]
dpos = [0 for i in range (16)]
 
 
def printBord():
    for r in range(8):
        for c in range(8):
            if q[r] == c:
                print("Q",end="")
            else: print(".",end="")
        print()
 
 
def putQueen(i):
    if i == 8:
        printBord()
        return
     
    if row[i]:
        if putQueen(i+1):return
 
    for j in range(8):
        if (row[i] or col[j] or dpos[i+j] or dneg[i-j+7]) == NOT_FREE :continue
        q[i] = j
        col[j] = dpos[i+j] = dneg[i-j+7] = NOT_FREE
        if putQueen(i+1) : return
        col[j] = dpos[i+j] = dneg[i-j+7] = FREE
    return
 
 
if __name__=='__main__':
    k = int(input())
    for i in range(k):
        r, c = (int(x) for x in input().split())
        q[r] = c
        row[r] = col[c] = dpos[r+c] = dneg[r-c+7] = NOT_FREE
    putQueen(0)

Submission status: Accepted

Solution code:
k = int(input())
row = [1] * 8
col = [1] * 8
dpos = [1] * 15
dneg = [1] * 15
X = [['.' 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] = 0
    X[r][c] = 'Q'
 
def s(i):
    while i < 8 and not row[i]:i += 1        
    if i == 8:
        for i in range(8):
            print(''.join(X[i]))
    for j in range(8):
        if not col[j] or not dpos[i+j] or not dneg[i-j+7]: continue
        row[i] = col[j] = dpos[i+j] = dneg[i-j+7] = 0
        X[i][j] = 'Q'
        s(i+1)
        row[i] = col[j] = dpos[i+j] = dneg[i-j+7] = 1
        X[i][j] = '.'
s(0)

Submission status: Accepted

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

N = 8

row = [-1 for i in range(N)]
col = [False for i in range(N)]
board = [[False for i in range(N)] for j in range(N)]
pos = [False for i in range(2*N-1)]
neg = [False for i in range(2*N-1)]

num = int(input())

for i in range(num):
  x, y = list(map(int, input().split()))
  board[x][y] = True
  
def priboard():
  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):
      char = 'Q' if row[i] == j else '.'
      print(char, end="")
    print()
      
def back_track(k):
  if k == N:
    priboard()
    return 0
  for i in range(N):
    if (not col[i]) and (not pos[k+i]) and (not neg[k-i+N-1]):
      row[k] = i
      col[i] = True
      pos[k+i] = True
      neg[k-i+N-1] = True
      
      back_track(k+1)
      row[k] = -1
      col[i] = False
      pos[k+i] = False
      neg[k-i+N-1] = False

back_track(0)

Submission status: Accepted

Solution code:
answer_printed = 0
answer=[]
for i in range(8):
    answer.append([])
for i in range(8):
    for j in range(8):
        answer[i].append('.')
row=[]
for i in range(8):
    row.append('.')
col=[]
for i in range(8):
    col.append('.')
right_slope=[]
for i in range(15):
    right_slope.append('.')
left_slope=[]
for i in range(15):
    left_slope.append('.')

def slope_change_r(x,y):
    return (x+y)%15

def slope_change_l(x,y):
    return (x-y+15)%15

def eightqueen(x,y,c):
    global answer_printed
    if c == 8:
        if answer_printed == 0:
            print_answer()
            answer_printed = 1
        return
    if x >= 8:
        return
    if row[x] == 'Q':
        if x<7:
            eightqueen(x+1,0,c)
        else:
            return
    for y in range(8):
        if is_all_clear(x,y):
            mark(x,y)
            eightqueen(x+1,0,c+1)
            unmark(x,y)

def mark(x,y):
    answer[x][y] = 'Q'
    row[x] = 'Q'
    col[y] = 'Q'
    right_slope[slope_change_r(x,y)] = 'Q'
    left_slope[slope_change_l(x,y)] = 'Q'

def unmark(x,y):
    answer[x][y] = '.'
    row[x] = '.'
    col[y] = '.'
    right_slope[slope_change_r(x,y)] = '.'
    left_slope[slope_change_l(x,y)] = '.'

def is_all_clear(x,y):
    if answer[x][y] == 'Q':
        return False
    if row[x] == 'Q':
        return False
    if col[y] == 'Q':
        return False
    if right_slope[slope_change_r(x,y)] == 'Q':
        return False
    if left_slope[slope_change_l(x,y)] == 'Q':
        return False
    return True

def print_answer():
    for i in range(8):
        for j in range(8):
            if answer[i][j] == 'Q':
                print('Q',end='')
            else:
                print('.',end='')
        print('',end='\n')
    
k = int(input())
while True:
    try:
        r,c = map(int,input().split())
    except:
            break
    else:
        mark(r,c)

eightqueen(0,0,k)

Submission status: Accepted

Solution code:
NOT_FREE = 1
FREE = 0

q = [0 for i in range(8)]
row = [0 for i in range(8)]
col = [0 for i in range(8)]
dneg = [0 for i in range (16)]
dpos = [0 for i in range (16)]


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


def putQueen(i):
    if i == 8:
        printBord()
        return
    
    if row[i]:
        if putQueen(i+1):return 

    for j in range(8):
        if (row[i] or col[j] or dpos[i+j] or dneg[i-j+7]) == NOT_FREE :continue
        q[i] = j
        col[j] = dpos[i+j] = dneg[i-j+7] = NOT_FREE
        if putQueen(i+1) : return
        col[j] = dpos[i+j] = dneg[i-j+7] = FREE
    return


if __name__=='__main__':
    k = int(input())
    for i in range(k):
        r, c = (int(x) for x in input().split())
        q[r] = c
        row[r] = col[c] = dpos[r+c] = dneg[r-c+7] = NOT_FREE
    putQueen(0)

Submission status: Accepted

Solution code:
import sys

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


def print_board():
    for i in range(N):
        for j in range(N):
            if row[i] == j:
                print("Q", end='')
            else:
                print(".", end='')
        print("\n", end='')


def put_queen(i):
    if i == N:
        return True
    elif row[i] != -1:
        if put_queen(i+1):
            return True
        else:
            return False
    else:
        for j in range(N):
            if col[j] == 1 or dpos[i+j] == 1 or dneg[i-j+N-1] == 1:
                continue
            row[i] = j
            col[j] = dpos[i+j] = dneg[i-j+N-1] = 1
            if put_queen(i+1):
                return True
            else:
                row[i] = -1
                col[j] = dpos[i+j] = dneg[i-j+N-1] = 0
        return False


line = sys.stdin.readline()
n = int(line)
for i in range(n):
    line = sys.stdin.readline()
    r, c = map(int, line.split())
    row[r] = c
    col[c] = dpos[r+c] = dneg[r-c+N-1] = 1

put_queen(0)
print_board()

Submission status: Accepted

Solution code:
import sys
import time
input = sys.stdin.readline
FREE = True
NOT_FREE = False

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

row = [FREE]*8
col = [FREE]*8
dpos = [FREE]*15
dneg = [FREE]*15
chess_board = [['.' for i in range(8)] for j in range(8)]

def printBoard():
    for c in chess_board:
        print("".join(c))

def chess_init():
    for q in Q:
        i = q[0]
        j = q[1]
        chess_board[i][j] = 'Q'
        row[i] = col[j] = dpos[i+j] = dneg[i-j+7] = NOT_FREE

def putQueen(i):

    if(i == 8):
        printBoard()
        return
    
    row_idx = 0
    for j in range(8):
        if(row[j] == FREE):
            row_idx = j
            break

    for j in range(8):
        if(col[j] == NOT_FREE or dpos[row_idx+j] == NOT_FREE or dneg[row_idx-j+7] == NOT_FREE):
            continue
        # not free jya nai nara oku
        chess_board[row_idx][j] = 'Q'
        row[row_idx] = col[j] = dpos[row_idx+j] = dneg[row_idx-j+7] = NOT_FREE
        putQueen(i+1)
        # i+1 banme tansaku site kokoni kaette kitara
        # tansaku sippai = backtracking suru kara FREE ni modosu
        chess_board[row_idx][j] = '.'
        row[row_idx] = col[j] = dpos[row_idx+j] = dneg[row_idx-j+7] = FREE

if __name__ == "__main__":
    chess_init()
    # sudeni okareta koma igai no koma no tansaku suru
    putQueen(num)

Submission status: Accepted

Solution code:
N = int(input())
a = []
b = []
c = []
for i in range(N):
    a += [list(map(int, input().split()))]
    
row = [1]*9
col = [1]*9
dops = [1]*16
dneg = [1]*16

def sett(x, y):
    row[y] = 0
    col[x] = 0
    dops[x+y] = 0
    dneg[y-x+7] = 0

def dsett(x, y):
    row[y] = 1
    col[x] = 1
    dops[x+y] = 1
    dneg[y-x+7] = 1
    
def paint(ans):
    pain = [["."]*8for _ in range(8)]
    for i, j in ans.items():
        pain[i][j] = "Q"
        print("".join(pain[i]))
    
cnt = 1
def serch(h):
    global cnt
    if h == 8:
        aa = 0
        for i, j in a:
            if ans[i] == j:
                aa += 1
        if aa == len(a):
            cnt = 0
            paint(ans)
            return
    for i in range(8):
        if row[h] and col[i] and dops[h+i] and dneg[h-i+7] and cnt:
            sett(i, h)
            ans[h] = i
            
            serch(h+1)
            
            dsett(i, h)
            del ans[h]

ans = {}          
serch(0)

Submission status: Accepted

Solution code:
import random

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


def solve():
    global qs
    if len(qs) == 8:
        return True

    # モンテカルロ的に探索
    ry, rx = random.randint(0, 7), random.randint(0, 7)
    for y in range(8):
        y = (y+ry) % 8
        for x in range(8):
            x = (x+rx) % 8
            f = False
            for qy, qx in qs:
                dy, dx = abs(y-qy), abs(x-qx)
                if qy == y or qx == x or dy == dx:
                    f = True
                    break
            if not f:
                qs.append([y, x])
                if solve():
                    return
                qs.pop(-1)
    return False


solve()

for y in range(8):
    v = ""
    for x in range(8):
        if [y, x] in qs:
            v += "Q"
        else:
            v += "."
    print(v)

Submission status: Accepted

Solution code:

def put_queen(field,r,c):
    return field | 1<<(r*8+c)

def check_queen(field,r,c):
    return field & 1<<(r*8+c)

def view_field(field):
    for i in range(8):
        for j in range(8):
            print('Q' if check_queen(field,i,j) else '.', end='')
        print()

def placeable(field,r,c):
    for i in range(8):
        if check_queen(field,r,i) or check_queen(field,i,c):
            return False
    if r>c:
        r1,c1 = r-c,0
    else:
        r1,c1 = 0,c-r

    if r>7-c:
        r2,c2 = r-(7-c),7
    else:
        r2,c2 = 0,c+r

    for i in range(8):
        if 0<=r1+i<8 and 0<=c1+i<8 and check_queen(field,r1+i,c1+i)     \
            or                                                          \
            0<=r2+i<8 and 0<=c2-i<8 and check_queen(field,r2+i,c2-i):
            return False

    return True


def make_field(field, queen_num):
    if queen_num==8:
        return field
    for i in range(8):
        for j in range(8):
            if placeable(field,i,j):
                solve_field = make_field(put_queen(field,i,j),queen_num+1)
                if not solve_field==2**64:
                    return solve_field
    return 2**64
    
k=int(input())
field=0
for i in range(k):
    r,c=map(int,input().split())
    field = put_queen(field,r,c)

view_field(make_field(field,k))

Submission status: Accepted

Solution code:
def sakuzyo(i):
    if koteirow[i] == 1:
        sakuzyo(i-1)
    else:
        for j in range(N):
            if haiti[i][j] == 'Q':
                #print('delete {} {}'.format(i, j))
                haiti[i][j] = '.'
                row[i] = 0
                col[j] = 0
                dpos[i + j] = 0
                dneg[i - j + (N - 1)] = 0
                if j == N-1:
                    sakuzyo(i-1)
                else:
                    sounyuu(i, j+1)


def sounyuu(i, j):
    if koteirow[i] == 0:
        for k in range(j, N):
            flag = 0
            if col[k] == 0 and dpos[i+k] == 0 and dneg[i-k+(N-1)] == 0:
                haiti[i][k] = 'Q'
                #print('add {} {}'.format(i, k))
                row[i] = 1
                col[k] = 1
                dpos[i+k] = 1
                dneg[i-k+(N-1)] = 1
                flag = 1
                if i == N-1:
                    for o in range(N):
                        for p in range(N):
                            print(haiti[o][p], end='')
                        print()
                    exit()
                else:
                    sounyuu(i+1, 0)
        if flag == 0:
            sakuzyo(i-1)
    elif i == N-1:
        for o in range(N):
            for p in range(N):
                print(haiti[o][p], end='')
            print()
        exit()
    else:
        sounyuu(i+1, j)


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

N = 8
row = [0]*N
col = [0]*N
dpos = [0]*(N*2-1)
dneg = [0]*(N*2-1)
haiti = [['.']*N for _ in range(N)]
koteirow = [0]*N

for i in data:
    haiti[i[0]][i[1]] = 'Q'
    row[i[0]] = 1
    col[i[1]] = 1
    dpos[i[0]+i[1]] = 1
    dneg[i[0] - i[1] + (N - 1)] = 1
    koteirow[i[0]] = 1

sounyuu(0, 0)

Submission status: Accepted

Solution code:
N = 8
tate = [True]*N
yoko = [True]*N
rnaname = [True]*(2*N-1)
lnaname = [True]*(2*N-1)
board = [[True]*N for i in range(N)]


def update(x, y, value):
    tate[x] = value
    yoko[y] = value
    rnaname[x+y] = value
    lnaname[x-y+N-1] = value
    board[x][y] = value


def check(x, y):
    if tate[x] and yoko[y] and rnaname[x+y] and lnaname[x-y+N-1]:
        return True
    return False


def show():
    for i in range(N):
        for j in range(N):
            print('.' if board[i][j] else 'Q', sep='', end='')
        print()


# iは縦ベース
def solve(i):
    if i == N:
        show()
        exit(0)
    if tate[i] is False:
        solve(i+1)
    for j in range(N):
        if check(i, j):
            update(i, j, False)
            solve(i+1)
            update(i, j, True)


n = int(input())
for i in range(n):
    Q = list(map(int, input().split()))
    update(Q[0], Q[1], False)

for i in range(N):
    if tate[i]:
        solve(i)
        break
solve(N)

Submission status: Accepted

Solution code:
row = [False] * 8
col = [False] * 8
dpos = [False] * 15
dneg = [False] * 15


board = [['.', '.', '.', '.', '.', '.', '.', '.'] for i in range(8)]

import sys

file_input = sys.stdin

k = int(file_input.readline())

for line in file_input:
    r, c = map(int, line.split())
    row[r] = True
    col[c] = True
    dpos[r + c] = True
    dneg[r - c + 7] = True
    board[r][c] = 'Q'

def dfs(i = 0):
    if i == 8:
        for line in board:
            print(''.join(line))
    elif row[i]:
        dfs(i + 1)
    else:
        for j in range(8):
            if col[j] or dpos[i + j] or dneg[i - j + 7]:
                continue
            row[i] = True
            col[j] = True
            dpos[i + j] = True
            dneg[i - j + 7] = True
            board[i][j] = 'Q'
            dfs(i + 1)
            row[i] = False
            col[j] = False
            dpos[i + j] = False
            dneg[i - j + 7] = False
            board[i][j] = '.'

dfs()

Submission status: Accepted

Solution code:
import sys

blank = [i for i in range(64)]
nump = int(sys.stdin.readline())
qpos = []
for _ in range(nump):
    j, i = map(int, sys.stdin.readline().split())
    qpos.append([j*8+i, j-i, j+i])
    for x in range(8):
        if j*8+x in blank: blank.remove(j*8+x)
        if x*8+i in blank: blank.remove(x*8+i)
        if 8*(j-i+x)+x in blank: blank.remove(8*(j-i+x)+x)
        if 8*(j+i-x)+x in blank: blank.remove(8*(j+i-x)+x)

idx = [0] * (8-nump)
used = [False] * len(blank)

def combination(n, k, m=0):
  if m==k:
    board = ['.'] * 64
    for qp, _, _ in qpos:  board[qp] = 'Q'
    for i in range(8):  print(''.join(board[i*8:i*8+8]))
  else:
    for i in range(n):
      if m>0 and idx[m-1]<i:  continue
      if used[i]: continue
      idx[m] = i
      q = blank[i]

      x,y = q%8, q//8
      for p, b, c in qpos:
          if x==p%8 or y==p//8: break
          if y==x+b or y==-x+c: break
      else:
          used[i]=True
          qpos.append([q, y-x, y+x])
          combination(n, k, m+1)
          qpos.pop()
          used[i]=False


combination(len(blank), 8-nump)

Submission status: Accepted

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


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


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


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


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


def put_queen_in_row(y):
    #print("put_queen_row",y, queens)
    if y == 8:
        return True     # 既にQを7行に置いているので正解に到達
    if y in skip_row:
        return put_queen_in_row(y + 1)   # 前提条件にある列は無視して次の行に行く

    for x in search_blank_in_row(y):
        put_queen(x, y)
        if not put_queen_in_row(y + 1):
            elim_queen(x, y)    # クイーンを置けなかったのでx,yを取り除く
        else:
            return True
    return False    # すべての候補が失敗


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

    # 8 queen main
    put_queen_in_row(0)

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


main()

Submission status: Accepted

Solution code:
from itertools import permutations

N = 8

M = [['.']*N for i in range(N)]
A0 = set()
B0 = set()

K = int(input())
R = set(range(N))
C = set(range(N))
for i in range(K):
    r, c = map(int, input().split())
    R.remove(r); C.remove(c)
    M[r][c] = 'Q'
    A0.add(r+c)
    B0.add(r-c)


for CS in permutations(C):
    A = A0.copy()
    B = B0.copy()
    ok = 1
    for r, c in zip(R, CS):
        if r+c in A:
            ok = 0
        A.add(r+c)
        if r-c in B:
            ok = 0
        B.add(r-c)
    if ok:
        for r, c in zip(R, CS):
            M[r][c] = 'Q'
        break
print(*("".join(m) for m in M), sep='\n')

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop

BIG_NUM = 2000000000
HUGE_NUM = 9999999999999999
MOD = 1000000007
EPS = 0.000000001


global H,W
global num_diff
global diff_row,diff_col

def rangeCheck(row,col):
    if row >= 0 and row <= H-1 and col >= 0 and col <= W-1:
        return True
    else:
        return False

#table[row][col]にあるQueenの経路を塗る
def paint(table,row,col):

    table[row][col] = 'Q'

    for i in range(num_diff):

        tmp_row = row+diff_row[i]
        tmp_col = col+diff_col[i]

        while rangeCheck(tmp_row,tmp_col) == True:

            table[tmp_row][tmp_col] = 'x'

            tmp_row += diff_row[i]
            tmp_col += diff_col[i]


#table[row][col]にQueenを置けるか調べる
def is_ok(table,row,col):

    #未定義マスでなければfalse
    if table[row][col] != '.':
        return  False

    #他のQueenと衝突するか調べる
    for i in range(num_diff):

        tmp_row = row+diff_row[i];
        tmp_col = col+diff_col[i];

        while rangeCheck(tmp_row,tmp_col) == True:

            if table[tmp_row][tmp_col] == 'Q':
                return False

            tmp_row += diff_row[i]
            tmp_col += diff_col[i]

    return True


def recursive(base_row,base_col,table,put_num):

    if put_num == 8:

        for row in range(H):
            for col in range(W):

                if table[row][col] == 'Q':

                    print("Q",end = "")
                else:
                    print(".",end = "")
            print()
        return

    #置かないで次へ
    if base_col == 7:
        if base_row == 7:
            return

        recursive(base_row+1,0,table,put_num)

    else:
        recursive(base_row,base_col+1,table,put_num)


    #置けないなら打ち切り
    if is_ok(table,base_row,base_col) == False:
        return

    next_table = [[None]*8 for i in range(8)]

    for row in range(H):
        for col in range(W):
            next_table[row][col] = table[row][col]

    paint(next_table,base_row,base_col)

    if base_col == 7:
        if base_row == 7:
            return
        else:
            recursive(base_row+1,0,next_table,put_num+1)

    else:
        recursive(base_row,base_col+1,next_table,put_num+1)


debug = 0
H = 8
W = 8
num_diff = 8
diff_row = [-1,-1,-1,0,0,1,1,1]
diff_col = [-1,0,1,-1,1,-1,0,1]


N = int(input())
first_table = [['.']*8 for i in range(8)]

for loop in range(N):
    row,col = map(int,input().split())
    paint(first_table,row,col)

recursive(0,0,first_table,N)

Submission status: Accepted

Solution code:
board = [["." for i in range(8)] for i in range(8)]
N = int(input())
row = [1] * 8
col = [1] * 8
dpos = [1] * 15
dneg = [1] * 15


for i in range(N):
  x, y = map(int, input().split())
  row[x] = col[y] = dpos[x+y] =dneg[x-y+7] = 0
  board[x][y] = "Q"

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

solve(0)

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:
# -*- coding: utf-8 -*-
"""
Created on Mon Aug 13 18:17:29 2018
ALDS_1_13_A
@author: maezawa
"""
import copy
def searchq(board, k):
    global result
    if k == 0:
        result = copy.deepcopy(board)
        return True
    for x in range(1,9):
        for y in range(1,9):
            #if k == 6:
                #print(x,y,board[x][y])
            if board[x][y] == 0:
                cpb = copy.deepcopy(board)
                cpb[x][y] = 9
                mark(cpb, x,y)
                #print(x,y)
                if searchq(cpb, k-1):
                    return True
                #else:
                    #print('False at {},{}'.format(x,y))
    return False
      
def mark(board, x, y):
    direction = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1),
                 (1,0), (1,1)]
    for dx, dy in direction:
        x1 = x
        y1 = y
        while True:
            x1 += dx
            y1 += dy
            if board[x1][y1] == 0 or board[x1][y1] == 1:
                board[x1][y1] = 1
            else:
                break
            
n = int(input())
board = [[0]*10 for _ in range(10)]
board[0] = [-1]*10
board[9] = [-1]*10

result = copy.deepcopy(board)

for i in range(10):
    board[i][0] = -1
    board[i][9] = -1
for i in range(n):
    x, y = list(map(int, input().split()))
    board[x+1][y+1] = 9
    mark(board, x+1, y+1)

#print(*board[1:9], sep='\n')
if searchq(board, 8-n):
    pass
else:
    print('Error')
#print(*result[1:9], sep='\n')
for x in range(1,9):
    for y in range(1,9):
        if result[x][y] == 9:
            print('Q', end='')
        else:
            print('.', end='')
    print()

Submission status: Accepted

Solution code:
import sys
N = 8
board = [[0 for j in range(N)] for i in range(N)]
queen = [-1] * N

def main():
    init()
    search(0)

def search(i):
    if i == N:
        printBoard()
        sys.exit()
    
    if queen[i] != -1:
        search(i + 1)

    else :
        for j in range(N):
            if board[i][j] == 0:
                queen[i] = j
                changeBoard(i, j, 1)
                search(i + 1)
                changeBoard(i, j, -1)
                queen[i] = -1

def init():
    k = int(input())

    for i in range(k):
        a = list(map(int, input().split()))
        queen[a[0]] = a[1]
        changeBoard(a[0], a[1], 1)

def changeBoard(i, j, number):
    for k in range(N):
        board[i][k] += number
        board[k][j] += number

    if i > j :
        for k in range(N - (i - j)) :
            board[k + (i - j)][k] += number
    else:
        for k in range(N - (j - i)) :
            board[k][k + (j - i)] += number
    if i + j < N :
        for k in range(i + j + 1) :
            board[i + j - k][k] += number
    else:
        for k in range(i + j - N + 1, N):
            board[i + j - k][k] += number

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# Heuristic Search - 8 Queens Problem
def reload_board(B,r,c,diff):
    # ?????¨???????????????????????????????????????????????????????????????????????????????????°????????????
    global Q,NUM
    for i in range(NUM):
        # ????¨???????????????¶???
        B[r][i] += diff
        B[i][c] += diff
        # ????§?45??????????????????????????¶???
        if i < r and c + (r-i) < NUM:
                B[i][c+(r-i)] += diff
        elif r <= i and c - (i-r) >= 0:
                B[i][c-(i-r)] += diff
        # ????§?135??????????????????????????¶???
        if i < r and c - (r-i) >= 0:
                B[i][c-(r-i)] += diff
        elif r <= i and c + (i-r) < NUM:
                B[i][c+(i-r)] += diff

def solve(queens, B, r):
    global NUM,SETROW
    if r >= NUM:
        return True
    if r in SETROW:
        return solve(queens,B,r+1)
    else:
        for c in range(NUM):
            if B[r][c] == 0:
                ifed = True
                queens[r] = c
                reload_board(B,r,c,1)
                if not solve(queens,B,r+1):
                    reload_board(B,r,c,-1)
                else:
                    return True
    return False

def print_board(queens):
    for i in range(NUM):
        for j in range(NUM):
            print('Q' if queens[i] == j else '.', end='')
        print()

NUM = 8
k = int(input())
B = [[0 for _ in range(NUM)] for _ in range(NUM)]
SETROW = []
queens = [-1 for _ in range(NUM)]
for _ in range(k):
    r,c = map(int, input().split())
    reload_board(B,r,c,1)
    SETROW.append(r)
    queens[r] = c

solve(queens,B,0)
print_board(queens)

Submission status: Runtime Error

Solution code:

class Chess_board:
    def __init__(self):
        self.board=[[0]*8 for i in range(8)]
        self.queen_array=[]
        self.queen_row=[]


def copy_board(chess_board):
    new_board=Chess_board()
    new_board.board=[chess_board.board[i][:] for i in range(8)]
    new_board.queen_array=chess_board.queen_array[:]
    new_board.queen_row=chess_board.queen_row[:]
    return new_board


def mk_board(chess_board,queen_array):
    for queen in queen_array:
        row=queen[0]
        col=queen[1]
        if(chess_board.board[row][col]==0):
            chess_board.queen_array.append(queen)
            chess_board.queen_row.append(row)
            for i in range(8):
                chess_board.board[row][i]=1
            for i in range(8):
                chess_board.board[i][col]=1
            for i in range(1,8):
                if(row - i >=0 and col - i >=0):
                    chess_board.board[row-i][col-i]=1
                else:
                    break
            for i in range(1,8):
                if(8 > row + i >=0 and col - i >=0):
                    chess_board.board[row+i][col-i]=1
                else:
                    break
            for i in range(1,8):
                if(row - i >=0 and 8 > col + i >=0):
                    chess_board.board[row-i][col+i]=1
                else:
                    break
            for i in range(1,8):
                if(8 > row + i >=0 and 8 > col + i >=0):
                    chess_board.board[row+i][col+i]=1
                else:
                    break

        else:
            return 0
    
    return 1



def find_queen(chess_board):
    
    for tmp_row in range(8):
        if(tmp_row in chess_board.queen_row):
            pass
        else:
            break
    
    for col in range(8):
        new_board=copy_board(chess_board)
        if(mk_board(new_board,[[tmp_row,col]])==1):
            if(len(new_board.queen_row)==8):
                return new_board
            else:
                result=find_queen(new_board)
                if(result is not None):
                    return result
    
    return None



n=int(input())

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

board=Chess_board()
mk_board(board,queen_array)
result_board=find_queen(board)

for i in range(8):
    for queen in result_board.queen_array:
        if(queen[0]==i):
            str1="."*queen[1]
            str2="."*(7-queen[1])
            print(f"{str1}Q{str2}")