Re: Pattern enumeration. (ugly)

Here is a rather informal presentation of the start of a way to come up with an exact count, at least in theory.

96 Constraints C1..C96
[download]

Divide the space of all possible fillings into 97 buckets:

B0: Legal fillings
B1: Fillings that violate C1
B2: Fillings that don't violate C1 but do viloate C2
B$N: Fillings that don't violate C1..C$N but do violate C$N

Fill the grid, counting the possibilities until you get to a point when it becomes possible to determine if a constraint has been violated. At this point, you must split the building total into two: Those that violate the next constraint and those that don't. You take the first number and multiple it by 6**(number of unfilled locations) and that is the total value for B$N. The second "number" is used to continue calculations, filling in more buckets.

Start with 6**64. You can trivially calculate and subtract B1 to get much closer to the number of legal fillings. A little bit more work lets you subtract B2 to get a little closer. After a lot of work, you can subtract B6. Each subsequent bucket size calculation gets several-fold more complex to calculate but also gets less significant. Perhaps you get to a point where you are close enough or just extrapolate an approximation from the patterns you start to observe.

Anyway, I track the exact calculations as a list of products. Sum up all of the products (except the first one) and if they don't equal the first product, then you made a mistake somewhere.

Start with an obvious choise of C1..C6 being the constraints that apply to the first row.

Look at ways to fill just the first 3 locations:

6,6,6 = 6*36 all possible ways<br />
6,1,1 = 6*1  ways to violate C1<br />
      = 6*35 ways to not violate C1 (via subtraction)<br />
[download]

B1 = 6 * 6**(64-3)
[download]

But it gets more complicated than that in the next step so we preplan for dealing with C2:

6,6,6 = 6*36 = T3   = all possible ways to fill first 3 locations
6,1,1 = 6*1  = B1,3 = ways to violate C1 (after filling 3 locations)
6,5,1 = 6*5  = B2,3 = ways to not violate C1 but might violate C2
      = 6*30 = B0,3 = ways to not violate C1 nor C2 (via subtraction)
[download]

Now expand this to cover the first 4 locations:

6,6,6,6 = T4   = all possible ways to fill first 4 locations
6,1,1,6 = B1,4 = ways to violate C1 (after 4 locations)
6,5,1,1 = B2,4 = ways to violate C2 (but not C1)
          B3,4 = ways to maybe violate C3, never C1..C2
6,5,5,1 + A,B,C,C (maybe C = A)
6,1,5,1 + A,A,B,B
          B0,4 = T4 - B(1..3),4
          Let's enumerate these so we can check our work:
6,1,5,5 + A,A,B,C (maybe C = A)
6,5,1,5 + A,B,B,C
6,5,5,5 + A,B,C,D
[download]

B2 = 6*5*1*1 * 6**(64-4)
[download]

The items under B3,4 get expanded under B3,5 in one way and under B0,5 another way. The items under B0,4 get expanded under B4,5 in one way and under B0,5 another way:

6,6,6,6,6 = T5   = all possible ways to fill first 5 locations
6,1,1,6,6 = B1,5 = ways to violate C1
6,5,1,1,6 = B2,5 = ways to violate C2 (but not C1)
            B3,5 = ways to violate C3 (not C1 nor C2)
6,5,5,1,1 + A,B,C,C,C (maybe C = A)
6,1,5,1,1 + A,A,B,B,B
            B4,5 = ways to maybe violate only C4
6,1,5,5,1 + A,A,B,C,C (maybe A=C)
6,5,1,5,1 + A,B,B,C,C (maybe A=C)
6,5,5,5,1 + A,B,C,D,D (maybe A=C, A=D, or B=D)
            B0,5 = T5 - B(1..4),5
6,5,5,1,5 + A,B,C,C,D (A!=B && B!=C && C!=D)
6,1,5,1,5 + A,A,B,B,C
6,1,5,5,5 + A,A,B,C,D
6,5,1,5,5 + A,B,B,C,D
6,5,5,5,5 + A,B,C,D,E
[download]

B3 = ( 6*5*5 + 6*5 ) * 6**(64-5)
[download]

6,6,6,6,6,6 = T6   = all possible ways to fill first 5 locations
6,1,1,6,6,6 = B1,6 = ways to violate C1
6,5,1,1,6,6 = B2,6 = ways to violate C2 (but not C1)
              B3,6 = ways to violate C3 first
6,5,5,1,1,6 + A,B,C,C,C
6,1,5,1,1,6 + A,A,B,B,B
              B4,6 = ways to violate C4 first
6,1,5,5,1,1 + A,A,B,C,C,C
6,5,1,5,1,1 + A,B,B,C,C,C
6,5,5,5,1,1 + A,B,C,D,D,D
              B5,6 = ways to maybe violate only C5
6,5,5,1,5,1 + A,B,C,C,D,D
6,1,5,1,5,1 + A,A,B,B,C,C
6,1,5,5,5,1 + A,A,B,C,D,D
6,5,1,5,5,1 + A,B,B,C,D,D
6,5,5,5,5,1 + A,B,C,D,E,E
              B0,6 = T6 - B(1..5),6
6,1,5,5,1,5 + A,A,B,C,C,D
6,5,1,5,1,5 + A,B,B,C,C,D
6,5,5,5,1,5 + A,B,C,D,D,E
6,5,5,1,5,5 + A,B,C,C,D,E
6,1,5,1,5,5 + A,A,B,B,C,D
6,1,5,5,5,5 + A,A,B,C,D,E
6,5,1,5,5,5 + A,B,B,C,D,E
6,5,5,5,5,5 + A,B,C,D,E,F
[download]

B4 = ( 6*5*5*5 + 2*6*5*5 ) * 6**(64-6)
[download]

6,6,6,6,6,6,6 = T7   = all possible ways to fill first 5 locations
6,1,1,6,6,6,6 = B1,7 = ways to violate C1
...
                B5,7 = ways to violate C5 first
6,5,5,1,5,1,1 + A,B,C,C,D,D,D
6,1,5,1,5,1,1 + A,A,B,B,C,C,C
6,1,5,5,5,1,1 + A,A,B,C,D,D,D
6,5,1,5,5,1,1 + A,B,B,C,D,D,D
6,5,5,5,5,1,1 + A,B,C,D,E,E,E
                B6,7 = ways to maybe violate C6 first
6,1,5,5,1,5,1 + A,A,B,C,C,D,D
6,5,1,5,1,5,1 + A,B,B,C,C,D,D
6,5,5,5,1,5,1 + A,B,C,D,D,E,E
6,5,5,1,5,5,1 + A,B,C,C,D,E,E
6,1,5,1,5,5,1 + A,A,B,B,C,D,D
6,1,5,5,5,5,1 + A,A,B,C,D,E,E
6,5,1,5,5,5,1 + A,B,B,C,D,E,E
6,5,5,5,5,5,1 + A,B,C,D,E,F,F
                B0,7
6,5,5,1,5,1,5 + A,B,C,C,D,D,E
6,1,5,1,5,1,5 + A,A,B,B,C,C,D
6,1,5,5,5,1,5 + A,A,B,C,D,D,E
6,5,1,5,5,1,5 + A,B,B,C,D,D,E
6,5,5,5,5,1,5 + A,B,C,D,E,E,F
6,1,5,5,1,5,5 + A,A,B,C,C,D,E
6,5,1,5,1,5,5 + A,B,B,C,C,D,E
6,5,5,5,1,5,5 + A,B,C,D,D,E,F
6,5,5,1,5,5,5 + A,B,C,C,D,E,F
6,1,5,1,5,5,5 + A,A,B,B,C,D,E
6,1,5,5,5,5,5 + A,A,B,C,D,E,F
6,5,1,5,5,5,5 + A,B,B,C,D,E,F
6,5,5,5,5,5,5 + A,B,C,D,E,F,G
[download]

B5 = ( 6*5*5 + 3*6*5*5*5 + 6*5**4 ) * 6**(64-7)
[download]

6,6,6,6,6,6,6,6 = T8   = all possible ways to fill first 5 locations
6,1,1,6,6,6,6,6 = B1,8 = ways to violate C1
...
                  B6,8 = ways to violate C6 first
