BrowserUk:

To enumerate the series, I think I'd use an approach of treating the board as a vector of 64 symbols^[1], set to an arbitrary legal pattern. Then each time you want the next board, advance the first position, advancing the next digit each time the current digit rolls over. The advance code would skip a symbol if the next two positions in the row use that symbol. Similarly, it would skip the symbol if the next two column positions already contain that symbol.

As for computing it mathmatically, I think I'd approach it by computing the number of all possible boards (without the constraints), i.e. 6^64. Then, I'd subtract out all illegal boards I could: 2*48*6*6^61. The 6^61 is the number of boards for each case of 3-in-a-row, the 6 is the number of symbols, 48 being the number of positions you can start a 3-in-a-row, and 2 for symmetry for the 3-in-a-column case. So, unless I've missed something, I think the number of boards is: 6^64 - 2*48*6*6^61.^[2]

Notes:

[1] To simplify the position checking logic, I'd actually make it a larger vector so I can create a border (two wide) on the right and bottom of the board. The border would hold an invalid symbol to make the symbol checking simple. Thus, you could disallow a symbol if:

if ( $sym ne $brd[$pos+1] or $sym ne $brd[pos+2] or
     $sym ne $brd[$pos+11] or $sym ne $brd[pos+22] ) {
   # symbol is legal in this position
}
else {
   # symbol is illegal in this position, try next symbol
}
[download]

[2] After further reflection, I find I'm counting excluded boards multiple times, because there will be boards with multiple rows/columns-of-three. I'll give it another minute or two to see if I can refine it a bit. But I think that at least that would give you a lower bound on the number of boards...

...roboticus

Update: I moved the last paragraph up before the Notes section, where it was supposed to be.

Update 2: Added note [2]

Update 3: Gah! I had my exponents consistently backwards (64^6 instead of 6^64).

Update 4: Struck out the totally useless paragraph. In this case, a back-of-the-envelope estimate should have remained on the envelope!

Sorry, but your calculation is significantly too simple. An illegal board can fail more than just one constraint. Your 2*48*6*6**61 enumerates the possible paths for a simple algorithm that is guaranteed to produce an illegal board. But a huge number of those paths are just different ways of generating the same board (if a board violates 6 different constraints, then your equation will count that board 6 different times).

So you have over estimated the number of illegal boards rather significantly. This is rather easy to see by noting that your estimated number of legal boards comes out to -360*6**61. A negative number of possibilities is clearly the wrong answer.

I've computed counts for similar sets in the past. It gets very complicated very quickly. I'll try to write up at least the first part of such a calculation but I doubt I'll be posting that very soon. :)

You could get an approximate answer by generating a large number of boards at random and calculating the average number of constraints violated by a random illegal board and then using that number to divide the number you originally calculated.

- tye        

You could get an approximate answer by generating a large number of boards at random

Generating random boards and then just checking for pass/fail very quickly converges to a figure of 8.9%; giving a approximation of 5.657e+48 legal boards.

I don't understand your "calculating the average number of constraints violated by a random illegal board" bit.

I do realise that for any given legal board, there are 720 "symmetries", where the arrangement of tokens is the same, but the actual tokens are different. Um. Not a good description.

Ie. The following are symmetries because the pattern of the tokens remains the same, though the values of the tokens are different:

1 2 3    2 3 1    3 2 1
2 3 1    3 1 2    2 1 3            
3 2 1    1 3 2    1 2 3
[download]

For my purpose, reflection and rotational symmetries are different.

So, I think that once I've calculated the total number of legal arrangements, I divide by 720 to determine the number of patterns?

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

RIP an inspiration; A true Folk's Guy

tye:

I see what you mean by "It gets very complicated very quickly". I tried to make a new calculation for the number of legal boards, and quickly got bogged down while trying to make sure I didn't count boards multiple times.

After working on the problem for a while, I can confidently state the following: I can't afford the amount of coffee, scratch paper, erasers and pencils required for me to figure it out!

...roboticus

Hm.

