in reply to Pattern enumeration.

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!

Replies are listed 'Best First'.
Re^2: Pattern enumeration. (KISS)
by tye (Sage) on Jul 27, 2010 at 07:52 UTC

    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        

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

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

        A 3x3 with 4 symbols has 95,340178,068 solutions, a number that's not even divisible by 4!. This is because some solutions don't use all the available symbols.

[reply]

      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

[reply]
Re^2: Pattern enumeration.
by BrowserUk (Patriarch) on Jul 27, 2010 at 08:04 UTC

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

In Section Seekers of Perl Wisdom