9
$\begingroup$

The number of ways to place k bishops in a nonattacking configuration on an n by n square board is a well known result and can for example be found in http://problem64.beda.cz/silo/kotesovec_non_attacking_chess_pieces_2013_6ed.pdf

However, trying to generalize the result to a rectangular board seems rather difficult. Has there been any progress on this front?

$\endgroup$
2
  • 2
    $\begingroup$ Can't the black squares and the white squares be thought of separately, that is, sum over $w+b=k$ bishops, and place $b$ black, non-attacking bishops on the board... Then, the black squares and black bishops can be thought of as rooks, and then you are dealing with rook placements, for which there is extensive literature. $\endgroup$ – Per Alexandersson Aug 29 '15 at 18:10
  • 1
    $\begingroup$ Yes, that is the normal method of dealing with the problem for the square case, in which the squares of each color form a Ferrers board. However, in the general rectangular case, you only have a quasi-Ferrers board, which makes the calculation more difficult, and as far as I know, there is no literature on rook polynomials for such boards. $\endgroup$ – ruadath Aug 30 '15 at 11:23
0
$\begingroup$

Search

Berghammer R. Relational Modelling and Solution of Chessboard Problems. in: RAMICS (Relational and algebraic methods in computer science), 12th international conference, Rotterdam, Netherlands May 20 - June 3 2011. Heidelberg, Springer; 2011

If I'm not mistaken, Dr Berghammer investigated the topic at this conference, although I didn't go, so double check it.

I believe that the max # of ind bishops is either $m+n-1$ or $m+n-2$ depending upon three cases, with $n>m$: $m,n$ both odd; exactly one of $m,n$ are even, and $m,n$ both even. So, the results are $m+n-2$ for $m=n$ or $m,n$ both even and $n>m$; otherwise $m+n-1$. It has been a while since I worked through the proofs of this independently, but as for the formations:

Given an $m \times n$ board, with $n>m$, plant bishops in the first and last columns. This will leave squares in the center that are neither attacked nor occupied, if $n>m+1$. You can then plant the needed number of independent bishops in the center.

Apologies for not being formal. My independent proof (which I've since deleted) was discovered sometime ago, and I don't feel it necessary to go through in detail considering the info is out there and the proof is a bit long.

I might add that the number of ways of placing maximum independent sets of bishops on the rectangular board is open. Kotosevec did find the number of ways of placing $k$ independent bishops on the square board.

$\endgroup$
2
  • $\begingroup$ The Kotosevec result was already noted, with a link, in the original question. $\endgroup$ – Gerry Myerson Nov 30 '20 at 0:06
  • $\begingroup$ Fair enough. The rest of the answer is relevant however. $\endgroup$ – Paul Burchett Nov 30 '20 at 4:17

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.