Web Paint-by-Number Forum
Topic #8: Symmetry set
By Mark Conger (aruba)

#1: Mark Conger (aruba) on Jan 5, 2005

I've been spending a lot of time with a certain unpublished puzzle, trying to solve it. I found one solution, but there are multiple solutions, and I haven't found the one the author intended. I keep trying to modify the one I have to make it look more like something recognizable.

It started me thinking about the set of all solutions to a puzzle. Clearly there are certain operations you can do to a picture which will leave its paint-by-number description fixed. For instance,
<pre>
.. ..
..*. can be replaced by .*..
.*.. ..*.
.. ..
</pre>
without changing the puzzle description. (Of course that means that puzzles with a unique solution can never contain those little pictures.)

My question is, if you list all the solutions to a given puzzle, is there some short list of operations like the one above which will generate all solutions from a given one?
In other words, can we define operations A_1, ..., A_n,
for some small n, so that for any two solutions there is a sequence of transformations A_{i_1}, ..., A_{i_m} which changes one solution into the other?
#2: Mark Conger (aruba) on Jan 5, 2005
Hmmm - that picture didn't come out too well. Multiple spaces were replaced by a single space. Can I make Backtalk not do that?
#3: Mark Conger (aruba) on Jan 5, 2005
My question is inspired by a concept from knot theory called "Reidemeister moves". The mathematician Kurt Reidemeister showed in 1927 that you can transform any representation of a knot into any other representation of the same knot with a finite sequence of simple operations. Only 3 operations are needed; there's a picture of them here: http://en.wikipedia.org/wiki/Image:Reide.jpg
#4: Jan Wolter (jan) on Jan 5, 2005
Amazingly enough, this is not backtalk. I actually wrote an entirely different conferencing system for this site, instead of continuing my usual practice of using Backtalk for everything. Unlike backtalk, it doesn't have a html sanity checker, so the only person who can post HTML is, well, me. So here's Mark's picture:
 ..                        ..
..*.  can be replaced by  .*..
.*..                      ..*.
 ..                        ..
#5: Jan Wolter (jan) on Jan 5, 2005
I doubt it.

Consider the set of 2n by 2n puzzles, all of whose clues consist of n ones. These have exactly two solutions - checkerboards, one with the upper left corner black, the other with the upper left corner white.

Now, since those are the only two solutions, there must be an operation in your set that will transform one into the other. This is an operation that changes the color of every single cell on the grid. That's quite an operation.

This doesn't prove that no such set of operations exist, it just proves that the operations cannot be all simple localized things like the Reidemeister moves. Which pretty much means the whole thing is going to be uninteresting.
#6: Mark Conger (aruba) on Jan 6, 2005
Good counterexample.
#7: Curt Jeanis (ocshelper) on Feb 13, 2005
I have an unsolvable puzzle in my saved puzzles. How can I get rid of it?
#8: Jan Wolter (jan) on Feb 15, 2005
Good question....um...you can't. I had the same problem and fixed it by guessing and guessing until I guessed right, but that is ridiculous. I should really put in some kind of control so that you can delete them. If it's the puzzle I think it is (123), it has actually been un-published, but that doesn't make it vanish from your saved games list.

I can delete them...but it looks like you actually have three (123, 134, and 147), and I'm not entirely sure that it's 123 you want deleted.
#9: Curt Jeanis (ocshelper) on Feb 16, 2005
123 and 134 are the ones I would like deleted. Thanks.

Goto next topic

You must register and log in to be able to participate in this discussion.