Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Possibly silly question... I played more than 100 puzzles and casually browsed many more, but I couldn't find one with a symmetry axis. Is it just because they are extremely uncommon, or did you exclude them for some reason?


There are a couple examples linked in another comment[1], so they do exist. The author of the game has stated[2] they excluded about 1/4 of all possible configurations to avoid including puzzles that required too much trial and error. Perhaps symmetry leads to more ambiguity than asymmetry, and therefore more than ~1/4 of symmetrical configurations were excluded?

Your comment made me curious about how often symmetry occurs in the full set of all possible 5x5 configurations. I took a shot at calculating this as an exercise, but I am a bit rusty when it comes to combinatorics...

First consider mirror symmetry via the center column. There are 2^5 configurations of the center column, and for each of those, there are 2^10 configurations of the left two columns. Since we are mirroring the right two columns from the left two, the number of configurations exhibiting mirror symmetry via the center column is 2^5 * 2^10 = 2^15. Rotating these 90 degrees gives us mirror symmetry via the center row, which is another 2^15 configurations. Mirror symmetry via the corner-to-corner axes, which also have 5 squares, is another pair of 2^15 configurations. So now we're at 2^17 configurations for mirror symmetry for the four axes.

Radial symmetry is slightly harder to describe, but it involves similar partitioning. You can partition the 5x5 grid into two 12-square subsets excluding the center square:

    x x x x x
    x x x x x
    x x . o o
    o o o o o
    o o o o o
For any given configuration of the x-subset, you flip and reverse that to get the configuration of the o-subset. There are 2^12 possible configurations of the x-subset. Since there are two possible values of the center square, that gives us 2^13 configurations of two-subset radial symmetry. I believe rotating 90 or 180 degrees simply produces another configuration that has already been accounted for.

There is also four-subset radial symmetry:

    a a a B B
    a a B B B
    D a . c B
    D D D c c
    D D c c c
however, I think these would all be special cases of two-subset radial symmetry. If I pick a random configuration for the a-partition and apply it to the other subsets, it matches a configuration that would appear in the two-subset group:

    a a a B B    X X o B B    X X o o X
    a a B B B    o X B B B    o X X X X
    D a . c B => D X . c B => o X . X o
    D D D c c    D D D c c    X X X X o
    D D c c c    D D c c c    X o o X X

So between mirror symmetry and radial symmetry we have: 2^17 + 2^13 = 139,264. There are a total of 2^25 = 33,554,432 configurations irrespective of symmetry, so that's 17/4096 or roughly 0.415% that are symmetric...a bit more than 1/256.

EDIT: And by some hilarious bit of fate, I just went to go knock out a few puzzles to reset my brain, and the first one I completed[3] exhibits mirror symmetry in one of the diagonal axes. I'm pretty sure this is the first one I've hit in over 1000 solves.

[1]: https://news.ycombinator.com/item?id=44148396

[2]: https://news.ycombinator.com/item?id=44141047

[3]: https://pixelogic.app/every-5x5-nonogram#3328511

EDIT: formatting; add link to symmetric puzzle




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: