Skip to content

morph.md

Latest commit

 

History

History
109 lines (76 loc) · 8.29 KB

morph.md

File metadata and controls

109 lines (76 loc) · 8.29 KB
Raw

Morph Notes

Background

Discussions related to equivalence checking can be found by searching for "Sudoku Canonicalization". Equivalence can be checked by canonicalizing two sudokus and then checking if the results are identical.

Scramble-Invariant Properties of Grids

Scrambling cannot:

  • Swap cells between 1xO1 (vertical or horizontal) box-aligned slices (I will call this an "atom").
  • Swap cells or atoms between houses.
  • Swap boxes between chutes except by swapping entire chutes.
  • Change the vertical/horizontal orientation of an atom except by transposing the whole grid.

Partial Imbalance Analysis

Once source of chute_imbalance is in the distribution of same-atom relations between horizontal or vertical chutes. If such a same-atom relation happens N times, the most evenly distributed way for them to occur across one polarity of chute can be represented by creating an array of length O containing numbers in [0, IMBALANCE_MAX]. IMBALANCE_MAX is equal to 2 * (O floor_div 2) * (O - (O floor_div 2)). Cycle over the entries decrementing a counter from N each iteration and incrementing the entry. Imbalance can then be calculated by counting the number of times the relation occurs in each chute, sorting in decreasing order, and then summing the differences between the result and the balanced version.

My Canonicalization Algorithm

I decided not to try to support direct canonicalization of puzzles. I don't know how much time it would take to adapt the current algorithm to work for that, and there's another way to do it which is much simpler to understand: simply solve the puzzle, canonicalize the solution, and apply the same canonicalizing transformations to the puzzle. While it comes with the cost of solving, there is elegance in that this approach is easy to implement outside of any canonicalization algorithm's specific implementation details, and that when the puzzle is solved, the solution will be in canonical form.

Symbol Canonicalization

Given a grid G and a pair of symbols a and b, for each box B of G, we can observe whether, and in what orientation a and b cohabit an atom in B.

Given G, a, and b, this could be visualized like so, in an O1 x O1 grid of Bs, where "0" represents no atom-cohabitation, "|" represents cohabitation of a vertical atom, and "-" represents cohabitation of a horizontal atom:

- | |
| | 0
0 0 -

This is still a positional frame of observation (because of the grid of Bs). but we want to observe qualities that are position-agnostic.

Here are some position-agnostic qualities we can extract from this frame of observation:

  • How many boxes do the two symbols cohabit an atom in? [0,O2] sort desc.
  • Of the atom cohabitations, how many are horizontal, and how many are vertical? [0,O2] sort desc lexicographically of desc sorted per direction
  • Try to normalize "-" / "|".
    • For each cohabitation-orientation cell,
      • How many other cells does it see "pointing to" it? Ex. 121 011 231
      • How many other cells does it see "orthogonal to" it? Ex. 212 213 100
    • How many other "occupied" cells can it see? notice the information redundancy in that the arraysum of the above two equals this.
    • Could try to maxlex these by performing chute rearrangement and transposition to factor out positionality from it.

Note that for a given symbol a, the number of atom-cohabitations it has with symbols other than itself is always exactly O2 * (O1-1)*2, and the number of times it cohabits an atom with some other symbol b is in the range [0,O2], with an average of (O1-1)*2.

Now that we can assign quantitative measures to relationships between pairs of symbols, we can try to provide an ordering between two symbols based on their relationships with all other symbols (for each a and b, performing some kind of sorting or normalization of the quanitifcations of its relationships with other symbols S-{a} and S-{b} respectively to make them symbol-agnostic as entities that can be compared to produce an ordering).

Position Canonicalization

This depends on first performing symbol canonicalization.

Time Complexity

TODO: update this.

Result

Note that there are many possible variations on the calculations / measures used in my algorithm that can just as well canonicalize. I made decisions according to the above goals.

The end result of the specific choices made is that:

  • Symbols are given such that lower valued ones "play favourites". (they will cohabit atoms with some label values more than others).
  • Instances of favouritism will be more concentrated at the top and left of the grid.

This may help with solving- symbol labelling and positioning are "sorted" to specific relationship patterns.

Other Approaches For Exploration

This was originally more of a "things that I tried and didn't work" section, but I'm rebranding since when I originally tried these, I wasn't taking into account any scramble-invariant properties of grid other than the number of times a pair of label values occurred in the same atom in a grid.

config_auto_canonicalizer Relabelling

  • Linear Algebra Route: Try breaking relabelling ties by using powers of the counts matrix (normalized to the same support). Need to find a continuous version or approximation of the Binomial distribution's PMF. Do some research, and as a last resort, just lerp it or something. Read about the gamma function (continuous version of factorial?). tgamma(i+1) = i!

    • A public domain library for the Jacobi algorithm (for diagonalizing dense, real symmetric matrices) https://github.com/jewettaij/jacobi_pd. This could be useful if going through several steps is needed to break ties.
    • This doesn't work for order 2. I know order 2 isn't even marginally interesting, but I think the solution should work for any order, and if it doesn't work for order 2, then something's wrong with it. That being said, I didn't explore this route much. Perhaps with adjustments, it can be useful.

  • Graph Theory Route:

  1. Come up with a weight mapping for each edge in rel_counts and then do a Floyd-Warshall, and then map each row of the result to either its max or its sum, and then sort. For mapping meanings, see Closeness Centrality- also the section on disconnected graphs.
    • The weight mapping can be: (recall that (rel_counts[i][j])/O2 represents the probability in this sudoku grid's markov chain of transitioning from label i to label j.)
      • O2 - rel_counts[i][j]
      • rel_counts[i][j] interesting? what's would this mean / represent?
      • p_binom(rel_counts[i][j]) what would this mean / represent?
      • If further differentiation is needed, look into factoring in more scramble-invariant properties.
    • Would this work against the Most Canonical Grid? I don't have high hopes. Will need to test or reason it out.
    • Note that there are other definitions of centrality, such as Betweenness Centrality, but it uses information that isn't retained in the basic Floyd-Warshall algorithm.