How do I calculate how many ways 14 non-attacking bishops can be placed on a chessboard?

It's possible to place up to 14 non-attacking bishops on a chessboard.

How can I calculate the number of valid configurations, without writing a program to brute force it?

I've checked Non Attacking Chess Pieces, but it doesn't cover the variation I'm interested in, and a quick Google hasn't yielded useful results.

UPDATE: Proof that only 14 bishops can be placed:

If we divide the chessboard into diagonals, and we treat diagonal 1 and 15 as the same diagonal, then the maximum number of bishops per diagonal is 1, therefore 14.

Chessboard diagonals

Here is an example configuration of 14 bishops to show it's possible:

14 non-attacking bishops

NOTE: Not a duplicate of this question because I am asking about the number of arrangements of 14 bishops, not the maximum number of bishops on a chess board.


Solution 1:

Look at the board and count the number of diagonals one direction let's say negative slope there are 7 white and there are 7 black diagonals. So 14 is definitely the largest possible number. For what I'm going to say to make sense make sure you have your chessboard in standard orientation (white in the bottom right-hand corner). I'm going to use / to mean positive sloped diagonal and \ to mean negative sloped diagonal.

Start with the white diagonal in the upper right hand \ diagonal. You have 2 choices to place a bishop here, but then you have made the choice for the bottom left hand \ diagonal. This eliminates the middle two / diagonals from consideration from the rest. So the 2nd \ diagonal down has two choices and similarly forces the next diagonal up to be the other value. This eliminates the next middle two / diagonals from choices. Continue in this manner until you've eliminated you've chosen a place for all the white bishops there are $2^4$ similarly you'll get $2^4$ independent positions for the black bishops. So you can find $2^8=256$ different configurations.

Note: I believe this is effectively brute force since you can recover every configuration from this algorithm we just count them instead of write them down :)

Solution 2:

Let's convert the chessboard into points: (rank,file). The normal chessboard refers to file A through H. We will use 1 through 8. Consider the number rank minus file:

$$\begin{matrix} & & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline 8 & | & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 0 \\ 7 & | & 6 & 5 & 4 & 3 & 2 & 1 & 0 & -1 \\ 6 & | & 5 & 4 & 3 & 2 & 1 & 0 & -1 & -2 \\ 5 & | & 4 & 3 & 2 & 1 & 0 & -1 & -2 & -3 \\ 4 & | & 3 & 2 & 1 & 0 & -1 & -2 & -3 & -4 \\ 3 & | & 2 & 1 & 0 & -1 & -2 & -3 & -4 & -5 \\ 2 & | & 1 & 0 & -1 & -2 & -3 & -4 & -5 & -6 \\ 1 & | & 0 & -1 & -2 & -3 & -4 & -5 & -6 & -7\end{matrix}$$

Notice how these numbers are constant on the diagonals?

Next consider rank + file:

$$\begin{matrix} & & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline 8 & | & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ 7 & | & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ 6 & | & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ 5 & | & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ 4 & | & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 3 & | & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ 2 & | & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 1 & | & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\end{matrix}$$

Notice how these numbers are constant on the opposite diagonals? So, you are looking for 14 pairs of numbers from 1 through 8 such that you get 14 distinct pairs (rank-file,rank+file) such that no other pair shares the same rank-file or rank+file.

I went through my old notes to see where I remember a similar problem to this. It may have been the seminar I took that discussed block designs. I did not actually take a class that focused on block designs, so I do not recall the set up. I think this approach could be interesting (and give more details about configurations), but also far more time consuming and maybe not worth it. Specifically, this is a problem for a Transversal Design.