模倣子 8-Rook Problem

 Macromemetics Index

Introduction

The problem is to enumerate all of the ways to cover a "white board" with eight non-attacking rooks. Rotationally symmetric configurations are redundant.

The Basics

There are 8! = 40,320 ways to cover the board with rooks that are not attacking each other. This is simply placing a rook at one row in each file, leaving seven rows in the next file, etc. Since each of these configurations may be generated from any of the four edges, they are redundant and their count must be divided by four, giving 10,080 rotationally distinct configurations.

However, there are some configurations which when rotated by a quarter turn (1/4 spin) produce the same configuration, e.g., rooks all along the diagonal.

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

There are also configurations where the exact same configuration obtains regardless of the number of rotations. For example,

	x
							x
				x
		x
					x
			x
x
						x

I call these "pinwheel" configurations. 

Question: are there any configurations where a half-spin obtains the same configuration?

The problem then becomes to enumerate the quarter-spin, half-spin, and pinwheel configurations and subtract them from the total. 

Let's take a moment to understand this. There are four ways to generate any configuration, i.e., beginning the generation process from any of the four edges. Each of these configurations is rotationally symmetric to the other four, hence we divide the contribution of this configuration by four. This sounds like pinwheels do not require special treatment.

Hypothesis: The contribution of a pinwheel to the total number of combinations is the same as any other.

In other words, while a "regular" generated tiling is rotationally symmetric to four other tilings (generated from the other four edges), a pinwheel tiling is rotationally symmetric to itself, in other words, it's contribution to the total should still be divided by four.

The set contribution logic is as follows: the string of 8-digit "words" (all blanks with one rook in the midst) is the same from each edge, just as with a "messy" tiling. This means that each configuration is still identical and the total rotationally unique contribution should be divided by four.

This is not true, however, of quarter rotation, or quarter-spin, tilings, such as the two diagonals. The word strings of generation from each edge are not the same, so the contribution to the total set size appears to be larger.

Q1-Q3 Sequestered Tilings

Let's name the quadrants:

Q1	Q2
Q4	Q3

The tilings that look differently, i.e., are generated as two different tilings, but when rotated by a quarter turn are congruent, may yield a different contribution to the total set size.

Hypothesis 1: a configuration in which half the rooks are sequestered in non-attacking configuration in Q1 and the others non-attacking in Q3 will be globally non-attacking.

Note: There are 4! = 24 possible ways to tile a quarter of the board with 4 rooks, and 4! x 4! = 576 tilings with four rooks in either Q1 or Q3.

Hypothesis 2: In a Q1/Q3-sequestered tiling, the configurations of Q1 and Q3 are independent.

Corollary 2.1: "Messy corners" tilings will be rotationally symmetric to their quarter-turn, half-turn, and three-quarter-turn homologs, hence their contributions will be one-eighth.

Corollary 2.2: With Q1/Q3 diagonal reflective congruence, the tiling is quarter-turn symmetric. There are 4! = 24 such tilings, hence, half contribution to total set size.

Corollary 2.3: Congruent corner tilings are a subset of "messy corners" tilings, which should obtain 576 - 24 = 552 messy corner tilings (with one-quarter contributions).

Hypothesis 4: Tilings may exist where some rooks "elope" to Q2

Corollary 4.1: Elopement tilings may be impossible with "messy corners"

Corollary 4.2: Elopement tilings will produce additional quarter- and half- and three-quarter-rotation tilings.

Corollary 4.3: Pinwheels are a special case of elopement tilings.

Corollary 4.4: Pinwheels may be a spanning set of elopement tilings (this should be fun to prove!)

Hypothesis 5: Any "elopement" of a rook from Q1 to any file in Q2 along the same rank will be non-attacking.

Corollary 5.1: Eloped rooks will continue to be non-attacking across a quarter rotation (e.g., Q1 to Q4, Q2 to Q1).

Hypothesis 6: There is some non-empty set of elopements of rooks from Q1 to Q2 that are also non-attacking when reflected across the diagonal to Q3, and which do not produce pinwheels. This is the "Big One," by the way.

Lemma 6.1: If hypothesis 6 does NOT obtain, then corollary 2.3 exhausts the set of all "non-messy" tilings, in terms of contribution to set size.

What We Have So Far...

To sum up, we have that we divide the contribution of all configurations by four, since the same configuration may be generated from each edge, and is thus rotationally symmetrical and redundant. 

We further have that "pinwheels" make the same contribution to set size.

Tilings in which rooks are sequestered to diagonal corners is so far the only case in which rotational symmetry redundancy actually removes some configurations from the total set size.

Pinwheels are a special case of some rooks "eloping" to Q2 to be non-attacking from both Q2 (obviously) and also Q3 (in rotation/reflection). In the case of pinwheels, Q2 is congruent to Q1 (and Q3). The question is whether it is possible to describe non-pinwheel cases where rooks elope so as to be non-attacking in both Q2 and Q3 and yet not be congruent to Q2?

This may actually be trivial.

So the count should be something like ( 40,320 - 576 ) / 4+ 552 / 12 + 24 / 8 = 

...pending further investigation...more to be revealed...

Let's Talk About Sets! 

A = the set of all patterns  num(A) or n(A) = 8!

Ar = the complete non-redundant set   Ar <= A "is contained by / a subset of"

n(Ar) is what we want to find out! It's bounding value should be 8! / 4  There are rotatable combinations which need to be subtracted out from this bounding total.