2 * 48 * 6 * 6^61 = 1.6890743110126207388309943185817e+50

6^64 = 6.3340286662973277706162286946812e+49

Subtracting the former from the latter is -1.0556714443828879617693714491129e+50?

What I think I have:

Take one row; ignoring the vertical component for the moment, at each iteration:

1. the first cell has a choice of 6;
2. the second also has a choice of 6;
3. the third cell has:
   • a choice of 6

     unless the two preceding cells are the same, which happens 6/36 times

   • when it has a choice of 5

   for an average choice of 5.8333

4. This figure is true for the other five cells in the row.

Giving ( 6 * 6 * 5.833333333^6 ) ^ 8 = 2.220030530726145590197494583735e+47

However, for the 3rd and subsequent rows, the choice at each position is further constrained by the existing values for the previous two cells in the column.

For the first two columns, 30/36 the choice will be 6; 6/36 it will be 5 giving the familiar 5.8333 average. But for the 3rd and subsequent columns, it gets messy.

I thought that it might be :

28.1944 / 5.8333^2 choice is 6; 5.83333 / 5.8333^2 choice is 5; giving an average of: 5.82857142

For each of the 6x6 cells in the bottom right.

For an overall calculation of:

( 6**2 * 5.833333333333333333333333333333**6 )**2 *

( ( 5.833333333333333333333333333333**2 * 5.8285714285714285714285714285714**6 )**6 )

= 1.13460446277538e+049

But that doesn't make sense because it is bigger than the previous result constrained in only one direction :(.

In either case, it is far to big a number to actually iterate.

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

RIP an inspiration; A true Folk's Guy

This is similar to the classic "knight moves" chess problem.

I'd suggest a single-dimension array with 8 elements.
Each element has 8 bits of content, which represents a column of data.

With this structure, the problem reduces to identifying rules to generate legal adjacent bit patters.

It's late in my day - brain too fried to attempt that now - I'm sure wiser, more alert monks will oblige.

Cheers.

Update:Sigh .. - it is even later in the night, but I'm bothered because the representation above is not right.
The values 0..5 can represent your 6 choices - these can fit into 3 bits. Times 8 gives you 24 bits.

So, a single dim array, where each element holds 24 bits can represent your problem.

If you shift items in sequences of 6 bits, you can identify legal vertical patterns. The same rules can apply to adjacent indexes masking out the right bits.

Brain still to fried to conceptualize the actual patterns.

The number of patterns if phenomenal.
With a 3x3 with at most 3 symbols, there are 9,750 solutions.
With a 3x3 with at most 4 symbols, there are 178,068 solutions.
With a 4x4 with at most 3 symbols, there are 8,484,138 solutions

Here's a trivial solution for 8x8 with at most 6 symbols:

AABAABAA
AABAABAA
BBABBABB
AABAABAA
AABAABAA
BBABBABB
AABAABAA
AABAABAA
[download]

I'm using the regex engine to generate solutions for speed:

use strict;
use warnings;

#
# Two types of operation:
#
# - Pick a symbol:
#   '<ABC>' =~ /<[A-C]*([A-C])[A-C]*>/
#
# - Constraint check:
#   '<AB,AC,BA,BC,CA,CB,AAB,AAC,BBA,BCC,CCA,CCB>' =~ /<(?:[A-C]*,)*\x\
+y\z?(?:,[A-C]*)*>/
#


sub allowed {
   my ($syms) = @_;
   my @combos;
   for    my $y (@$syms) {
      for my $x (@$syms) {
         next if $x eq $y; 
         push @combos, "$y$x";
         push @combos, "$y$y$x";
      }
   }
   return @combos;
}


