11
$\begingroup$

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

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

Improve this question
$\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
    Commented Aug 29, 2015 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
    Commented Aug 30, 2015 at 11:23

1 Answer 1

Reset to default
1
$\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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .