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: Wrong Answer

Solution code:
def check(a):
    flag = True
    for i in C:
        if (i[0] == a[0]) or (i[1] == a[1]) or (abs(i[0]-a[0]) == abs(i[1]-a[1])):
            flag = False
    return flag

def recq(r):
    if r == 8:
        pass
    elif DPr[r] == 1:
        recq(r+1)
    else:
        for c in range(8):
            if DPc[c]:
                continue
            else:
                if check((r,c)):
                    DPr[r] = 1
                    DPc[c] = 1
                    C.append([r,c])
                    recq(r+1)
                    if DPr[7] == 0:
                        C.pop()
                        DPr[r] = 0
                        DPc[c] = 0
k = int(input())
C = [[int(i) for i in input().split()] for _ in range(k)]
DPr = [0 for i in range(8)]
DPc = [0 for i in range(8)]
for i in C:
    DPr[i[0]]=1
    DPc[i[1]]=1
recq(0)
Q = [["." for i in range(8)] for i in range(8)]
for i in C:
    Q[i[0]][i[1]] = "Q"
for i in Q:
    tmp = ""
    for j in i:
        tmp+=j
    print(tmp)

Submission status: Wrong Answer

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)
if(n==8):
    result_board=find_queen(board)
else:
    result_board=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}")

Submission status: Wrong Answer

Solution code:
import copy

n = int(input())

dotsa = []
for _ in range(n):
    y,x = map(int,input().split(" "))
    dotsa.append([y,x])

pattern = []
pattern.append(dotsa)


for y in range(8):
    nextpattern = []
    #print("#######")
    #print(pattern)
    for pat in pattern:
        #print(";;;;;;;;;;;;;;;;;;;;;")
        #print(pat)
        flag = False
        for dot in pat:
            if dot[0] == y:
                flag = True
                break

        if flag:
            nextpattern = pattern
            continue

        ifFound = False
        for x in range(8):
            ank = len(pat)
            flag2 = True
            for i in range(ank):
                if abs(pat[i][0]-y) == abs(pat[i][1]-x) or pat[i][1] == x:
                    flag2 = False
                    break
            if flag2:
                #print("appended")
                #print(y)
                #print(x)
                tmp = copy.deepcopy(pat)
                tmp.append([y,x])
                nextpattern.append(tmp)
        #print("x loop end")
    pattern = nextpattern

ans = pattern[0]
board = [["."]*8 for i in range(8)]
#print(ans)
for ele in ans:
    board[ele[1]][ele[0]] = "Q"
for row in board:
    print(''.join(map(str,row)))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
2
2 2
5 3

