1

I have an algorithm that runs a search through every combination of a 5x5 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.

6
  • I may have misunderstood something, but from your symmetry description, looks like there's a triangle that repeats 8 times within this square? If so, then the triangle consists of 6 entries, and you only really have to generate 3^6 different combinations. Then you can either check for these conditions on the triangle itself, if possible, or reconstruct the whole square and then do the check. If this is indeed the case, that cuts down the search space by a hell of a lot more than a factor of 8! Mar 3, 2023 at 1:48
  • "However, rotating the grid 90 degrees doesn't change anything, nor does mirroring it along either axis" - I guess the crux of the question is what you mean by "doesn't change anything"? Does this mean that you get the same grid after applying these operations, or that you get a different (rotated, flipped) grid, that also satisfies the same set of conditions? Mar 3, 2023 at 2:05
  • @FilipMilovanović Sorry, what I mean is the grid will satisfy the same conditions even if it is rotated or flipped; not that its contents are symmetrical, but that rotating / flipping the contents of the grid do not change the properties of the grid wrt the search. Hope that makes sense. In other words, if I check some grid G (with arbitrary contents, not necessarily symmetrical), then I do not need to check a rotated and/or flipped version of G.
    – Jason C
    Mar 3, 2023 at 3:10
  • 1
    @FilipMilovanović I made a small edit to hopefully clarify.
    – Jason C
    Mar 3, 2023 at 3:13
  • Just asking, is this a 5x5 TicTacToe? Because if so, there are other ways of looking at the board that narrow the space. For one, you can never have 14 or more of a single non-empty token, and you can't have more than 1 more X than O (or vice versa). The space gets overinflated by allowing those variants back in the list of possibilities.
    – Flater
    Mar 3, 2023 at 10:01

1 Answer 1

5
  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.

3
  • You can shave a little bit of time and space by combining step 2, 3 and 4. If when generating the symmetry class, you find a smaller value than the current one, immediately move on to the next number, without needing to calculate the rest of the set. If you haven't found a smaller number, this is the minimal number and needs to be processed. Mar 3, 2023 at 2:21
  • This makes a lot of sense, thank you!
    – Jason C
    Mar 3, 2023 at 3:14
  • @user1937198: yes, I left that out for the sake of simplicity, assuming the OP would be able to figure it out by themselves ;-)
    – Doc Brown
    Mar 3, 2023 at 5:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.