Queen Collisions

A lot of time has been spent by computer science students dealing with queens on a chessboard. Two queens on a chessboard collide if they are on the same row, column, or diagonal, and there is no piece between them. Boards of various sizes and numbers of queens are considered. For example, in Figure $1$, a 7 \times 7 board contains $7$ queens with no collisions. In Figure $2$, there is a 5 \times 5 board with $5$ queens and $4$ collisions. In Figure $3$, a traditional 8 \times 8 board, there are $7$ queens and $5$ collisions.

On an n \times n board, queen positions are given in Cartesian coordinates $(x,y)$, where $x$ is the column number from $1$ to $n$, and $y$ is the row number from $1$ to $n$. Queens at distinct positions (x_1, y_1) and (x_2, y_2) are on the same diagonal if |x_1-x_2| = |y_1-y_2|. They are on the same row or column if y_1 = y_2 or x_1 = x_2, respectively. In each of these cases, the queens have a collision if there is no other queen directly between them on the same diagonal, row, or column. For example, in Figure $2$, the collisions are between the queens at $(5,1)$ and $(4,2)$, $(4,2)$ and $(3,3)$, $(3,3)$ and $(2,4)$, and finally $(2,4)$ and $(1,5)$. In Figure $3$, the collisions are between the queens at $(1,8)$ and $(4,8)$, $(4,8)$ and $(4,7)$, $(4,7)$ and $(6,5)$, $(7,6)$ and $(6,5)$, and finally $(6,5)$ and $(2,1)$. Your task is to count the number of queen collisions.

In many situations there are a number of queens placed in a regular pattern. For instance, in Figure $1$ there are $4$ queens in a line at $(1,1)$, $(2,3)$, $(3,5)$, and $(4,7)$. Each of these queens, after the first at $(1,1)$, is one to the right and $2$ up from the previous one. Three queens starting at $(5,2)$ follow a similar pattern. Noting these patterns allows the positions of a large number of queens to be described concisely.

7 2
4 1 1 1 2
3 5 2 1 2
5 1
5 1 1 1 1
8 4
1 1 8 0 0
2 4 8 0 -1
2 6 5 1 1
2 2 1 1 1
0

0
4
5