title: Is there a constant time solution to the safe queens problem?(python)
body: <p>I'm working on the safe queens problem and I'm curious if there is a constant time solution to the question. </p>
  
  <h2>Safe Queens</h2>
  
  <p>In chess the queen is the most powerful piece, as it can move any number of unoccupied squares in a straight line along columns (called "files"), rows (called "ranks"), and diagonals. It is, however, possible to place 8 queens on a board such that none are threatening another.</p>
  
  <p>In this challenge we read an input of 8 positions in standard algebraic notation (files "a" to "h" and ranks "1" to "8"). Our goal is to determine, using the safe_queens function, if all of the queens are safe from each other – that is, none of them should share a file, rank, or diagonal. If they are all safe, the function should print 'YES', otherwise it should print 'NO'.</p>
  
  <p>Example:
  Input:
  a5
  b3
  c1
  d7
  e2
  f8
  g6
  h4</p>
  
  <p>(example input positions shown on board below)</p>
  
  <p>Output:
  YES</p>
  
  <p>This example outputs 'YES' because no queens share a file, rank, or diagonal. If the a5 were an a4 it would output 'NO' because the leftmost two queens would be on the same diagonal.</p>
  
  <p>I believe that you could transform the solution be into constant time by keeping track of visited squares and checking for inference for the diagonals, but I'm not 100% sure.</p>
  
  <pre><code>def safe_queens():
    positions = [input() for _ in range(8)]
  
    # if there isn't exactly one queen per file and per rank then return 'NO'
    if (len({i[0] for i in positions}) != 8) or (
        len({i[1] for i in positions}) != 8):
         return 'NO'
  
    # to check diagonals compare difference between each queen combinations
    # rank values and file values, adjust for both diagonal directions by 
    # using abs()
    for p in range(8):
      for q in range(p+1, 8):
        if (abs(ord(positions[p][0]) - ord(positions[q][0]))) == (
            abs(int(positions[p][1]) - int(positions[q][1]))):
          return 'NO'
    return 'YES'
  </code></pre>
  
  <p>Link to colab notebook with the problem description and my soluion: <a href="https://colab.research.google.com/drive/1sJN6KnQ0yN-E_Uj6fAgQCNdOO7rcif8G" rel="nofollow noreferrer">https://colab.research.google.com/drive/1sJN6KnQ0yN-E_Uj6fAgQCNdOO7rcif8G</a></p>
  
  <p>The solution above is O(n^2), but I'm looking for a constant time solution. Thanks!</p>