in reply to Pattern enumeration.

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]
wasn't allowed. Fixed.

Replies are listed 'Best First'.
Re^2: Pattern enumeration.
by BrowserUk (Patriarch) on Jul 27, 2010 at 20:59 UTC
    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.

[reply]
[d/l]

      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.
[reply]
[d/l]
[select]

        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]

In Section Seekers of Perl Wisdom