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: import copy as cp
  
  N = 8
  ans = []
  
  
  def out(M):
      for i in range(N):
          for j in range(N):
              print(M[i][j], end="")
          print("")
  
  
  def DFS(r, c, dp, dn, qn):
      global ans
      if qn == N:
          for h in range(N):
              for w in range(N):
                  if r[h] & c[w] & dp[h + w] & dn[w - h + 7]:
                      ans.append([h, w])
                      return True
          return False
  
      for h in range(N):
          for w in range(N):
              if r[h] & c[w] & dp[h + w] & dn[w - h + 7]:
                  new_r = cp.deepcopy(r)
                  new_c = cp.deepcopy(c)
                  new_dp = cp.deepcopy(dp)
                  new_dn = cp.deepcopy(dn)
                  new_r[h], new_c[w], new_dp[h + w], new_dn[w - h + 7] = (
                      False,
                      False,
                      False,
                      False,
                  )
                  if DFS(new_r, new_c, new_dp, new_dn, qn + 1):
                      ans.append([h, w])
                      return True
      return False
  
  
  def main():
      row = [True] * N
      col = [True] * N
      dp = [True] * (2 * N - 1)
      dn = [True] * (2 * N - 1)
      k = int(input())
      MAP = [["." for _ in range(N)] for __ in range(N)]
      for _ in range(k):
          h, w = map(int, input().split())
          MAP[h][w] = "Q"
          row[h] = False
          col[w] = False
          dp[w + h] = False
          dn[w - h + 7] = False
  
      DFS(row, col, dp, dn, k + 1)
  
      for h, w in ans:
          MAP[h][w] = "Q"
  
      out(MAP)
  
  
  main()
  
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..."}]