n-rooks problem , n-bishops problem
QSCGZ
How many solutions are there, to place n chess-rooks (2*n-2 bishops)
on an n x n chessboard, such that no rook attacks another one ?
Symmetric solutions are counted only once.
Is there a simple algorithm to count them for n= say 100 ?
Green Kevin D
QSCGZ (qs...@aol.com) wrote:
: How many solutions are there, to place n chess-rooks (2*n-2 bishops)
: Symmetric solutions are counted only once.
: Is there a simple algorithm to count them for n= say 100 ?
In the rook problem, the total number of placements is n!.
The problem arises in trying to determine how many positions
are rotations and reflections of another. Some postions can
only be rotated and/or reflected to give 2 distinct positions.
Others give 4 or 8. I'm going to go out on a limb and say that
there is no simple way of dealing with this.
The bishop problem is a little easier to deal with. I believe
there is only one essentially distinct method of placement.
I could of course be dead wrong about both. :)
Kev
Jay Cox
Green Kevin D wrote:
>
> QSCGZ (qs...@aol.com) wrote:
> : How many solutions are there, to place n chess-rooks (2*n-2 bishops)
> : on an n x n chessboard, such that no rook attacks another one ?
> : Symmetric solutions are counted only once.
> : Is there a simple algorithm to count them for n= say 100 ?
>
> In the rook problem, the total number of placements is n!.
> The problem arises in trying to determine how many positions
> are rotations and reflections of another. Some postions can
> only be rotated and/or reflected to give 2 distinct positions.
> Others give 4 or 8. I'm going to go out on a limb and say that
> there is no simple way of dealing with this.
ok, If it doesn't matter where the rooks are placed, you can have a
checkerboard pattern
and a maximum amount of 32 rooks on the board in a checkerboard pattern.
I think the solution is this.
choose a place on the board (64 choices)
now you have 31 remaining choices. choose one and now you have 30
choices.. etc etc.
64 for 1 rook
64*31 for two rooks
64*31*30 for three rooks....
64*31*30*29 ....
Jay
Stan Armstrong
In article <686e0b$boi$1...@ursa.smsu.edu>, Green Kevin D
<kdg...@cnas.smsu.edu> writes
>QSCGZ (qs...@aol.com) wrote:
>: How many solutions are there, to place n chess-rooks (2*n-2 bishops)
>: on an n x n chessboard, such that no rook attacks another one ?
>: Symmetric solutions are counted only once.
>: Is there a simple algorithm to count them for n= say 100 ?
>
>The bishop problem is a little easier to deal with. I believe
>there is only one essentially distinct method of placement.
>
eighth rank and one with 8 and 6. i.e. you can move one of the corner
bishops in the first to the other end of its diagonal to get the second.
This surely cannot be regarded as a rotation or reflection.
>
>
--
Stan Armstrong "a louse i used to know told me that millionaires
and bums taste much the same to him."
archie the cockroach - via don marquis
Mike ROBSON
Stan Armstrong <St...@stanleya.demon.co.uk> writes:
>In article <686e0b$boi$1...@ursa.smsu.edu>, Green Kevin D
><kdg...@cnas.smsu.edu> writes
>>QSCGZ (qs...@aol.com) wrote:
>>: How many solutions are there, to place n chess-rooks (2*n-2 bishops)
>>: on an n x n chessboard, such that no rook attacks another one ?
>>: Symmetric solutions are counted only once.
>>: Is there a simple algorithm to count them for n= say 100 ?
><snip>
>>
>>The bishop problem is a little easier to deal with. I believe
>>there is only one essentially distinct method of placement.
>>
>It seems to me that there are two: on with 7 on each of the first and
>eighth rank and one with 8 and 6. i.e. you can move one of the corner
>bishops in the first to the other end of its diagonal to get the second.
>This surely cannot be regarded as a rotation or reflection.
>>
>>
And there are others as well since you can rotate the black square
bishops while leaving the rest, i.e. use all the white squares on
the first and last rank and the black squares on the a and h files
minus one white and one black corner.
There are certainly other possibilities. I think there are 2^(n-2)
distinct ones if you allow rotations but not reflections. With
reflections it must be half of this plus a few (to allow for
symmetric patterns).
--
J.M. Robson
LaBRI, Universite Bordeaux 1
QSCGZ
>>>: How many solutions are there, to place 2*n-2 bishops
>>>: on an n x n chessboard, such that no bishop attacks another one ?
>>>: Symmetric solutions are counted only once.
>
>. I think there are 2^(n-2)
>distinct ones if you allow rotations but not reflections. With
>reflections it must be half of this plus a few (to allow for
>symmetric patterns).
yes,I think that's correct.
There are no rotation-symmetric solutions.
But how many are 'plus a few' ?
In the 8x8 case, the solution is 36.
Dan Hoey
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
Ho...@AIC.NRL.Navy.Mil
Dan Hoey
qs...@aol.com (QSCGZ) asked:
> How many solutions are there, to place n chess-rooks...
> on an n x n chessboard, such that no rook attacks another one ?
> Symmetric solutions are counted only once.
There are eight symmetry operations of the chessboard: three
rotations, four reflections, and the identity. Counting the number of
positions that are left unchanged by the various symmetry operations
is a tedious but not terribly difficult combinatorial exercise. For
n>1 there are
[n/2]!
R_Q(n) = ------ if [n/2] is even, 0 otherwise
[n/4]!
positions unchanged by 90-degree rotations,
R_S(n) = [n/2]! 2^[n/2]
positions unchanged by 180-degree rotations,
[n/2] n!
R_L(n) = Sum --------------
i=0 (n-2i)! i! 2^i
positions unchanged by each diagonal reflection, none unchanged by an
orthogonal reflection, and n! unchanged by the identity.
From the Cauchy-Frobenius-Polya-(not)Burnside theorem we can compute
the number of positions up to symmetry by counting the average, over
all symmetry operations, of the number of positions left unchanged:
R(n) = (2 R_Q(n) + R_S(n) + 2 R_L(n) + 0 + n!)/8.
n 0 1 2 3 4 5 6 7 8 9 10 11 12
R(n) 1 1 1 2 7 23 115 694 5,282 46,066 456,454 4,999,004 59,916,028
and R(100)=11,665,776,930,493,019,085,212,404,857,033,337,561,339,-
496,033,047,702,683,574,120,486,902,199,999,159,757,-
068,380,354,180,755,001,424,896,581,199,329,890,890,-
062,330,104,725,878,634,060,229,093,973,813,100,544.
This is sequence A000903 in Sloane and Plouffe (see
http://www.research.att.com/~njas/sequences).
Dan Hoey
Ho...@AIC.NRL.Navy.Mil
QSCGZ
How many solutions are there, to place 2*n-2 chess-bishops
on an n x n chessboard, such that no bishop attacks another one ?
Symmetric solutions are counted only once.
Ho...@AIC.NRL.Navy.Mil (Dan Hoey) proved :
> there are 2^n possible ways of placing the bishops before
> reducing by symmetry
> there are 2^floor((n+3)/2) symmetric positions
> the total number of arrangements is 2^(floor((n-3)/2) + 2^(n-3). {if n>1}
which completely solves the bishops-case .
------------------------------------------------------------
> qs...@aol.com (QSCGZ) asked:
>> How many solutions are there, to place n chess-rooks...
>> on an n x n chessboard, such that no rook attacks another one ?
>> Symmetric solutions are counted only once.
Ho...@AIC.NRL.Navy.Mil (Dan Hoey) answered :
Thanks for you efforts !
I found some of the rook-results with computer-help, by forecasting
small n results , and looking for patterns.
I remember, that I once looked at Slaone and Plouffe, but only found
A000085 (your R_L(n)), I wonder, why I missed A000903.
BTW A000017 (symmetric n-queens) must be wrong .
Do you think, it's possible, that someone ever finds a formula
for n-queens too ?
qs...@aol.com , 1998/01/15,8:10 GMT