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: 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)
if(board.queen_row!=8):
    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}")

Submission status: Runtime Error

Solution code:
# coding=utf-8

class Tree():
    def __init__(self, init_field):
        self.root = init_field

    def search(self, field_id, field):
        global final_queen_pos
        #print("field_id:", field_id)
        #field.print_field()
        q_r = rest_row[field_id - n]
        if final_queen_pos:
            return None
        else:
            for q_c, cell in enumerate(field.state[q_r]):
                if cell == 0:
                    if final_queen_pos:
                        break
                    if field_id == 7:
                        field.queen_pos.append([q_r, q_c])
                        final_queen_pos = field.queen_pos
                        break
                    else:
                        next_field = Field(field_id + 1, field)
                        field.children.append(next_field)
                        next_field.update(q_r, q_c)
                        self.search(field_id + 1, next_field)
                else:
                    continue

class Field():
    def __init__(self, field_id, parent=None):
        self.id = field_id
        self.parent = parent
        self.children = []

        if field_id == 0:
            self.state = [[0 for _ in range(W)] for H in range(H)]
            self.queen_pos = []
        else:
            self.state = []
            self.queen_pos = []
            for row in self.parent.state:
                x = row.copy()
                self.state.append(x)
            for parent_queen_pos in self.parent.queen_pos:
                self.queen_pos.append(parent_queen_pos)

    def update(self, q_r, q_c):
        self.queen_pos.append([q_r, q_c])
        for i in range(8):
            self.state[q_r][i] = 1
            self.state[i][q_c] = 1
        summ = q_c + q_r
        diff = q_c - q_r
        for i in range(8):
            if (0 <= i + diff < 8):
                self.state[i][i + diff] = 1
            if (0 <= summ - i < 8):
                self.state[i][summ - i] = 1

    def print_field(self): #for debug
        print("queen_pos:", self.queen_pos)
        for row in self.state:
            print(*row)


H, W = 8, 8
n = int(input())
init_field = Field(0)
tree = Tree(init_field)
field_list = [init_field]
rest_row = [i for i in range(8)]
queen_pos = []
final_queen_pos = None
final_result = [["." for _ in range(8)] for _ in range(8)]

for _ in range(n):
    r, c = map(int, input().split())
    queen_pos.append([r, c])
    rest_row.remove(r)

i = 0
prev_field = init_field
for q_r, q_c in queen_pos:
    i += 1
    field = Field(i, prev_field)
    field.update(q_r, q_c)
    field_list.append(field)
    prev_field.children = [field]
    prev_field = field

tree.search(i, field)
for q_r, q_c in final_queen_pos:
    final_result[q_r][q_c] = "Q"

for row in final_result:
    print("".join(row), end = "\n")

Submission status: Runtime Error

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")
    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: Runtime Error

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[1] != queen_point[1] and \
            new_point[0] != queen_point[0] and \
            new_point[0] != new_point[1] + queen_point[0] - queen_point[1] and \
            new_point[0] != -new_point[1] + queen_point[0] + queen_point[1]
    return queen_filter


def get_board_string(queen_points):
    """
    クイーンの位置座標の配列を指定出力形式に変換する
    """
    queen_points_set = set(list(map(lambda point: "{}:{}".format(point[1], point[0]), 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: Runtime Error

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[1] != queen_point[1] and \
            new_point[0] != queen_point[0] and \
            new_point[0] != new_point[1] + queen_point[0] - queen_point[1] and \
            new_point[0] != -new_point[1] + queen_point[0] + queen_point[1]
    return queen_filter


def get_board_string(queen_points):
    """
    クイーンの位置座標の配列を指定出力形式に変換する
    """
    queen_points_set = set(list(map(lambda point: "{}:{}".format(point[1], point[0]), 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)) + "\n")


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# 8 Puzzle
import copy
z = 0
[N, d] = [3, 0]
check_flag = [[1, 2, 3, 4,  1, 2, 3, 4,  1, 2, 3, 4],
              [2, 3, 4, 1,  2, 3, 4, 1,  2, 3, 4, 1],
              [3, 4, 1, 2,  3, 4, 1, 2,  3, 4, 1, 2],
              [4, 1, 2, 3,  4, 1, 2, 3,  4, 1, 2, 3],
              [3, 2, 1, 4,  3, 2, 1, 4,  3, 2, 1, 4],
              [2, 1, 4, 3,  2, 1, 4, 3,  2, 1, 4, 3],
              [1, 4, 3, 2,  1, 4, 3, 2,  1, 4, 3, 2],
              [4, 3, 2, 1,  4, 3, 2, 1,  4, 3, 2, 1]]

start = []
goal = [[i + j*N for i in range(1, N + 1)] for j in range(N)]
goal[2][2] = 0
for i in range(N):
    start.append(list(map(int, input().split())))


def manhattan(value, pairs):
    h = 0

    if value == 1:
        h = (pairs[0] + pairs[1])
    if value == 2:
        h = (pairs[0] + abs(pairs[1] - 1))
    if value == 3:
        h = (pairs[0] + abs(pairs[1] - 2))
    
    if value == 4:
        h = (abs(pairs[0] - 1) + pairs[1])
    if value == 5:
        h = (abs(pairs[0] - 1) + abs(pairs[1] - 1)) 
    if value == 6:
        h = (abs(pairs[0] - 1) + abs(pairs[1] - 2))
        
    if value == 7:
        h = (abs(pairs[0] - 2) + pairs[1])      
    if value == 8:
        h = (abs(pairs[0] - 2) + abs(pairs[1] - 1))
        
    return h

def flag_array(flag, input):

    flag.pop(0)
    flag.append(input)
    return flag


s_h = 0
for i in range(N):
    for j in range(N):
        s_h += manhattan(start[i][j], [i, j])

# print(s_h)

for i in range(N):
        check = start[i].count(0)
        if check != 0:
            [s_r, s_c] = [i, start[i].index(0)]
            break
        if i == 3:
            print("Error")

while True:
    d += 1
    queue = []
    flag = [0 for i in range(12)]
    queue.append([s_h, start, 0, [s_r, s_c], flag])

    #while True:
    while len(queue) != 0:
        #print("Q: ", len(queue), "depth: ", d)
        short_n = queue.pop(0)
        h = short_n[0] - short_n[2]
        state = short_n[1]
        g = short_n[2]
        [r, c] = short_n[3]
        flag = short_n[4]
        #print("left_Q: ", len(queue), "depth: ", d, "h: ", h, "g: ", g, "state: ", state, "g+h: ", short_n[0], "flag: ", flag[len(flag) - 1])
        #print("left_Q: ", len(queue), "depth: ", d, "h: ", h, "g: ", g, "flag: ", flag, "g+h: ", short_n[0])
        #if d == 1:
            #print(short_n[0])
            #print(state)
            #print(g)

        if h == 0:
            print(short_n[2])
            #print(z)
            break
        """
        if flag in check_flag:
            z += 1
            continue
        """
        if r - 1 >= 0 and flag[len(flag) - 1] != 3:
            [temp, temp_array] = [copy.deepcopy(state), flag[:]]
            h = short_n[0] - short_n[2] - manhattan(temp[r - 1][c], [r - 1, c]) + manhattan(temp[r - 1][c], [r, c])
            [temp[r][c], temp[r - 1][c]] = [temp[r - 1][c], temp[r][c]]
            #if temp[r][c] != goal[r][c]:
            #[r, c] = [r - 1, c]
            #if temp
            #h = manhattan(temp)
            #print("1: ", h, temp)
            if g + 1 + h <= d:
                queue.append([h + g + 1, temp, g + 1, [r - 1, c], flag_array(temp_array, 1)])
        
        if c + 1 < N and flag[len(flag) - 1] != 4:
            #print("2: ")
            [temp, temp_array] = [copy.deepcopy(state), flag[:]]
            #temp_array = copy.deepcopy(flag)
            h = short_n[0] - short_n[2] - manhattan(temp[r][c + 1], [r, c + 1]) + manhattan(temp[r][c + 1], [r, c])
            [temp[r][c], temp[r][c + 1]] = [temp[r][c + 1], temp[r][c]]
            #queue.append(calculate(temp, g + 1))
            #print("2: ", h, temp)
            if g + 1 + h <= d:
                queue.append([h + g + 1, temp, g + 1, [r, c + 1], flag_array(temp_array, 2)])

        if r + 1 < N and flag[len(flag) - 1] != 1:
            #print("3: ")
            [temp, temp_array] = [copy.deepcopy(state), flag[:]]
            #temp_array = copy.deepcopy(flag)
            h = short_n[0] - short_n[2] - manhattan(temp[r + 1][c], [r + 1, c]) + manhattan(temp[r + 1][c], [r, c])
            [temp[r][c], temp[r + 1][c]] = [temp[r + 1][c], temp[r][c]]
            #queue.append(calculate(temp, g + 1))
            #print("3: ", h, temp)
            if g + 1 + h <= d:
                queue.append([h + g + 1, temp, g + 1, [r + 1, c], flag_array(temp_array, 3)])
        
        if c - 1 >= 0 and flag[len(flag) - 1] != 2:
            #print("4: ")
            [temp, temp_array] = [copy.deepcopy(state), flag[:]]
            h = short_n[0] - short_n[2] - manhattan(temp[r][c - 1], [r, c - 1]) + manhattan(temp[r][c - 1], [r, c])
            [temp[r][c], temp[r][c - 1]] = [temp[r][c - 1], temp[r][c]]
            if g + 1 + h <= d:
                queue.append([h + g + 1, temp, g + 1, [r, c - 1], flag_array(temp_array, 4)])
                
        queue.sort(key = lambda data:data[0])
        queue.sort(key = lambda data:data[2], reverse = True)

        data = []
        g_data = []
        #print(queue)
        """
        for i in range(len(queue)):
            data.append(str(queue[i][0]))
            g_data.append(str(queue[i][2]))
            #print(queue[i])
        print("g+h: ",' '.join(data))
        print("g: ",' '.join(g_data))
        """
        #if d == 1:
        #print(len(queue))

    if state == goal:
        break

Submission status: Runtime Error

Solution code:
from copy import deepcopy


class EightQueen:
    NQUEENS = 8
    SIZE = 8

    class Board:
        def __init__(self, size):
            self.queens = []
            self.size = size

        def place(self, i, j):
            self.queens.append((i, j))

        def count(self):
            return len(self.queens)

        def ok(self, i, j):
            for qi, qj in self.queens:
                if qi == i:
                    return False
                if qj == j:
                    return False
                if i - j == qi - qj:
                    return False
                if i + j == qi + qj:
                    return False
            return True

        def __str__(self):
            s = ''
            for i in range(self.size):
                for j in range(self.size):
                    if (i, j) in self.queens:
                        s += "Q"
                    else:
                        s += "."
                s += '\n'
            return s

    def __init__(self):
        self.board = self.Board(self.SIZE)

    def add_queen(self, i, j):
        self.board.place(i, j)

    def solve(self):
        def _solve(board, si, sj):
            if board.count() == self.NQUEENS:
                return board

            for i, j in _from_pos(si, sj):
                if board.ok(i, j):
                    b = deepcopy(board)
                    b.place(i, j)
                    result = _solve(b, i, j)
                    if result is not None:
                        return result
            else:
                return None

        def _from_pos(i, j):
            for n in range(i*self.SIZE + j, self.SIZE*self.SIZE):
                yield (n // self.SIZE, n % self.SIZE)

        self.board = _solve(self.board, 0, 0)

    def __str__(self):
        if self.board is None:
            return 'no solution'
        else:
            return str(self.board)


def run():
    input()
    q = EightQueen()

    for i, j in [int(i) for i in input().split()]:
        q.add_queen(i, j)

    q.solve()
    print(q)


if __name__ == '__main__':
    run()

Submission status: WA: Presentation Error

Solution code:
row = [True] * 8
col = [True] * 8
dpos = [True] * 15
dneg = [True] * 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] = "INIT"
    col[c] = "INIT"
    dpos[r + c] = False
    dneg[r + (7 - c)] = False
    board[r][c] = 'Q'

def dfs(i = 0):
    if i == 8:
        for line in board:
            print(*line)
        return
    if row[i] == "INIT":
        dfs(i + 1)
    elif row[i]:
        for j in range(8):
            if col[j] == "INIT":
                pass
            elif col[j] and dpos[i + j] and dneg[i + (7 - j)]:
                row[i] = False
                col[j] = False
                dpos[i + j] = False
                dneg[i + (7 - j)] = False
                board[i][j] = 'Q'
                dfs(i + 1)
                row[i] = True
                col[j] = True
                dpos[i + j] = True
                dneg[i + (7 - j)] = True
                board[i][j] = '.'

dfs()

Submission status: WA: Presentation Error

Solution code:
n = int(input())
nt = []

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

for i in range(n):
    y, x = map(int, input().split())
    board[y][x] = "Q"
    nt.append(y)

def output():
    for row in board:
        print(" ".join(row))

def check(x, y):
    for i in range(8):
        for j in range(8):
            if i == y and j == x:
                continue
            elif i == y and board[i][j] == "Q":
                return False
            elif j == x and board[i][j] == "Q":
                return False
            elif abs(i-y) == abs(j-x) and board[i][j] == "Q":
                return False
    return True

def dfs(row):
    if row == 8:
        output()
        return
    if row in nt:
        dfs(row+1)
        return

    for i in range(8):
        board[row][i] = "Q"
        if not check(i, row):
            board[row][i] = "."
            continue
        else:
            dfs(row+1)
            board[row][i] = "."


dfs(0)

Submission status: WA: Presentation Error

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[1] != queen_point[1] and \
            new_point[0] != queen_point[0] and \
            new_point[0] != new_point[1] + queen_point[0] - queen_point[1] and \
            new_point[0] != -new_point[1] + queen_point[0] + queen_point[1]
    return queen_filter


def get_board_string(queen_points):
    """
    クイーンの位置座標の配列を指定出力形式に変換する
    """
    queen_points_set = set(list(map(lambda point: "{}:{}".format(point[1], point[0]), 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: WA: Presentation Error

Solution code:
from copy import deepcopy


class EightQueen:
    NQUEENS = 8
    SIZE = 8

    class Board:
        def __init__(self, size):
            self.queens = []
            self.size = size

        def place(self, i, j):
            self.queens.append((i, j))

        def count(self):
            return len(self.queens)

        def ok(self, i, j):
            for qi, qj in self.queens:
                if qi == i:
                    return False
                if qj == j:
                    return False
                if i - j == qi - qj:
                    return False
                if i + j == qi + qj:
                    return False
            return True

        def __str__(self):
            s = ''
            for i in range(self.size):
                for j in range(self.size):
                    if (i, j) in self.queens:
                        s += "Q"
                    else:
                        s += "."
                s += '\n'
            return s

    def __init__(self):
        self.board = self.Board(self.SIZE)

    def add_queen(self, i, j):
        self.board.place(i, j)

    def solve(self):
        def _solve(board, si, sj):
            if board.count() == self.NQUEENS:
                return board

            for i, j in _from_pos(si, sj):
                if board.ok(i, j):
                    b = deepcopy(board)
                    b.place(i, j)
                    result = _solve(b, i, j)
                    if result is not None:
                        return result
            else:
                return None

        def _from_pos(i, j):
            for n in range(i*self.SIZE + j, self.SIZE*self.SIZE):
                yield (n // self.SIZE, n % self.SIZE)

        self.board = _solve(self.board, 0, 0)

    def __str__(self):
        if self.board is None:
            return 'no solution'
        else:
            return str(self.board)


def run():
    n = int(input())
    q = EightQueen()

    for _ in range(n):
        i, j = [int(i) for i in input().split()]
        q.add_queen(i, j)

    q.solve()
    print(q)


if __name__ == '__main__':
    run()