S = the set of "sequestered corners" where all rooks are in Q1 & Q4

the bounding value of n(M) looks like 4! x 4! but some patterns are more rotatable than others, see "messy" versus "reflected (clean) corners"

Just to be clear, the following sets represent subsets of A which are able to rotate (in some cases) so that their impact on removing numbers of distinct cases from A may be double or quadruple. For instance, with set C below (reflected corners) each set member enumerated represents two members of set A that are duplicates. That is, both of those members are present, and one of them needs to be subtracted out.

C = the set of all "reflected corner" patterns (Q1 = Q4)

n(C) should be 4!

members of this set may be quarter-rotated, hence we subtract 2 x n(C) from n(A) / 4 for n(Ar)

C <= S  

M = the set of all "messy corner" patterns (Q1 <> Q4)

members of this set may be rotated three ways, hence we subtract 4 x n(M) from n(A) / 4 to get n(Ar)

the bounding value of n(M) should be 4! x 4! but we have "clean corners" to remove.

Hence, n(Mr) =  4! x 4!  / 16 - 4! / 8

E = "elopement tilings"

E <= A, not E <= C  also E => P "pinwheels"

but E is generated from C, hence E = g(C)

members of E may be quarter-rotated, hence subtract 2 x n(Er) = from n(A)/4 for n(Ar)

but we must exclude the pinwheel tilings since they have no rotation dependence

hence 2 x ( n(E) - n(P) ) subtracted from n(A) / 4 to get n(Ar)

P = "pinwheel tilings"

all rotations of members of this set are the same, hence n(Pr) = n(P) / 4

P <= E  this is the tricky bit. It may be possible to enumerate all of E, but difficult to formulaically enumerate P

So what we're looking for, i.e., all of the unique patterns, ignoring rotations, should look something like:

n(Ar) = n(A) / 4 - n(Cr) - 3 x n(Mr) - n(Er) + n(Pr)

Elopement Tilings

Hypothesis 7: an eloping rook that comes from the diagonal of Q1, and goes to the diagonal of Q2 will not be in attack when reflected to Q3

Corollary 7.1: If a rook does not go diagonal to diagonal between Q1 and Q2, it may avoid attack with a rook in Q1 when it is reflected to Q3. This is a pinwheel requirement

Lemma 7.1: A pinwheel cannot have rooks on the corners

How many patterns with at least one rook on the diagonal are there?

Hypothesis 8: The set of all patterns generated by eloping rooks from C, ie, E = g(C), will generate a superset containing all pinwheels (this should be fun to prove)

Each quadrant is made up of subquadrants, noted here in lowercase:

Q1	q1	q2	Q2	q1	q2
	q4	q3		q4	q3
Q4	q1	q2	Q3	q1	q2
	q4	q3		q4	q3

...and each of these subquadrants is a quadrilles of rooks and spaces. All of these rotate together, so we have to think about which quadrilles can be next to which others, and which can be in neighboring quadrants without attacking. Likewise, all of these quadrilles must be non-attacking to the neighboring quadrants.

first rotation	second rotation	third rotation	fourth rotation
a   b   d  c	b   c   a  d	c  d  b  a	d  a   c   b

Hypothesis 9: a quadrant must be populated by subquadrants which are non-attacking of their neighboring subquadrants, and also of the neighboring quadrants.

Corollary 9.1: there are exactly seven different possible quadrilles for a subquadrant, namely, one rook in any of the corners, rooks in upper left and lower right, or upper right and lower left.

Lemma 9.1.1: let's number these quadrilles one through six, i.e., upper left, upper right, lower right, lower left, then five is upper left and lower right, and six is upper right and lower left "backslash", and seven is blank (no rooks) just like how we've been numbering the quadrants and subquadrants.

one	two	three	four	five	six	seven
x	x	x	x	x          x	x    x

Corollary 9.2: there are a limited number of patterns of subquadrants that can make up quadrants with non-attacking rook elopement

Lemma 9.2.1: A five or six quadrille in any subquadrant means only seven (blank) quadrilles can occupy any subquadrants in the same rank or file.

Lemma 9.2.2: A one or two quadrille in any subquadrant means only three or four or blank quadrilles may occupy any subquadrants in the same rank

Lemma 9.2.3: A one or four quadrille in any subquadrant means only two or three quadrilles may occupy any subquadrants in the same file.

Lemma 9.2.4.1: In right rotation, a one quadrille becomes a two, a two becomes a three, and a three becomes a four. A five becomes a six and a six becomes a five.

Lemma 9.2.4.2: In a left rotation, a one quadrille becomes a four, a two becomes a one, a three becomes a two, and a four becomes a one. Fives and sixes change one to the other.

Hypothesis 10: if two quadrants Q1 and Q2, may constructed as non-attacking, their left or right rotation will be non-attacking.

Hypothesis 11: For two non-attacking quadrants Q1 and Q2, the reflection of Q2 to Q4 (or Q1 to Q3) will also be non-attacking

Hypothesis 12: If the reflection of Q2 is non-attacking of Q1 and it's rotation to Q4 is also non-attacking, then the configuration is a pinwheel.

Hypothesis 13: There exist (non-trivial) non-congruent to Q2 (either by reflection or rotation) configurations of Q4 which are non-attacking of Q1. In other words, three or more corners may be different and still non-attacking.

Note: