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 itertools
  import copy
  
  
  def is_safe(qweens):
      x = []
      y = []
      for q in qweens:
          x.append(q[0])
          y.append(q[1])
      if len(set(x)) + len(set(y)) != len(qweens) * 2:
          return False
      for q1, q2 in itertools.combinations(qweens, 2):
          slope = (q1[0] - q2[0]) / (q1[1] - q2[1])
          if slope == 1 or slope == -1:
              return False
      return True
  
  
  def print_boad(qweens):
      for r in range(8):
          for c in range(8):
              if (r, c) in qweens:
                  print("Q", end="")
              else:
                  print(".", end="")
          print("")
  
  
  k = int(input())
  cand = [[(r, c) for c in range(8)] for r in range(8)]
  init_qweens = []
  for _ in range(k):
      pos = tuple(map(int, input().split()))
      for r in range(8):
          for c in range(8):
              try:
                  cand[r].remove((pos[0], c))
              except ValueError:
                  pass
              try:
                  cand[r].remove((r, pos[1]))
              except ValueError:
                  pass
      init_qweens.append(pos)
  
  for r in range(7, -1, -1):
      if cand[r] == []:
          cand.pop(r)
  
  qweens = []
  for per in itertools.permutations([i for i in range(8 - k)]):
      qweens = copy.deepcopy(init_qweens)
      for r, c in enumerate(per):
          qweens.append(cand[r][c])
  
      if is_safe(qweens):
          break
  
  print_boad(qweens)
  
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..."}]