{
   my $solve       = shift || "count_solutions";  # first_solution, al
+l_solutions, count_solutions
   my $grid_size   = shift || 8;
   my $num_symbols = shift || 6;

   my @syms = ('A'..'Z')[0..$num_symbols-1];

   my $syms_list  = join('', reverse(@syms));
   my $syms_class = "[" . $syms[0] . "-" . $syms[-1] . "]";

   my $pick_str = "<$syms_list>";
   my $pick_pat = "<$syms_class*($syms_class)$syms_class*>";

   my $constr_str = "<" . join(',',allowed(\@syms)) . ">";
   my $constr_pat_gen = sub { "<(?:$syms_class*,)*\\$_[0]\\$_[1]\\$_[2
+]?(?:,$syms_class*)*>" };

   my $str = '';
   my $pat = '';

   for    my $y (0..$grid_size-1) {
      for my $x (0..$grid_size-1) {
         $str .= $pick_str;
         $pat .= $pick_pat;

         my $z = $y * $grid_size + $x + 1;

         if ($x >= 2) {
            $str .= $constr_str;
            $pat .= $constr_pat_gen->($z, $z-1, $z-2);
         }

         if ($y >= 2) {
            $str .= $constr_str;
            $pat .= $constr_pat_gen->($z, $z-1*$grid_size, $z-2*$grid_
+size);
         }
      }
   }

   #print("$str\n");
   #print("$pat\n");

   if ($solve eq "first_solution") {
      my (@sol) = $str =~ /^$pat\z/
         or die("No solution");

      for    my $y (0..$grid_size-1) {
         for my $x (0..$grid_size-1) {
            print($sol[$y * $grid_size + $x]);
         }
         print("\n");
      }
   }
   elsif ($solve eq "all_solutions") {
      use re 'eval';
      local our $count = 0;
      $str =~ /^$pat\z(?{
         ++$count;
         for    my $y (0..$grid_size-1) {
            for my $x (0..$grid_size-1) {
               no strict 'refs';
               print(${ $y * $grid_size + $x + 1 });
            }
            print("\n");
         }
         print("\n");
      })(?!)/;
      print("$count solutions\n");
   }
   elsif ($solve eq "count_solutions") {
      use re 'eval';
      local our $count = 0;
      $str =~ /^$pat\z(?{ ++$count; print "$count\n" if $count % 10000
+ == 0; })(?!)/;
      print("$count solutions\n");
   }
   else {
      die("Bad value for \$solve\n");
   }
}
[download]

Update: I thought

   F
   FF
[download]

I'm using the regex engine to generate solutions for speed:

Hm.

c:\test>851581.pl
10000 1280263403
20000 1280263405
30000 1280263407
40000 1280263410
50000 1280263412
60000 1280263414
70000 1280263416
80000 1280263418
90000 1280263420
100000 1280263423
110000 1280263425
120000 1280263427
130000 1280263429
140000 1280263431
Terminating on signal SIGINT(2)
[download]

I read that as 230 microseconds per iteration. Not sure if that is generated or tested good, but even if the latter; and assuming a (way) underestimate of 5^64; then 3 779 192 301 486 978 976 247 237 055 279 666 years.

I don't think that throwing threads, or even a google, at it will help any :) Maybe a few giant red spots.

I started playing with a recursive solution that builds grids from smaller grids. Bonus: This method naturally omits permutations.

For example, given

2x2, 2 syms:

AA  AB  AB
BB  AB  BA
[download]

One can overlap the 2x2 grids to form:

3x3, 2 syms:

13    22    31    33    33
13    33    31    22    33

AAB   ABA   ABB   ABA   ABA
BBA   ABA   BAA   BAB   BAB
AAB   BAB   ABB   BAB   ABA
[download]

I think it might be possible to turn this into an efficient solution for counting the arrangements instead of generating them.

That's all I had time to do for now.

Update: At time of writing, I thought

F
FF
[download]

wasn't allowed. The concept still applies, although there would be a lot more possible grids.

Mathworld has something to say about the number of coloured graphs where no two colours may be adjacent (which is more restrictive than your problem). It suggest that using brute force to calculate the answer to your problem isn't viable.

No, what you write is not the same problem I think. The original question only bans three adjacent cells of the same color in a row or a column, not L-shaped.

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]

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:

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":

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.

