Web Paint-by-Number Forum

Topic #208: Symmetry

By Jan Wolter (jan)

Topic #208: Symmetry

By Jan Wolter (jan)

**#1: Jan Wolter (jan) on Jan 27, 2010**

The Advanced Puzzle Solving page that I wrote for this site talks a bit about symmetrical puzzles, ones where the clues are symmetrical, so that if you flipped them around, say, a vertical axis, they would not change. If you have a have a puzzle with symmetrical clues, then it is obvious that you could reflect any possible solution around the same axis, and still have a valid solution. This means either (1) the solution must be symmetrical, (2) there are multiple solutions, or (3) there is no solution. The third case can never happen on this site, though if you created a puzzle just by writing down a lot of clue numbers, it would be a pretty likely outcome, but you can't quite exclude the second case, so it isn't really completely logically sound to assume that the solution is symmetrical just because the clues are.However, something else just occurred to me. Suppose you had a puzzle that had symmetrical clues but no symmetrical solution. For purposes of discussion, here's a simple example (please forgive the crudity of the drawing):

1 1 1 +--+--+--+ 1 | | | | +--+--+--+ 2 | | | | +--+--+--+Let's suppose we forgot all about line solving and tried to solve this with symmetry instead. Since the clues are horizontally symmetrical, our usual procedure would be to fill in all the cells of the center column, black if the row clue has an odd number of clue numbers, white otherwise:1 1 1 +--+--+--+ 1 | |XX| | +--+--+--+ 2 | |XX| | +--+--+--+But this leads to a contradiction, since we now have two black cells in the center column, which may only have one.So something interesting has just happened. We didn't solve the puzzle, but we did prove that it does not have just one solution. It either has multiple solutions, or none. Being able to prove that without actually solving the puzzle, is, in my opinion, really cool.

So if you apply symmetry logic to solving a puzzle, there are two possible outcomes. Either you hit a contradiction, and prove the puzzle does not have one unique solution, or you find a solution, which may or may not be the only solution. Almost, but not quite, cool enough to make me feel that it is acceptable as a valid technique for logically solving a puzzle. The fly in the ointment is that if you do find a solution you still don't really know if it is the only one.

Actually, you can go one better. With some symmetrical puzzles, including very large and complex ones, you can tell at a glance that it does not have one unique solution, without solving even one single cell. Well, this is a puzzle site, let's make a puzzle of it:

Suppose you have a 200x200 puzzle and all the clues are symmetrical around a vertical axis like the example above or the one in the "Advanced Puzzle Solving" discussion. Suppose one of the horizontal side clues is "13 13 13". You can state positively without needing any other information that the puzzle does not have a unique solution. It either has multiple solutions or is insolvable. Why?

"Suppose you have a 200x200 puzzle..." Jan, you have a BIG imagination. :-) I can't figure out your puzzle. If someone else can, I hope they can explain it well enough so my fuzzy brain can follow it. Your brain is amazing!

Another feature of symmetrical puzzles is that clues on both axes are symmetrical. If you have y-axis symmetry, then the clues across the top will match those on the other end, while the clues on the side will be mirrored within the row. In an odd-numbered width, this would never result in even number being the lone number on the row. It would either be paired with an identical even number, or it would be odd. In your 200x200 example we have the opposite issue; odd-numbered clues will be in even pairs if the puzzle is symmetrical.

I was going to say what Wombat said, but likely with less words. :)

I think Wombat has got the answer, but this is pretty hard to talk clearly about. If the side clue is supposed to be "13 13 13" and the row is supposed to be symmetrical, then the middle thirteen block has to be in the middle of the puzzle. But if the puzzle has an even number of columns (200 in this case) then you have a problem. You can't center an odd sized block in an even sized number of columns.

So, in general, if a line is supposed to be symmetrical than either (1) there have to be an even number of clue-numbers in the clue, or (2) the center clue-number has to have the same parity as the number of cells in the line.

So in our 200x200 even-sized puzzle, clues like "13 13" would be fine, because that has a space in the center and we can make the space any size, and clues like "12" or "13 12 13" would be fine, because they have even numbers in the center, and even sized blocks can be centered on an even sized grid. But clues like "13" or "13 13 13" would not be OK.

If the number of cells is odd, then clues with even numbers of clue-numbers still always work, but clues with odd numbers of clue-numbers have to have an ODD number in the middle. This is the case with the little 2x3 puzzle I drew above. It has a row clue of "2". You can't center 2 cells in 3 columns. So obviously there is no symmetrical solution. Yet the clues are symmetrical, so we know that if there is one solution, there is another different solution, since the mirror image of the solution has to be a solution and it is not the same as the original solution. So this puzzle must have an even number of solutions, like 0 or 2, but not 1.

So the point is, that once you notice that clues are symmetrical, you can get quite a lot of interesting information from that.

Jan, here's something to think about.

If the clues in a puzzle are symmetrical but for an extra 1 on each side of the axis, can you assume that the pixel where those two 1s cross is a black pixel?

See Gator's puzzle #8222 for an example.

It is intuitive that this would work, but I can't come up with a theoretical framework for it.

It occurs to me that the symmetry must be along a diagonal so each side of the axis corresponds to the different sets of clues.

#7100 is a puzzle that is symmetrical like in my previous post, but the axis is not diagonal.

In this case, it is a rotational symmetry around column 6. As a 10x10 puzzle, that leaves c1 out, and indeed, the 2 in c1 is reflected in an extra 1 in r1 and a 1 turning into a 2 in r2.

I noticed the symmetry after placing four pixels and decided to test the assumption by blacking c1r1-2, which worked out.

Now I have to go back and re-solve it with "normal logic" ;p

So there are basically three forms of symmetry.. Symmetry about the x-axis, about the y-axis, and about the origin (diagonal). My puzzle #7100 is symmetrical about the origin, since you can flip the top half of the puzzle about the x-axis, then the y-axis, and it would be identical to the bottom half. This is probably the most difficult type of symmetry to recognize, but I guess if you can prove it somehow you can apply it.

Really, there are only two: mirror and rotational.

In comment #6 I was referring to mirror symmetry along the diagonal axis.

Mirror symmetry is definitely the easiest to see as it's all around us. Most creatures are mirror-symmetrical.

Rotational symmetry is like in crossword puzzles. One half is the same as the other, except rotated 180°. (In most crosswords it's even more symmetrical: each quarter is the same; rotated 90° each.) This kind of symmetry is seen in plants (like flowers).

Mathematics recognizes two more types of symmetry that the layman generally won't regard as such: translation and glide-reflection.

Basically, translation is repetition and glide reflection is mirror reflection where one side moves parallel to the axis of reflection.

oh man translations and glide reflections.. flashbacks of 9th grade geometry class

Re #1 -- I've just today been thinking of making a puzzle that exploits "symmetrical" logic, but hadn't got very far. The logic of even/odd outlined above is clever, and a very nice addition to the techniques of solving/creating puzzles

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