in reply to Re^2: Pattern enumeration.
in thread Pattern enumeration.

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.

Replies are listed 'Best First'.
Re^4: Pattern enumeration.
by BrowserUk (Patriarch) on Jul 27, 2010 at 22:25 UTC

    That's an interesting approach. I still doubt it will complete in the life of the universe though.

    This is my random generator/validator for approximating the percentage of valid patterns. It is 3.5 times faster than your original, but still if all the clouds in all the world, (a veritable storm), ran this and nothing else it would still take longer than the life of the universe to date. 

    #! perl -slw
use strict;
#use Math::Random::MT qw[ rand ];

$|++;

our $I //= 1e6;

my( $tried, $good );

for ( 1 .. $I ) {
    ++$tried;
    my @b = map int( rand 6 ), 1 .. 64;
    $good += checkBoard( \@b );
#    displayBoard( \@b ); print "$good of $tried"; <STDIN>;
    printf "\r%10u %18.15f ", $tried, $good / $tried unless $tried % 1
+0000;
}


sub checkBoard {
    my $ref = shift;
    for(
        [0..7],[8..15],[16..23],[24..31],[32..39],[40..47],[48..55],[5
+6..63],
        [ 0, 8,16,24,32,40,48,56],
        [ 1, 9,17,25,33,41,49,57],
        [ 2,10,18,26,34,42,50,58],
        [ 3,11,19,27,35,43,51,59],
        [ 4,12,20,28,36,44,52,60],
        [ 5,13,21,29,37,45,53,61],
        [ 6,14,22,30,38,46,54,62],
        [ 7,15,23,31,39,47,55,63],
    ) {
        my $n = 0;
        join( '', @{$ref}[ @$_ ] ) =~ m[(.)\1\1] and return 0;
    }
    return 1
}
sub displayBoard {
    print for unpack '(A16)*', join ' ', @{ $_[ 0 ] }
}

    [download]

    I *think* I now know how to write a program to generate a calculation that will produce the count. Your original program will be useful for testing the calculation against (much) smaller test cases. If it gets close for them, and results in a percentage of the 6^64 possibilities of 8.972% (approximation from 100 million trials), then it will be reasonable to assume the calculation is um...reasonable :)

[reply]
[d/l]
      I don't get your checkBoard function. It seems to only check if there aren't 3 equal numbers on a single row or column. There doesn't seem to be a check for 3 equal numbers at "an angle". Or am I missing something?
[reply]

        If you check the OP, I'm only concerned with horizontal and vertical adjacencies.

        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.
[reply]

In Section Seekers of Perl Wisdom