(I believe) Its complexity is O(N²2^NS^2N) where NxN is the grid size and S the number of symbols, so extrapolating, it should be able to solve the 8x8,6 case in 5000 13000 minutes, that's 9 days, probably in 4 or even 2 in a fast computer (mine isn't).

Note that I had to use multi-precision arithmetic in order to store the pattern counters and that the results are printed in hexadecimal.

Discovering the logic behind is left as an exercise to the reader ;-)

Update: Complexity and time estimations corrected. Result for 7x7,6 included.

It can solve the 6x6 case, with 6 symbols in two minutes in my computer.... it should be able to solve the 8x8,6 case in 5000 minutes,

Um. 6x6x6 is 6^36; 8x8x6 is 6^64. 6^64 / 6^36 = 6140942214464815497216 *2 minutes = A very long time :)

Discovering the logic behind is left as an exercise to the reader ;-)

Of course, maybe it is a non-linear algorithm. But it will take me a while to discover the logic :)

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

RIP an inspiration; A true Folk's Guy

Um. 6x6x6 is 6^36; 8x8x6 is 6^64. 6^64 / 6^36 = 6140942214464815497216 *2 minutes = A very long time :)

That would be true if I had used the brute force algorithm that has complexity O(S^N2) or worse... but I had not used it!

My solution has complexity O(N²S^2N) so, roughly, t_6x6,6 = k*6²*6^2*6 = 2min, so k = 2/78364164096 and t_8x8,6 = k*8²*6^2*8 = 180551034077184*2/78364164096 = 4608min

My solution has complexity O(N²2^NS^2N) so, roughly, t_7x7,6 = k*7²*2⁷*6^2*7 = 139min, so k = 139/A and t_8x8,6 = k*8²*6^2*8 = 180551034077184*139/A = 13000min

I guess there must be a way to calculate this precisely in a reasonable time, but if you only want an approximate answer, that's much easier. Just use sampling.

I made the computer fill the board with random letters 10_000_000 times, and 896_728 out of those were correct (no three adjacent letters in a row or column). As there are 6.33e49 possible boards, this means there are approximately 5.68e48 correct boards.

Beat ya to it! :)

The problem is, it converges very slowly. After 1 billion trials, it has still only rendered (at most) 5 significant digits. And plus or minus 1 place in that 5th digit is still a stunningly large margin of error:

[0] Perl> $t = 6**64;;
[0] Perl> $a = $t * 0.08972;;
[0] Perl> $b = $t * 0.08973;;
[0] Perl> print $b - $a;;
6.33402866630814e+044
[download]

Another problem is that 1 billion (or even 1 trillion) trials is such a minuscule sample that I'm not at all convinced that even those 5 digits are accurate. That figure is produced using Perl's built-in rand, which on my platform equates to MSC's hopelessly inadequate 15-bit linear congruential generator, with its known cyclic flaws.

I substituted Math::Random::MT and got substantially different results, but the MT, whilst a vastly better PRNG, is really very slow by comparison. Generating and testing an adaquate sample, say a quadrillion, would take a very long time also.

Luckily, salva came to the rescue with a very clever piece of C code that with luck will render an exact answer within the next 10 or so hours.

I'm also convinced that it can be done (very quickly) using purely numerical methods. Though it is considerably more complicated than I first thought. I just found a ridiculous typo(*) that had been hanging me up for two days. Maybe I'll make some progress now.

(*)I have variables $x_1, $x_2, $y_1, $y_2 to represent the values 1 and 2 to the left; and 1 & 2 above the current position. I thought they were vaguely mnemonic for X-1 etc.

Trouble is, in one place I typed $x-1 instead of $x_1 by accident, and whilst nothing appeared broken, the results were rubbish. I must have looked right past that typo a hundred times without spotting it!

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

RIP an inspiration; A true Folk's Guy

Sure. It's a binomial distribution with probability of an individual board being good around 0.09, so the divergence of the ratio of good boards you get from n samples is around 0.3/sqrt(n), which is about 9e-6 for n=1e9, so you should expect only four correct significant digits.