How many solutions to check?

I asked the year 6 (10- and 11-year-olds) children I teach through Code Club if they could find the five cell pattern that kept a Game of Life board going indefinitely (ie., could they find the “glider” pattern?).

Their prize if they manage it in the next week is chocolate. Of course they could look it up on the Internet – and I won’t object if they do, because they will still have shown intelligence in piecing together the clues.

But what if they search for solution in some algorithmic way? (Actually one of them already sent me an answer which was quite close to correct but was actually a sort of “Methuselah” pattern which filled the screen with living cells before reaching a stasis after about 115 generations.)

Well the first thing they could do is just plonk down 5 counters at random on the board and see if one of these patterns was the correct one. Let’s say they approach this totally randomly and – on average – it takes a minute to determine if the solution is correct or not.

There are obviously {400 \choose 5} possible solutions (this is the binomial coefficient/expansion – we are picking 5 spots at random from 400 possible spots as the board has a 20 x 20 grid) – this is \frac{400!}{(400 - 5)!5!} which is approximately 10^{13} – so using this method would take around the known age of the universe, give an order or two, to find the solution.

So, if we did this by checking cells which were, at most, one cell away from a previous cell? (The work below is my own, I think it’s right!)

Well the first cell could be anywhere, the location does not matter : 1

The second cell could then be in one of eight positions: 1 x 8

The third cell could then be in one of twelve positions: 1 x 8 x 12

The fourth could then be in one of sixteen positions: 1 x 8 x 12 x 16

And the fifth could then be in one of twenty positions: 1 x 8 x 12 x 16 x 20

This would take a mere 30,000 minutes or so to check: a good three weeks or so of continuous work.

4 thoughts on “How many solutions to check?

  1. I suspect you mean “at most, one cell away from ==>a<== previous cell" from the way you actually seem to be counting.

    These look like polyominoes with octagonal cells to me. We don't know a closed-form formula for the number of polyominoes.

    Here's the sequence from the On-line Encyclopedia of Integer Sequences .

    But I don’t think that polyominoes are the only patterns that need to be explored: I think some unconnected configurations are interesting and need to be explored.

  2. I just notices that links don’t come through in comments. The sequence you were looking for is A094169 in Sloan’s On-line Encylopedia of Integer Sequences (OEIS). This one was contributed by Hoey, Bill Gosper (a famous lifer), and Schroeppel.

    Your calculation yielded 30720 5-cell configurations. Their calculation is 3230, and that is without eliminating symmetric configurations.

    The normal way of enumerating polyominoes would make a reasonable skeleton for generating your test cases.

    P.S. If you don’t know the OEIS, have a look at it.

    1. Cheers. I assumed you meant the OEIS in any case 🙂 – the delinking thing is meant to deter spammers. I’ll have to have a look at that and see where I was an order of magnitude out

Comments are closed.