output:
......Q.
Q.......
..Q.....
.......Q
.....Q..
...Q....
.Q......
....Q...
"""

import sys

N = 8
FREE, NOT_FREE = -1, 1


def generate_board(_q_list):
    for queen in _q_list:
        x, y = map(int, queen)
        init_q_check[x][y] = True

    return init_q_check


def print_board():
    # for i in range(N):
    #     for j in range(N):
    #         if q_check[i][j]:
    #             if row[i] != j:
    #                 return None
                
    for i in range(N):
        line = []
        for j in range(N):
            if row[i] == j:
                line.append('Q')
            else:
                line.append('.')
        print(*line, sep='')

    return None


def recursive(i):
    if i == N:
        print_board()
        return None

    for j in range(N):
        if ((col[j] is NOT_FREE) or
                (dpos[i + j] is NOT_FREE) or
                (dneg[i - j + N - 1] is NOT_FREE)):
            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

    return q_check


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    q_num = int(_input[0])
    q_list = map(lambda x: x.split(), _input[1:])

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

    init_q_check = [[False] * N for _ in range(N)]
    q_check = generate_board(q_list)

    ans = recursive(0)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy, copy
class QueenMAP():
    __slots__ = ["yoko", "tate", "naname1", "naname2", "MAP"]
    def __init__(self):
        self.yoko = set()
        self.tate = set()
        self.naname1 = set()
        self.naname2 = set()
        self.MAP = [["."] * 8 for _ in range(8)]
    def add(self, y, x):
        self.MAP[y][x] = "Q"
        self.yoko.add(y)
        self.tate.add(x)
        self.naname1.add(y - x)
        self.naname2.add(x + y)
    def check(self, y, x):
        if x in self.tate or (y - x) in self.naname1 or (x - y) in self.naname2:
            return False
        return True
    def allcheck(self):
        for i in range(8):
            if not "Q" in self.MAP[i]:
                return False
        return True
def MAIN():
    f = lambda M: "\n".join("".join(map(str, m)) for m in M)
    QM = QueenMAP()
    n = int(input())
    for _ in range(n):
        a, b = map(int, input().split())
        QM.add(a, b)
    dp = [(deepcopy(QM), n)]
    while dp:
        Q, cnt = dp.pop()
        if cnt == 8:
            if Q.allcheck():
                print(f(Q.MAP))
                break
            continue
        cnt += 1
        for i in range(8):
            if i in Q.yoko:
                continue
            for j in range(8):
                if Q.check(i, j):
                    CQ = deepcopy(Q)
                    CQ.add(i, j)
                    dp.append((CQ, cnt))
MAIN()

Submission status: Wrong Answer

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

import sys


BOARD_SIZE_W = 8
BOARD_SIZE_H = 8


def set_queen(board, queen_point):
    """
    クイーンを指定座標に配置した後、残りの配置可能な位置の配列を返す
    """
    return filter(create_queen_filter(queen_point), board)


def create_queen_filter(queen_point):
    """
    指定位置にクイーンを配置したことにより、対象座標へ配置不可能にならないかを確認する関数を返す
    """

    def queen_filter(new_point):
        return new_point[0] != queen_point[0] and \
            new_point[1] != queen_point[1] and \
            new_point[1] != new_point[0] + queen_point[1] - queen_point[0] and \
            new_point[1] != -new_point[0] + queen_point[1] + queen_point[0]
    return queen_filter


def get_board_string(queen_points):
    """
    クイーンの位置座標の配列を指定出力形式に変換する
    """
    queen_points_set = set(list(map(lambda point: "{}:{}".format(point[0], point[1]), queen_points)))
    board_string_lines = []
    for y in range(BOARD_SIZE_H):
        line = ""
        for x in range(BOARD_SIZE_W):
            if "{}:{}".format(x, y) in queen_points_set:
                line += "Q"
            else:
                line += "."
        board_string_lines.append(line)
    return "\n".join(board_string_lines)


def get_all_queen_points(board, queen_points):
    if len(queen_points) >= 8:
        return queen_points
    elif not board:
        return []
    for empty_point in board:
        new_queen_points = [empty_point]
        new_queen_points.extend(queen_points)
        new_queen_points = get_all_queen_points(list(set_queen(board, empty_point)), new_queen_points)
        if new_queen_points:
            return get_all_queen_points(list(set_queen(board, empty_point)), new_queen_points)


def main():
    inputStr = sys.stdin.read()
    lines = inputStr.split("\n")
    lines = list(filter(lambda line: line, lines))
    if len(lines) <= 1:
        lines = []
    else:
        lines = lines[1:]
    queen_points = list(map(lambda line: list(map(int, line.split(" "))), lines))
    board = [[i % BOARD_SIZE_W, i // BOARD_SIZE_H] for i in range(BOARD_SIZE_H * BOARD_SIZE_W)]
    for queen_point in queen_points:
        board = set_queen(board, queen_point)
    print(get_board_string(get_all_queen_points(board, queen_points)))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

import sys


BOARD_SIZE_W = 8
BOARD_SIZE_H = 8


def set_queen(board, queen_point):
    """
    クイーンを指定座標に配置した後、残りの配置可能な位置の配列を返す
    """
    return filter(create_queen_filter(queen_point), board)


def create_queen_filter(queen_point):
    """
    指定位置にクイーンを配置したことにより、対象座標へ配置不可能にならないかを確認する関数を返す
    """

    def queen_filter(new_point):
        return new_point[0] != queen_point[0] and \
            new_point[1] != queen_point[1] and \
            new_point[1] != new_point[0] + queen_point[1] - queen_point[0] and \
            new_point[1] != -new_point[0] + queen_point[1] + queen_point[0]
    return queen_filter


def get_board_string(queen_points):
    """
    クイーンの位置座標の配列を指定出力形式に変換する
    """
    queen_points_set = set(list(map(lambda point: "{}:{}".format(point[0], point[1]), queen_points)))
    board_string_lines = []
    for y in range(BOARD_SIZE_H):
        line = ""
        for x in range(BOARD_SIZE_W):
            if "{}:{}".format(x, y) in queen_points_set:
                line += "Q"
            else:
                line += "."
        board_string_lines.append(line)
    return "\n".join(board_string_lines)


def get_all_queen_points(board, queen_points):
    if len(queen_points) >= 8:
        return queen_points
    elif not board:
        return []
    for empty_point in board:
        new_queen_points = [empty_point]
        new_queen_points.extend(queen_points)
        new_queen_points = get_all_queen_points(list(set_queen(board, empty_point)), new_queen_points)
        if new_queen_points:
            return get_all_queen_points(list(set_queen(board, empty_point)), new_queen_points)


def main():
    inputStr = sys.stdin.read()
    lines = inputStr.split("\n")
    lines = list(filter(lambda line: line, lines))
    if len(lines) <= 1:
        lines = []
    else:
        lines = lines[1:]
    queen_points = list(map(lambda line: list(map(int, line.split(" "))), lines))
    board = [[i % BOARD_SIZE_W, i // BOARD_SIZE_H] for i in range(BOARD_SIZE_H * BOARD_SIZE_W)]
    for queen_point in queen_points:
        board = set_queen(board, queen_point)
    sys.stdout.write(get_board_string(get_all_queen_points(board, queen_points)))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys;

def putQueen(i, row, col, dpos, dneq,count):
    if(i == 8):
        global finding
        if(finding == 0):
            return
        finding = 0
        printBoard(row[0:])
    

    for j in range(8):
        if(count < len(r)):
            if(r[count] == j):
                putQueen(i+1,row[0:], col[0:], dpos[0:], dneq[0:],count+1)
                continue
        if(col[j] == 1 or dpos[i+j] == 1 or dneq[i-j+7] == 1):
            continue
        row[i] = j
        col[j] = dpos[i+j] = dneq[i-j+7] = 1
        putQueen(i+1,row[0:], col[0:], dpos[0:], dneq[0:],count)
        col[j] = dpos[i+j] = dneq[i-j+7] = 0

def printBoard(row):
    for k in range(8):
        if(row[k] == 0):
            print("Q.......")
        elif(row[k] == 1):
            print(".Q......")
        elif(row[k] == 2):
            print("..Q.....")
        elif(row[k] == 3):
            print("...Q....")
        elif(row[k] == 4):
            print("....Q...")
        elif(row[k] == 5):
            print(".....Q..")
        elif(row[k] == 6):
            print("......Q.")
        else:
            print(".......Q")

n = (int)(input());
row = [0 for i in range(8)]
col = [0 for i in range(8)]
dpos = [0 for i in range(15)]
dneq = [0 for i in range(15)]

r=[0]*n

for i in range(n):
    r[i],c = map(int, input().split());
    row[r[i]] = c
    col[c] = 1
    dpos[r[i]+c] = 1
    dneq[r[i]-c+7] = 1

finding = 1

putQueen(0,row, col, dpos, dneq,0)

Submission status: Wrong Answer

Solution code:
import sys;

def putQueen(i, row, col, dpos, dneq,count):
    if(i == 8):
        global finding
        if(finding == 0):
            return
        finding = 0
        printBoard(row[0:])

    for j in range(8):
        if(count < len(r)):
            if(r[count] == i):
                putQueen(i+1,row[0:], col[0:], dpos[0:], dneq[0:],count+1)
                continue
        if(col[j] == 1 or dpos[i+j] == 1 or dneq[i-j+7] == 1):
            continue
        row[i] = j
        col[j] = dpos[i+j] = dneq[i-j+7] = 1
        putQueen(i+1,row[0:], col[0:], dpos[0:], dneq[0:],count-1+1)
        col[j] = dpos[i+j] = dneq[i-j+7] = 0

def printBoard(row):
    for k in range(8):
        if(row[k] == 0):
            print("Q.......")
        elif(row[k] == 1):
            print(".Q......")
        elif(row[k] == 2):
            print("..Q.....")
        elif(row[k] == 3):
            print("...Q....")
        elif(row[k] == 4):
            print("....Q...")
        elif(row[k] == 5):
            print(".....Q..")
        elif(row[k] == 6):
            print("......Q.")
        else:
            print(".......Q")

n = (int)(input());
row = [0 for i in range(8)]
col = [0 for i in range(8)]
dpos = [0 for i in range(15)]
dneq = [0 for i in range(15)]

r=[0]*n

for i in range(n):
    r[i],c = map(int, input().split());
    row[r[i]] = c
    col[c] = 1
    dpos[r[i]+c] = 1
    dneq[r[i]-c+7] = 1

finding = 1

putQueen(0,row, col, dpos, dneq,0)

Submission status: Wrong Answer

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 solve(i):
    if i == 8:
        for i in range(8):
            print(''.join(X[i]))
        return
    if not row[i]:
        i += 1
    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'
        solve(i+1)
        row[i] = col[j] = dpos[i+j] = dneg[i-j+7] = 1
        X[i][j] = '.'
solve(0)

Submission status: Wrong Answer

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 solve(i):
    if i == 8:
        for i in range(8):
            print(''.join(X[i]))
        return
    if not row[i]: 
        i += 1
    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'
        solve(i+1)
        row[i] = col[j] = dpos[i+j] = dneg[i-j+7] = 1
        X[i][j] = '.'
solve(0)

Submission status: Wrong Answer

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 solve(i):
    if i == 8:
        for i in range(8):
            print(''.join(X[i]))
        return
    while i < 8 and not row[i]: 
        i += 1
    
    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'
        solve(i+1)
        row[i] = col[j] = dpos[i+j] = dneg[i-j+7] = 1
        X[i][j] = '.'
solve(0)

Submission status: Time Limit Exceeded

Solution code:
import sys;

def putQueen(i, row, col, dpos, dneq):
    if(i == 8):
        global finding
        if(finding == 0):
            return
        finding = 0
        printBoard(row[0:])
    

    for j in range(8):
        if i in myset:
            putQueen(i+1,row[0:], col[0:], dpos[0:], dneq[0:])
            continue
        if(col[j] == 1 or dpos[i+j] == 1 or dneq[i-j+7] == 1):
            continue
        row[i] = j
        col[j] = dpos[i+j] = dneq[i-j+7] = 1
        putQueen(i+1,row[0:], col[0:], dpos[0:], dneq[0:])
        col[j] = dpos[i+j] = dneq[i-j+7] = 0

def printBoard(row):
    for k in range(8):
        if(row[k] == 0):
            print("Q.......")
        elif(row[k] == 1):
            print(".Q......")
        elif(row[k] == 2):
            print("..Q.....")
        elif(row[k] == 3):
            print("...Q....")
        elif(row[k] == 4):
            print("....Q...")
        elif(row[k] == 5):
            print(".....Q..")
        elif(row[k] == 6):
            print("......Q.")
        else:
            print(".......Q")

n = (int)(input());
row = [0 for i in range(8)]
col = [0 for i in range(8)]
dpos = [0 for i in range(15)]
dneq = [0 for i in range(15)]

myset = set()

for i in range(n):
    r,c = map(int, input().split());
    myset.add(r)
    row[r] = c
    col[c] = 1
    dpos[r+c] = 1
    dneq[r-c+7] = 1

finding = 1

putQueen(0,row, col, dpos, dneq)

Submission status: Accepted

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

def initialize():
    row = [FREE] * N
    col = [FREE] * N
    dpos = [FREE] * (2 * N - 1)
    dneg = [FREE] * (2 * N - 1)
    return row, col, dpos, dneg


def printBoard(x, row):
    for i in range(N):
        for j in range(N):
            if x[i][j]:
                if row[i] != j:
                    return
    for i in range(N):
        line = ''
        for j in range(N):
            if row[i] == j:
                line += 'Q'
            else:
                line += '.'
        print(line)


def recursive(i, x, row, col, dpos, dneg):
    if i == N:
        printBoard(x, row)
        return

    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] = NOT_FREE
        dpos[i + j] = NOT_FREE
        dneg[i - j + N - 1] = NOT_FREE
        recursive(i+1, x, row, col, dpos, dneg)
        row[i] = FREE
        col[j] = FREE
        dpos[i + j] = FREE
        dneg[i - j + N - 1] = FREE


if __name__ == '__main__':
    row, col, dpos, dneg = initialize()
    x = [[False] * N for i in range(N)]
    k = int(input())
    for i in range(k):
        r, c = [int(v) for v in input().split()]
        x[r][c] = True

    recursive(0, x, row, col, dpos, dneg)

Submission status: Accepted

Solution code:
def check(a):
    flag = True
    for i in C:
        if (i[0] == a[0]) or (i[1] == a[1]) or (abs(i[0]-a[0]) == abs(i[1]-a[1])):
            flag = False
    return flag

def recq(r):
    if r == 8:
        pass
    elif DPr[r] == 1:
        recq(r+1)
    else:
        for c in range(8):
            if DPc[c]:
                continue
            else:
                if check((r,c)):
                    DPr[r] = 1
                    DPc[c] = 1
                    C.append([r,c])
                    recq(r+1)
                    flag = False
                    for i in range(8):
                        if DPr[i]==0:
                            flag = True
                    if flag:
                        C.pop()
                        DPr[r] = 0
                        DPc[c] = 0
k = int(input())
C = [[int(i) for i in input().split()] for _ in range(k)]
DPr = [0 for i in range(8)]
DPc = [0 for i in range(8)]
for i in C:
    DPr[i[0]]=1
    DPc[i[1]]=1
recq(0)
Q = [["." for i in range(8)] for i in range(8)]
for i in C:
    Q[i[0]][i[1]] = "Q"
for i in Q:
    tmp = ""
    for j in i:
        tmp+=j
    print(tmp)

Submission status: Accepted

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)
if(n!=8):
    result_board=find_queen(board)
else:
    result_board=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}")

Submission status: Accepted

Solution code:
import copy

n = int(input())

dotsa = []
for _ in range(n):
    y,x = map(int,input().split(" "))
    dotsa.append([y,x])

pattern = []
pattern.append(dotsa)


for y in range(8):
    nextpattern = []
    #print("#######")
    #print(pattern)
    for pat in pattern:
        #print(";;;;;;;;;;;;;;;;;;;;;")
        #print(pat)
        flag = False
        for dot in pat:
            if dot[0] == y:
                flag = True
                break

        if flag:
            nextpattern = pattern
            continue

        ifFound = False
        for x in range(8):
            ank = len(pat)
            flag2 = True
            for i in range(ank):
                if abs(pat[i][0]-y) == abs(pat[i][1]-x) or pat[i][1] == x:
                    flag2 = False
                    break
            if flag2:
                #print("appended")
                #print(y)
                #print(x)
                tmp = copy.deepcopy(pat)
                tmp.append([y,x])
                nextpattern.append(tmp)
        #print("x loop end")
    pattern = nextpattern

ans = pattern[0]
board = [["."]*8 for i in range(8)]
#print(ans)
for ele in ans:
    board[ele[0]][ele[1]] = "Q"
for row in board:
    print(''.join(map(str,row)))

Submission status: Accepted

Solution code:
from functools import lru_cache
cc = [["." for i in range(8)] for j in range(8)]

@lru_cache(maxsize=None)     
def dia(s,a,b):
    d = []
    for i in range(8):
        for j in range(8):
            try:
                if j + (a - i) == b: 
                    d.append(s[i][j])
                if j -  (a - i) == b:
                    d.append(s[i][j])
                if j + (i - a) == b: 
                    d.append(s[i][j])
                if j -  (i - a) == b:
                    d.append(s[i][j])
            except IndexError: continue
    print(d)
    return d


def check(cc,a,b):
    ss = list(zip(*cc))
    if 'Q' in cc[a]: return False
    if 'Q' in ss[b]: return False
    d = []
    for i in range(8):
        for j in range(8):
            try:
                if j + (a - i) == b: 
                    d.append(cc[i][j])
                if j -  (a - i) == b:
                    d.append(cc[i][j])
                if j + (i - a) == b: 
                    d.append(cc[i][j])
                if j -  (i - a) == b:
                    d.append(cc[i][j])
            except IndexError: continue
    if 'Q' in d: return False
    return True

def chess(s,queen):
    if queen == 8:
        return s
    for i in range(8):
        for j in range(8):
            if check(s,i,j):
                sol = s
                sol[i][j] = 'Q'
                if chess(sol,queen+1) != [[]]:
                    return sol
                else: sol[i][j] = "."
    return [[]]


k = int(input())
for i in range(k):
    a, b = input().split()
    cc[int(a)][int(b)] = 'Q'
ans = chess(cc,k)
print('\n'.join(list(map(lambda x: ''.join(x),ans))) )

Submission status: Accepted

Solution code:
from functools import lru_cache
cc = [["." for i in range(8)] for j in range(8)]

def check(cc,a,b):
    ss = list(zip(*cc))
    if 'Q' in cc[a]: return False
    if 'Q' in ss[b]: return False
    d = []
    for i in range(8):
        for j in range(8):
            try:
                if j + (a - i) == b: 
                    d.append(cc[i][j])
                if j -  (a - i) == b:
                    d.append(cc[i][j])
                if j + (i - a) == b: 
                    d.append(cc[i][j])
                if j -  (i - a) == b:
                    d.append(cc[i][j])
            except IndexError: continue
    if 'Q' in d: return False
    return True

def chess(s,queen):
    if queen == 8:
        return s
    for i in range(8):
        for j in range(8):
            if check(s,i,j):
                sol = s
                sol[i][j] = 'Q'
                if chess(sol,queen+1) != [[]]:
                    return sol
                else: sol[i][j] = "."
    return [[]]


k = int(input())
for i in range(k):
    a, b = input().split()
    cc[int(a)][int(b)] = 'Q'
ans = chess(cc,k)
print('\n'.join(list(map(lambda x: ''.join(x),ans))) )

Submission status: Accepted

Solution code:
from functools import lru_cache
cc = [["." for i in range(8)] for j in range(8)]
 
def check(cc,a,b):
    ss = list(zip(*cc))
    if 'Q' in cc[a]: return False
    if 'Q' in ss[b]: return False
    d = []
    for i in range(8):
        for j in range(8):
            try:
                if j + abs(a - i) == b: 
                    d.append(cc[i][j])
                if j -  abs(a - i) == b:
                    d.append(cc[i][j])
            except IndexError: continue
    if 'Q' in d: return False
    return True
 
def chess(s, queen):
    if queen == 8:
        return s
    for i in range(8):
        for j in range(8):
            if check(s, i, j):
                sol = s
                sol[i][j] = 'Q'
                if chess(sol, queen+1) != [[]]:
                    return sol
                else: sol[i][j] = "."
    return [[]]
 
 
k = int(input())
for i in range(k):
    a, b = map(lambda x: int(x), input().split())
    cc[a][b] = 'Q'
ans = chess(cc, k)
print('\n'.join(list(map(lambda x: ''.join(x), ans))) )

Submission status: Accepted

Solution code:
import sys, itertools
f = sys.stdin
        
n = int(f.readline())
q = []
rest_r = set(range(8))
rest_c = [i for i in range(8)]
for _ in range(n):
    r, c = map(int, f.readline().split())
    q.append([r, c, r + c, r - c])
    rest_r.remove(r)
    rest_c.remove(c)

def check(q, rc):
    for qi in q:
        if qi[2] == rc[2] or qi[3] == rc[3] :
            return False
    return True
    
def put_queen(q, rest_r, rest_c):
    if len(q) == 8:
        return q
    c = rest_c[len(rest_r) - 1]
    for r in rest_r:
        rc = [r, c, r + c, r - c]
        if check(q, rc):
            ret = put_queen(q + [rc], rest_r.difference([r]) , rest_c)
            if ret:
                return ret
    return False
q = put_queen(q, rest_r, rest_c)
    
board = [None for _ in range(8)]
for qi in q:
    board[qi[0]] = '.' * qi[1] + 'Q' + '.' * (8 - qi[1] - 1)
for line in board:
    print(line)