Building on the toy games introduced here.

I figured the easiest tile-game move to analyze is transpositions. Only two tiles are affected by any move, and they have to be opposite colors in any minimal solution. My earlier code showed, for example, that it takes 8 tile swaps (orthogonal moves only) to convert:

1101
0110
0100
1010
to
1111 ( Read more... )

The size of the search space in the toy problem I described in the last post is basically (n^2) choose (n^2)/2 for an n x n board. My initial implementation is in-memory only which only works for 3x3 and 4x4. It ought to work for 5x5 too but for some reason Python (on Windows) just stopped computation rather than giving me an out-of-memory error ( Read more... )

My vacation project has been putting together some Python code to systematically study various tile-permuting operations found in match-3 or sliding puzzle games. What I'm interested in is: given a particular goal on a square grid (like making a group of N tiles, or arriving at some other in a set of arrangements), how many moves does it take to ( Read more... )

...will not become a regular feature, unlike timprov's classic photos ( Read more... )

Suppose you have a set A and you want all possible ordered triples of elements in A. In Python you can just do

for x in itertools.product( A, repeat = 3 )Now, what if A has a special element X and you want only the ordered triples that include at least one X. What's the best way of doing so? (Assuming we want to pick only among the ( Read more... )

One branch of theoretical computer science looks at "circuit complexity", studying the size and depth of boolean logic circuits necessary to produce a particular function. A puzzle in this area is whether we can invert three binary digits using just two inverters (but as many AND and OR gates as we want ( Read more... )

I happened across "A multimodular algorithm for computing Bernoulli numbers" which implements a cute hack. The Bernoulli number B(k) mod p can be efficiently calculated for prime p > 5. You can calculate a bunch of B(k) mod p_i in parallel, then use the Chinese Remainder Theorem to stitch those results back into the desired number. This ( Read more... )

From "Combinatorial Analysis and Computers", February 1965:

When the size of a combinatorial problem grows very rapidly, we can usually expect the computer to do only about one case larger than can be done by hand.

I am curious whether there are readily-available examples where this is still true.