I'm working on a programatic solution to a combinatorics problem involving the board game Quarto. In Quarto there are sixteen pieces each with four binary properties. This means we can represent each piece as a tuple (i, j, k, l) where each element is either zero or one. To solve my problem I need to iterate over each unique way to arrange all of the pieces on a 4x4 playing board. I could do something like
from itertools import permutations
for board_orientation in permutations(pieces, 16):
do_stuff(board_orientation) #takes 1 or 2 full seconds
but this would mean 16! (over 20 trillion) iterations. To avoid this I'm trying to create a generator that yields only unique board orientations - that is orientations that are unique under rotation, reflection, and inversion of one or more properties (the first two properties are described by the dihedral group D4). I have found a similar question for Tic-Tac-Toe, but I'm struggling on how to extend it to this more complex iteration problem.
I think the solution involves mapping each board orientation to a numerical value via a hash tree, and then seeing how the number changes under the various symmetry operations, but struggling to convert this into code.
A board is 'isomorphic' to 16 boards by applying inversions, and to at most 8 boards by applying rotations and mirroring. That is set of isomorphic boards is at most 16*8=128. With that there are at least 15!/8 (1.6 * 10^11) board configurations.
Using inversions each board can be 'transformed' into a board with 0 in top-left corner. Fixing one corner covers all of symmetries except mirroring on diagonal through top-left corner (and lower-right.) That symmetry can be covers by choosing two 'opposite' fields on that symmetry (like (1,2) and (2,1)), and requiring smaller value in one of them (e.g. B[1,2] < B[2,1]). That means if B[1,2] > B[2,1] than perform diagonal mirroring. Board transformed in described way can be coded by 15 hexadecimal digits string (top-left field is always 0.) Call this coding normalization by top-left corner.
In the same way one board can be normalized by other corners. One board have 4 corner normalizations, and let call board ID minimum of these normalizations. That ID uniquely codes group of isometric boards.
Now the nice part :-), it is not needed to store generated IDs in a configuration generation process. It is enough to generate boards in lexicographic ordered of one corner normalized forms (e.f. top-left), calculate other three normalizations and if any of other three normalizations are lower than generated than we already pass that configuration. That is due configurations are generated in lexicographic order.
Note: it is possible to optimize code by checking normalization values inside creation board process, instead of creating whole board and performing upper checks. Like, fill two ordered fields ((1,2), (2,1)) than fill other corner with it's two ordered fields, if normalization of second corner has to be smaller than normalization of top-left corner (checking prefix of only two fields) than there is no need to generate further. For that coding has to have ordered fields as first two digits. Extension is to next fill third's corner fields, perform check, than fourth's corner fields and perform check.