Newsgroups: rec.puzzles
From: Hoey@AIC.NRL.Navy.Mil (Dan Hoey)
Date: 1998/01/11
Subject: Re: n-rooks problem , n-bishops problem

qs...@aol.com (QSCGZ) writes:

> >>>: How many solutions are there, to place n chess-rooks (2*n-2 bishops)
> >>>: on an n x n chessboard, such that no rook (bishop) attacks another one ?
> >>>: Symmetric solutions are counted only once.

Assume n>1.  For bishops, consider a family of 2n-1 parallel
diagonals.  The endmost diagonals (of length 1) cannot both have
bishops on them, and the remaining 2n-3 diagonals can have at most one
bishop each.  This establishes the bound of 2n-2 bishops.  For k > 1,
suppose we populate all but one of the diagonals of length less than
k, and consider the diagonal(s) of length k.  Each such diagonal will
have k-2 squares forbidden by previously placed bishops, so the only
places that bishops can be placed are at one of the endpoints.  This
establishes that all bishops will be on the edges of the board.

So any arrangement of 2n-2 non-attacking bishops will have two bishops
at the ends of the long diagonals (i.e., in adjacent corners) and two
bishops at opposite corners of each of n-2 45-degree rectangles:

 . . . . 2 . .
 . . . x' `x .
 . . x'. . .`1    Either there are bishops at both 2s
 . x'. . . x'.     or bishops at both 1s.
 1'. . . x'. .
 .`x . x'. . .
 . .`2'. . . .

So there are 2^n possible ways of placing the bishops (before reducing
by symmetry).  Because exactly two adjacent corners are populated, no
such pattern can be symmetric under rotation or diagonal reflection.
For orthogonal reflection, the symmetric patterns will have an axis
determined by the populated corners, and then the floor((n-2)/2) pairs
of rectangles must agree:

 . . 4 . 2 . b
 . x'.`x' `x .    If this is symmetric through the reflection
 3'. x'.`x .`1     determined by the bs, then either there are
 .`x'. . .`x'.     bishops at the 2s and 4s or there are bishops
 1'.`x . x'.`3     at the 1s and 3s..
 .`x .`x'. x'.
 . .`2'.`4'. b

If n is odd, the equilateral rectangle will always be symmetric under
orthogonal reflection.  So there are 2^floor((n+3)/2) symmetric
positions and 2^n-2^floor((n+3)/2) asymmetric positions; the former
appear in 4 orientations, and the latter in 8.  So the total number of
arrangements is

  (2^floor((n+3)/2))/4 + (2^n-2^floor((n+3)/2))/8
    = 2^(floor((n-3)/2) + 2^(n-3).

This works out to:

      n   0  1  2  3  4  5  6  7  8  9  10  11  12   13   14   15
positions 1  1  1  2  3  6 10 20 36 72 136 272 528 1056 2080 4160

and for n=100, there are 158456325028528956662064611328 positions.

The analysis for rooks is harder, since there are five kinds of
symmetry possible (reflection through two diagonals, reflection
through one diagonal, four-fold rotation, two-fold rotation, and
asymmetry).  Still, it's not impossible to carry out by hand for
small boards.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil