Given the solutions of a polyomino-puzzle one could ask themselves, how related the solutions are to each other.
Given one solution there might be two polyominos that can be taken out and put back in a different way, creating a new solution. Like in this example with the only difference being the position of the grey and blue polyomino.
We then say the above solutions have a distance of 2, or are leq-2-connected.
However due to the many solutions such a puzzle may have, a graph of all solutions may not give as much insight into this question.
This project therefore generalizes the above idea to create graphs with the following features: Given two numbers 1 <= n < m <= #polyominos
- nodes are the equivalence classes of solutions modulo the composit closure of leq-n-connectedness; One equivalence class contains all the solutions, for which there exists a finite number of leq-n-changes to get from one solution to the other.
- edges are drawn between two equivalence classes of solutions, if there are two representatives of the equivalence classes, which are leq-m-connected.
This narrows down the number of nodes in the example puzzle given from 32288 to just 971, if we take n=4 and m=5. The biggest connected component of this result is the uppermost - left picture. The node highlighted in green contains about 90% of all possible solutions.
And we can repeat this step. Given the subgraph of only the green highlighted equivalence class. We repeat this with n=3 and m=4 and obtain the middle picture. Repeated again with n=2 and m=3, we get the third picture above. At last we get the fourth picture when setting n=1 (no equivalence classes, except two or more polyominos fill the same space) and m=2. There is a remarking symmetry in the last picture.
This Project let's you 'zoom-in' on a specific solution using this procedure. It creates the following files:
- In directory
*_solution_ids.txt- a listing of all solution-ids occuring in the graph (no equivalence classes)*_nodes.csv- a listing of all nodes occuring (no equivalence classes)
- Out directory
*_size[X]_leqm-n.csv_EQ.csv- nodes (equivalence classes)*_size[X]_leqm-n.csv_ET.csv- edge table containing all edges*_size[X]_leqm-n.csv_NT.csv- nodes weight table
The files generated in the output directory are easily imported into a graph-viewing program, like Gephi, which I used to get the above graphs.
Note
The file DisjointUnion.scala is not yet uploaded. It uses a basic implementation of the disjoint union algorithm and will be replaced with an implementation using cats in the future.