6,1,5,5,1,5,1,1 + A,A,B,C,C,D,D,D
6,5,1,5,1,5,1,1 + A,B,B,C,C,D,D,D
6,5,5,5,1,5,1,1 + A,B,C,D,D,E,E,E
6,5,5,1,5,5,1,1 + A,B,C,C,D,E,E,E
6,1,5,1,5,5,1,1 + A,A,B,B,C,D,D,D
6,1,5,5,5,5,1,1 + A,A,B,C,D,E,E,E
6,5,1,5,5,5,1,1 + A,B,B,C,D,E,E,E
6,5,5,5,5,5,1,1 + A,B,C,D,E,F,F,F
                  B0,8 = ways to not violate constraints in a row
6,1,5,5,1,5,1,5 + A,A,B,C,C,D,D,E
6,5,1,5,1,5,1,5 + A,B,B,C,C,D,D,E
6,5,5,5,1,5,1,5 + A,B,C,D,D,E,E,F
6,5,5,1,5,5,1,5 + A,B,C,C,D,E,E,F
6,1,5,1,5,5,1,5 + A,A,B,B,C,D,D,E
6,1,5,5,5,5,1,5 + A,A,B,C,D,E,E,F
6,5,1,5,5,5,1,5 + A,B,B,C,D,E,E,F
6,5,5,5,5,5,1,5 + A,B,C,D,E,F,F,G
6,5,5,1,5,1,5,6 + A,B,C,C,D,D,E,*
6,1,5,1,5,1,5,6 + A,A,B,B,C,C,D,*
6,1,5,5,5,1,5,6 + A,A,B,C,D,D,E,*
6,5,1,5,5,1,5,6 + A,B,B,C,D,D,E,*
6,5,5,5,5,1,5,6 + A,B,C,D,E,E,F,*
6,1,5,5,1,5,5,6 + A,A,B,C,C,D,E,*
6,5,1,5,1,5,5,6 + A,B,B,C,C,D,E,*
6,5,5,5,1,5,5,6 + A,B,C,D,D,E,F,*
6,5,5,1,5,5,5,6 + A,B,C,C,D,E,F,*
6,1,5,1,5,5,5,6 + A,A,B,B,C,D,E,*
6,1,5,5,5,5,5,6 + A,A,B,C,D,E,F,*
6,5,1,5,5,5,5,6 + A,B,B,C,D,E,F,*
6,5,5,5,5,5,5,6 + A,B,C,D,E,F,G,*
[download]

B6 = ( 3 + 4*5 + 5**2 ) 5**3 * 6**(64-7)
[download]

Which gives us:

B1 = 6**(64-2)
B2 = 5*6**(64-3)
B3 = ( 5 + 1 ) * 5 * 6**(64-4)
B4 = ( 5 + 2 ) * 5**2 * 6**(64-5)
B5 = ( 1 + 3*5 + 5**2 ) * 5**2 * 6**(64-6)
B6 = ( 3 + 4*5 + 5**2 ) * 5**3 * 6**(64-7)
[download]

Which shows that the values to be subtracted don't decrease in size very fast at all so far:

1.75945240730481e48
1.46621033942068e48
1.46621033942068e48
1.42548227443677e48
1.39154222028351e48
1.35760216613026e48
[download]

Our approximations at B0 aren't converging very fast:

B0 < 6.33402866629733e49
B0 < 6.15808342556685e49
B0 < 6.01146239162478e49
B0 < 5.86484135768271e49
B0 < 5.72229313023903e49
B0 < 5.58313890821068e49
B0 < 5.44737869159766e49
[download]

Which means that the number of boards that don't violate any horizontal contraints is:

1444500 ** 8
  or
1.8955723685859e49
[download]

Yes, of course there are patterns in the above work that can be generized or you can write code to get to this point after you've seen how each step goes. But, trying to deal with the vertical constraints make the previous work look down-right simple by comparison! So any generalizations from the above work would likely have to be thrown away in our next phase anyway.

Although there are nearly 2e49 boards to search through, we represent about 1.4e6 of those with just 21 short products. So, by the time we have 8 rows, we might have somewhere remotely close to 21**8 products to keep track of. 37,822,859,361 arrays is not going be something most computers will easily handle. But that at least might be possible versus trying to enumerate 2e49 possibilities.

Probably best to drop the "A,A,B,C,C,D" notation in favor of two characters per cell chosen from:

'<' for "this loc has the same value as the loc to the left"
']' for "this loc has a value different from the loc to the left"
'|' for "no value to left or no constraint vs it"
'^' for "this loc has the same value as the loc above"
'u' for "this loc has a value different from the loc above"
'-' for "no value above or no constraint vs it"

Using '<' or '^' means that a 1 will go in the corresponding spot in the product. '|-' means a 6 goes in. ']-' or '|u' means a 5 goes in. ']u' means either 4 or 5 goes in, depending on whether the loc above is '<' or ']' (if the loc above is '|', then you need to split the case into two separate products).

The list of products for a single row now look like this:

6,1,5,5,1,5,1,5 + |,<,],],<,],<,]
6,5,1,5,1,5,1,5 + |,],<,],<,],<,]
6,5,5,5,1,5,1,5 + |,],],],<,],<,]
6,5,5,1,5,5,1,5 + |,],],<,],],<,]
6,1,5,1,5,5,1,5 + |,<,],<,],],<,]
6,1,5,5,5,5,1,5 + |,<,],],],],<,]
6,5,1,5,5,5,1,5 + |,],<,],],],<,]
6,5,5,5,5,5,1,5 + |,],],],],],],]
6,5,5,1,5,1,5,6 + |,],],<,],<,],|
6,1,5,1,5,1,5,6 + |,<,],<,],<,],|
6,1,5,5,5,1,5,6 + |,<,],],],<,],|
6,5,1,5,5,1,5,6 + |,],<,],],<,],|
6,5,5,5,5,1,5,6 + |,],],],],<,],|
6,1,5,5,1,5,5,6 + |,<,],],<,],],|
6,5,1,5,1,5,5,6 + |,],<,],<,],],|
6,5,5,5,1,5,5,6 + |,],],],<,],],|
6,5,5,1,5,5,5,6 + |,],],<,],],],|
6,1,5,1,5,5,5,6 + |,<,],<,],],],|
6,1,5,5,5,5,5,6 + |,<,],],],],],|
6,5,1,5,5,5,5,6 + |,],<,],],],],|
6,5,5,5,5,5,5,6 + |,],],],],],],|
[download]

We can sort the above items better. Note that the pattern is that we can't have two 1s adjacent and each row ends in either 5,6 or 1,5:

5**6: (not counting the two end values)
6,5,5,5,5,5,5,6 + |,],],],],],],|
5**5:
6,1,5,5,5,5,5,6 + |,<,],],],],],|
6,5,1,5,5,5,5,6 + |,],<,],],],],|
6,5,5,1,5,5,5,6 + |,],],<,],],],|
6,5,5,5,1,5,5,6 + |,],],],<,],],|
6,5,5,5,5,1,5,6 + |,],],],],<,],|
6,5,5,5,5,5,1,5 + |,],],],],],],]
5**4:
6,1,5,1,5,5,5,6 + |,<,],<,],],],|
6,1,5,5,1,5,5,6 + |,<,],],<,],],|
6,1,5,5,5,1,5,6 + |,<,],],],<,],|
6,1,5,5,5,5,1,5 + |,<,],],],],<,]
6,5,1,5,1,5,5,6 + |,],<,],<,],],|
6,5,1,5,5,1,5,6 + |,],<,],],<,],|
6,5,1,5,5,5,1,5 + |,],<,],],],<,]
6,5,5,1,5,1,5,6 + |,],],<,],<,],|
6,5,5,1,5,5,1,5 + |,],],<,],],<,]
6,5,5,5,1,5,1,5 + |,],],],<,],<,]
5**3:
6,1,5,1,5,1,5,6 + |,<,],<,],<,],|
6,1,5,1,5,5,1,5 + |,<,],<,],],<,]
6,1,5,5,1,5,1,5 + |,<,],],<,],<,]
6,5,1,5,1,5,1,5 + |,],<,],<,],<,]
[download]

Let's add the next location, separating between "might violate first vertical constraint" from "can't violate first vertical constraint":

