10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you know if it is possible to place 15 bishops on the board? I assume it is not, but understanding why not, and why 14 is the max, will probably go a long ways towards finding the answer. $\endgroup$ – Bram28 Jun 7 '18 at 14:17
  • $\begingroup$ @Bram28 Not possible, proof added. $\endgroup$ – Gustav Bertram Jun 7 '18 at 14:30
  • $\begingroup$ What do you mean by treating diagonals $1$ and $15$ as the same? $\endgroup$ – Théophile Jun 7 '18 at 14:45
  • 1
  • 3
    $\begingroup$ @ShubhrajitBhattachrya This definitely seems like a separate question from that one. While they deal with bishops on a chessboard, this question asks about number of arrangements for 14 nonattacking bishops, not whether or not 15 nonattacking bishops are possible (that is not even mentioned in the original problem and has no direct bearing on its solution). $\endgroup$ – InterstellarProbe Jun 7 '18 at 16:05
6
$\begingroup$

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 :)

$\endgroup$
  • $\begingroup$ For \ diagonals you actually have 7 white and 8 black diagonals, but the black corner diagonals can be treated as one since you can only pick whether to put the bishop on the top or the bottom black corner. $\endgroup$ – Gustav Bertram Jun 7 '18 at 14:50
  • 1
    $\begingroup$ I don't think you need to distinguish black and white bishops, the logic of eliminating the choice for the other diagonal of the same size holds. Very elegant. $\endgroup$ – Gustav Bertram Jun 7 '18 at 14:51
  • $\begingroup$ @GustavBertram yeah I got lazy with the black bishops. I think i'd rather consider choosing the positive sloped diagonals / for them. Alternatively, you could just argue by symmetry that there will be the same number of choices for white as black (switching white & black and rotating the board by a right angle leaves the board invariant so it should be the same for white and black) $\endgroup$ – N8tron Jun 7 '18 at 15:05
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I don't understand how you can count the total number of ways to get the 14 from this. Can you elaborate? $\endgroup$ – N8tron Jun 7 '18 at 14:25
  • 1
    $\begingroup$ For rank-file, you need the -7 or the 7 (you cannot get both, as they both correspond to rank+file of 9). There are 2 ways to get it. For rank+file, you need the 2 or the 16 (you cannot get both, as they both correspond to rank-file of 0). There are 2 ways to get that. Choose what is most restrictive. This will make the later choices more restrictive. Chessboards have lots of symmetry, so any restriction made in one scenario is likely to be made in lots of scenarios. $\endgroup$ – InterstellarProbe Jun 7 '18 at 14:36
  • $\begingroup$ Okay sounds like we are effectively counting the same way. Can you edit in a little more interpretation on how this is counted at the end? $\endgroup$ – N8tron Jun 7 '18 at 14:41
  • 1
    $\begingroup$ I did something similar when I took combinatorics years ago. I believe it wound up being a derangement problem, but off the top of my head, I do not recall the details. I will edit it later tonight when I get home. $\endgroup$ – InterstellarProbe Jun 7 '18 at 14:47
  • 2
    $\begingroup$ I'd be interested in the details. $\endgroup$ – Gustav Bertram Jun 7 '18 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.