[fuglede_]

That's nifty! There's a lot of symmetry that can help to boil it down. For example, you actually only need row moves, and any solution with column moves can canonically be turned into one with row moves; post-composing with Ci→j is pre-composing with Rj→i.

One can think of the set of all possible board configurations as the vertices as a graph, with edges indicating how to move between configurations. Then your 1536 solutions are the 1536 distinct shortest paths between the starting and target configuration.

Then, you can also choose to consider not just board configurations, but board configurations up to simultaneous permutation of rows and columns; that will also reduce the number of unique solutions.