6,5,5,5,5,5,5,6;1 + |,],],],],],],|;|^
6,1,5,5,5,5,5,6;1 + |,<,],],],],],|;|^
6,5,1,5,5,5,5,6;1 + |,],<,],],],],|;|^
6,5,5,1,5,5,5,6;1 + |,],],<,],],],|;|^
6,5,5,5,1,5,5,6;1 + |,],],],<,],],|;|^
6,5,5,5,5,1,5,6;1 + |,],],],],<,],|;|^
6,5,5,5,5,5,1,5;1 + |,],],],],],],];|^
6,1,5,1,5,5,5,6;1 + |,<,],<,],],],|;|^
6,1,5,5,1,5,5,6;1 + |,<,],],<,],],|;|^
6,1,5,5,5,1,5,6;1 + |,<,],],],<,],|;|^
6,1,5,5,5,5,1,5;1 + |,<,],],],],<,];|^
6,5,1,5,1,5,5,6;1 + |,],<,],<,],],|;|^
6,5,1,5,5,1,5,6;1 + |,],<,],],<,],|;|^
6,5,1,5,5,5,1,5;1 + |,],<,],],],<,];|^
6,5,5,1,5,1,5,6;1 + |,],],<,],<,],|;|^
6,5,5,1,5,5,1,5;1 + |,],],<,],],<,];|^
6,5,5,5,1,5,1,5;1 + |,],],],<,],<,];|^
6,1,5,1,5,1,5,6;1 + |,<,],<,],<,],|;|^
6,1,5,1,5,5,1,5;1 + |,<,],<,],],<,];|^
6,1,5,5,1,5,1,5;1 + |,<,],],<,],<,];|^
6,5,1,5,1,5,1,5;1 + |,],<,],<,],<,];|^

6,5,5,5,5,5,5,6;5 + |,],],],],],],|;|u
6,1,5,5,5,5,5,6;5 + |,<,],],],],],|;|u
6,5,1,5,5,5,5,6;5 + |,],<,],],],],|;|u
6,5,5,1,5,5,5,6;5 + |,],],<,],],],|;|u
6,5,5,5,1,5,5,6;5 + |,],],],<,],],|;|u
6,5,5,5,5,1,5,6;5 + |,],],],],<,],|;|u
6,5,5,5,5,5,1,5;5 + |,],],],],],],];|u
6,1,5,1,5,5,5,6;5 + |,<,],<,],],],|;|u
6,1,5,5,1,5,5,6;5 + |,<,],],<,],],|;|u
6,1,5,5,5,1,5,6;5 + |,<,],],],<,],|;|u
6,1,5,5,5,5,1,5;5 + |,<,],],],],<,];|u
6,5,1,5,1,5,5,6;5 + |,],<,],<,],],|;|u
6,5,1,5,5,1,5,6;5 + |,],<,],],<,],|;|u
6,5,1,5,5,5,1,5;5 + |,],<,],],],<,];|u
6,5,5,1,5,1,5,6;5 + |,],],<,],<,],|;|u
6,5,5,1,5,5,1,5;5 + |,],],<,],],<,];|u
6,5,5,5,1,5,1,5;5 + |,],],],<,],<,];|u
6,1,5,1,5,1,5,6;5 + |,<,],<,],<,],|;|u
6,1,5,1,5,5,1,5;5 + |,<,],<,],],<,];|u
6,1,5,5,1,5,1,5;5 + |,<,],],<,],<,];|u
6,5,1,5,1,5,1,5;5 + |,],<,],<,],<,];|u
[download]

Then the real fun begins after you decide whether to fill in the next item to the right or below. Note that you can re-use your list of 21 products in order to compute for a whole extra row in one sitting, now. But that is no small task.

Let's just quickly look at trying to append our last product to itself:

Might violate VC1:
6,5,1,5,1,5,1,5;1,...     + |,],<,],<,],<,];|^,] ,<,],<,],<,]

Can't violate VC1, but maybe VC2:
6,5,1,5,1,5,1,5;5,?,...   + |,],<,],<,],<,];|u,]^,<,],<,],<,]
[download]

Oops, we have to split that second case above into two cases already:

A B ...
C D ...
6,5,...;5,4,...

vs

A B ...
B C ...
6,5,...;1,5,...
[download]

Lots of fun.

Updated, very shortly after posting to replace a couple of wildly wrong calculations and to make one minor wording tweak.

- tye

Comment on Re: Pattern enumeration. (ugly) Select or Download Code