Bishop game - python A bishop can capture any other bishop if it lies along the same
  diagonal line, so long as no other bishop is in its path.
  Given a list of coordinates of the bishops locations, and a board size, determine how many bishops are unsafe. 


This code has a time complexity of \$O(N*K)\$ where N is the number of bishops, K is (N- current index). 

Is there a way to improve this? 

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

moves = [(1, 1), (1, -1), (-1, 1), (-1, -1)]

captured = []
for index, coordinates in enumerate(bishops):
    remaining = bishops[index + 1:]
    seen = bishops[:index + 1]
    for dx, dy in moves:
        x, y = coordinates
        while 0 &lt;= x + dx &lt; size and 0 &lt;= y + dy &lt; size:
            x += dx
            y += dy
            if (x, y) in seen:
                break
            if (x, y) in remaining:
                remaining.remove((x, y))
                capture = f"{coordinates} takes {x, y}"
                captured.append(capture)
                break

print(f"There are {len(captured)} moves")
print(*captured, sep = "\n")
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))