Algorithms – Narrowing Down Search Space with Equivalent Symmetries

algorithmscombinatoricsperformance

I have an algorithm that runs a search through every combination of a 5×5 grid where each cell can have 3 values, looking to see which combinations meet certain conditions. This gives 3^25 naive combinations.

However, rotating the grid 90 degrees doesn't change whether or not it satisfies the search conditions, nor does mirroring it along either axis*. This means I can theoretically cut down the search space by a factor of 8 (4 rotations * 2 flips) based on symmetry equivalence alone (not much but it helps).

Except, I don't have a lot of experience with search trees and I can't wrap my head around how to prune symmetries out of the search space as early as possible.

How can I search this space but cut out all of the symmetries?

* That is, if I take any given arbitrary grid and rotate/flip it to get 8 variants, all of those variants are equivalent.

Best Answer

  1. Each of the 3^25 combinations can be interpreted as a 25 digit number in base-3 number system. So there is a one-to-one correspondence between those numbers from 0 to 3^25-1 and those combinations / grid configurations.

  2. Each combination belongs to a symmetry class of up to 8 combinations in total, which can be determined by applying the symmetry operations (rotations and mirroring) you already know. When you use the base-3 representation, the 8 symmetry operations are just permutation of the digits, which can be implemented pretty fast.

It should be clear that you only need to test the conditions you want to test for one of the (up to) 8 combinations in a symmetry class. When you look at such a symmetry class and interpret each of the combinations as a number, there is always a minimal one among them.

This leads to the following algorithm:

  • loop through all numbers x from 0 to 3^25-1
  • calculate the symmetry class of x, which are up to 8 different numbers {x1, x2, ..., x8}
  • when x is the minimal number in this set, test the conditions you want to test for the corresponding grid
  • when x is not the minimal number, skip it.

That will still require 3^25 iterations, but only in roughly 3^25/8 cases you will have to test the conditions (the real number is a little bit larger, since some of the symmetry classes have less than 8 different elements). Assumed testing the conditions needs more running time than just calculating the symmetry class, this should do the trick.

Of course, this approach has some potential for further optimizations. As mentioned in a comment, testing if x is the minimal number of it's symmetry class does usually not require to generate all 8 members, the test can stop immediately when one smaller member was found.

Another optimization can be implemented by putting four symmetric cells (like the four corners) of the grid at the 4 most significant digits in the base-3 representation. Since each symmetry transformation will just permutate those cells/digits among each other, one can restrict the search to ranges where this 4-digit number is minimal in it's 4-digit symmetry class. I wrote a small script to count the classes, this approach will leave you with 21 out of 81 four-digit numbers, so roughly 1/4.

Related Topic