Bishop game - python
O(n)

You can transform the (row,column) coordinate of a bishop to a (row+column, row-column) coordinate. The row+column coordinate tells you which upper-left to lower right diagonal the bishop is on.  The row-column coordinate tells you which upper-right to lower-left diagonal the bishop is on.  

      row + col                     row - col
7  8  9 10 11 12 13 14       7  6  5  4  3  2  1  0
6  7  8  9 10 11 12 13       6  5  4  3  2  1  0 -1
5  6  7  8  9 10 11 12       5  4  3  2  1  0 -1 -2
4  5  6  7  8  9 10 11       4  3  2  1  0 -1 -2 -3
3  4  5  6  7  8  9 10       3  2  1  0 -1 -2 -3 -4
2  3  4  5  6  7  8  9       2  1  0 -1 -2 -3 -4 -5
1  2  3  4  5  6  7  8       1  0 -1 -2 -3 -4 -5 -6
0  1  2  3  4  5  6  7       0 -1 -2 -3 -4 -5 -6 -7


Now create two dictionaries.  One that maps each row+col value to a list of bishops on that diagonal.  The other one similarly maps the row-col value.  Any dict entry with more than one bishop, means all of those bishops are in danger.

bishops = [(0, 0),
           (1, 1),
           (0, 2),
           (1, 3),
           (2, 0),
           (2, 2)]

nwse = {}
nesw = {}

for row,col in bishops:
    nwse_index = row + col
    if nwse_index not in nwse:
        nwse[nwse_index] = [(row,col)]
    else:
        nwse[nwse_index].append((row,col))

    nesw_index = row - col
    if nesw_index not in nesw:
        nesw[nesw_index] = [(row,col)]
    else:
        nesw[nesw_index].append((row,col))

in_danger = set()

for k,v in nwse.items():
    if len(v) &gt; 1:
        in_danger.update(v)

for k,v in nesw.items():
    if len(v) &gt; 1:
        in_danger.update(v)

safe_bishops = set(bishops) - in_danger

print(len(safe_bishops))


Improved code

based on AJNeuman's answer and my comment below.

The row - col index is offset by adding -8 so that all the values will be &lt; 0.
The row + col index are all > 0. So just one dict is needed.

from collections import defaultdict

bishops = [(0, 0),
           (1, 1),
           (0, 2),
           (1, 3),
           (2, 0),
           (2, 2)]


occupied_diagonals = defaultdict(list)

for bishop in bishops:
    row, col = bishop
    occupied_diagonals[row + col].append(bishop)
    occupied_diagonals[row - col - 8].append(bishop)

in_danger = set()

for bishop_list in occupied_diagonals.values():
    if len(bishop_list) &gt; 1:
        in_danger.update(bishop_list)

print(len(in_danger))