▲ | MisterMusion 3 days ago | |
Enumerating all 7-Move solutions of today's puzzle, I expected some kind simple pattern, like some key moves with a few permutations. I found that it is far more complex: - there are 1536 solutions - almost all moves are useful, non are required - for every row-xoring move there is exactly one column-xoring move that appears in the same number of solutions (and no move appears twice in a solution) Here is the number of solutions a move appears in (0-based indices):
| ||
▲ | fuglede_ 3 days ago | parent | next [-] | |
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. | ||
▲ | 3 days ago | parent | prev [-] | |
[deleted] |