One day == 2 weeks
... "my bad".
I'ld make excuses, but I wouldn't want to sound like I was making excuses.
Hi
Serg,
I'll skip over all of the detail except for how to get the number of grids, x, where (g x) = x ... where 'g' is a member of the transformation group associated with the "full boxes" pattern, and (g x) is the result of applying it to the grid.
First, 'g' is represented as a permutation of the cells in the "." boxes, by a list of "cell cycles" ... similar to what others have done (Russel & Jarvis, JPF, ...).
Here is an example for the anti-corner pattern itself, and the transformation that swaps columns 1&3, and cycles rows, 7->8->9:
- Code: Select all
g : (0,2),(9,11),(18,20),(27,29),(33,35),(39,41),(45,50,51,47,48,53),(46,49,52)
+----------+----------+----------+ +----------+----------+----------+
| 0 1 2 | 3 4 5 | 6 7 8 | | A . A | . . . | . . . |
| 9 10 11 | 12 13 14 | 15 16 17 | | B . B | . . . | . . . |
| 18 19 20 | 21 22 23 | 24 25 26 | | C . C | . . . | . . . |
+----------+----------+----------+ +----------+----------+----------+
| 27 28 29 | 30 31 32 | x x x | | D . D | . . . | x x x |
| 33 34 35 | 36 37 38 | x x x | | E . E | . . . | x x x |
| 39 40 41 | 42 43 44 | x x x | | F . F | . . . | x x x |
+----------+----------+----------+ +----------+----------+----------+
| 45 46 47 | x x x | x x x | | G H G | x x x | x x x |
| 48 49 50 | x x x | x x x | | G H G | x x x | x x x |
| 51 52 53 | x x x | x x x | | G H G | x x x | x x x |
+----------+----------+----------+ +----------+----------+----------+
8 cycles, 2^8 possible on/off assignments ... 2*2*2*2*2*2*2*2.
For a pattern to satisfy (g x) = x, it is necessary that all of the the cells in each cycle, have the same on/off ("clue/not a clue") status.
Cells that are not in cycles ... "stationary cells" ... can be set to any state.
If we didn't need to worry about limiting clue counts to "<= 8 per box", then for the sample 'g': with 8 cycles and 33 stationary cells, there would be 2^(8+33) = 2199023255552 patterns with (g x) = x.
To enforce the "<= 8 clues per box" limit, we need to enumerate/"loop over" the different ways of assinging on/off status to the cycles, and total up a "pattern count" for each case.
For the sample 'g' (and "<= 8" limit) ... we need to make sure that:
1) The 'G" and H cycles are not both "on" ... or else box 7 would have 9 clues.
2) If cycles A,B and C are all "on", then we have < 3 clues in the statiionary cells in box 1.
3) If cycles D,E and F are all "on", then we have < 3 clues in the statiionary cells in box 4.
4) In boxes 2,3 and 5, we have < 9 clues.
More generally:
1) If the overall cycle on/off state has one or more (".") boxes completely covered by "on"-state cycles, ignore it.
2) If a (".") box has 'n > 0' stationary cells:a) if it overlaps at least one "off" cycle, allow any clue count from 0 to n
b) otherwise, allow only 0 to (n-1) clues.
For the sample 'g', then, if all we needed was the total number of patterns with (g x) = x, we would loop over the (256) cycle states, and add up counts defined as follows:
- 0 -- if G,H are both "on"
- (2^3)*(2^9-1)*(2^9-1)*(2^3)*(2^9-1) -- if at least one cycle is "off" in each of {G,H}, {A,B,C} and {D,E,F}
- (2^3-1)*(2^9-1)*(2^9-1)*(2^3)*(2^9-1) -- if A,B,C are all "on", and at least one is "off" in each of {G,H} and {D,E,F}
- (2^3)*(2^9-1)*(2^9-1)*(2^3-1)*(2^9-1) -- if D,E,F are all "on", and at least one is "off" in each of {G,H} and {A,B,C}
- (2^3-1)*(2^9-1)*(2^9-1)*(2^3-1)*(2^9-1) -- if A-F are all "on", and at least one is "off" in {G,H}
For the end of the story, things get a little more complicated if we want a breakdown of patterns by clue count, N.
For the mathematics end of it, Burnside's lemma applies once to each clue count, but the sums for each N are done in "parallel" -- in a/another set of nested loops, inside the "cycles loop".
The loops are potentially different for each way of assigning "on/off" states to the cell cycles.
Each level of nesting corresponds to a particular pool of cells:
- There's one pool, for the stationary cells in any/all of the "." boxes that overlap an "off" cycle.
That one gets a clue count that loops from 0 to the total number of cells.
(To ensure that at least one loop (level) is present, the "total number of cells" can be zero). - Then there is a pool for each "." box that 1) contains at least 2 stationary cells, and 2) doesn't overlap an "off" cycle.
Those get a clue count that loops from 0 to one less than the number stationary cells in the box.
Inside the loops:
1) A total clue count, N, is calculated, that is the cell count from "on" cycles, plus the clue counts from each loop level.
2) A "patterns" count for that N (and loop itteration) is calculated, that is the product of the "choose(n, cc)" values from each loop level, where 'n' is the pool size, 'cc' is the (looping) clue count, and "choose(n,cc)" is n!/cc!/(n-cc)!, the number of ways to choose 'cc' (clue) cells from a pool of 'n'.
3) (The pattern count is added to an accumulating sum for the particular N).
Something to note: the sum of choose(n,cc) for cc's ranging from 0 to 'n', is 2^n, and the sum from 0 to 'n-1', is (2^n-1).
For the outer loop pool, where 'n' is a sum of stationary cell counts over some set of boxes ... n = n1+n2+...+nk ... and 2^n is (2^n1)*(2^n2)*...*(2^nk).
The 2^ni and (2^n-1) values, are like the values (2^3),(2^3-1) and (2^9-1), from above, for the sample 'g' (and no breakdown by clue count).
I hope that's enough ...
Blue.
