output_description: 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 '.'.
input_description: 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.
attempt: # -*- coding:utf-8 -*-
  
  
  def solve():
      import itertools
      import copy
  
      K = int(input())
      grid = [[0 for i in range(8)] for j in range(8)]
  
      def put_queen(grid, r, c):
          for j in range(8):
              grid[r][j] = -1
          for i in range(8):
              grid[i][c] = -1
          # 左上
          i, j = r - 1, c - 1
          while i >= 0 and j >= 0:
              grid[i][j] = -1
              i, j = i - 1, j - 1
          # 左下
          i, j = r + 1, c - 1
          while i < 8 and j >= 0:
              grid[i][j] = -1
              i, j = i + 1, j - 1
          # 右上
          i, j = r - 1, c + 1
          while i >= 0 and j < 8:
              grid[i][j] = -1
              i, j = i - 1, j + 1
          # 右下
          i, j = r + 1, c + 1
          while i < 8 and j < 8:
              grid[i][j] = -1
              i, j = i + 1, j + 1
          grid[r][c] = 1
  
      for i in range(K):
          r, c = list(map(int, input().split()))
          put_queen(grid, r, c)
  
      # 8!を全探索
      ps = itertools.permutations([i for i in range(8)], r=8)
      for p in ps:
          ans_grid = copy.deepcopy(grid)
          is_ok = True
          for i in range(8):
              if ans_grid[i][p[i]] == 1:
                  continue
              if ans_grid[i][p[i]] == -1:
                  is_ok = False
                  break
              put_queen(ans_grid, i, p[i])
          if is_ok:
              break
  
      # ans_gridを出力して終了
      for i in range(8):
          s = ""
          for j in range(8):
              if ans_grid[i][j] == 1:
                  s += "Q"
              else:
                  s += "."
          print(s)
  
  
  if __name__ == "__main__":
      solve()
  
problem_description: 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.
  
  ![](https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_ALDS1_13_A_8queens)  
  
  For a given chess board where $k$ queens are already placed, find the solution
  of the 8 queens problem.
samples: [{"input": "2\n    2 2\n    5 3", "output": "......Q.\n    Q.......\n    ..Q.....\n    .......Q\n    .....Q..\n    ...Q....\n    .Q......\n    ....Q..."}]