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!

In reply to Re: Pattern enumeration. by roboticus
in thread Pattern enumeration. by BrowserUk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.