On the uniqueness of solutions

An exchange of comments in the Willa's Walk review prompted me to talk more in depth about solution uniqueness in logic puzzles, and its possible use as a shortcut while solving the puzzles.

First of all, one question which I'm often asked is: why should logic puzzles have a unique solution?

The easy answer is: why not? When you solve a crosswords puzzle, you take it for granted that there is only one valid solution. So why should logic puzzles be any different?

The more articulated answer is: because logic puzzles are puzzles that should be solvable by logic, and logic alone; no guessing should be necessary.
Solving a logic puzzle should consist of a series of logic deductions which allow you to exclude possibilities, until you are left with only one option. If the puzzle didn't have a unique solution, you would inevitably get to a point where you have two equally valid options, and you cannot choose between them, because they both lead to a different solution.

Once it is determined that a puzzle has a single solution, a question comes to mind: can one use this knowledge to make deductions and find the solution more easily?

This is a thorny issue, which I think has been well explained by Sudopedia this way:

- Sudoku axioms are constraints on the solution, given the entries (whichever these are); they are constraints the PLAYER must satisfy;
- Uniqueness is a constraint on the entries; it is a constraint the PUZZLE CREATOR must satisfy and the player may use if he trusts the puzzle creator; for the player, it is like an oracle on the puzzle.

In other words, a logic puzzle gives you a task to complete, like in Sudoku: "put numbers from 1 to 9 on the grid in such a way that each number appears exactly once in every row, column, and box." The rules don't say anything about the uniqueness of the solution, so the player shouldn't feel authorised to use that knowledge to make any deduction. However, if and only if the puzzle is well designed, it guarantees that the solution can be found using only logic deductions, and therefore the solution will be unique. If the puzzle is well designed, you can use deductions based on uniqueness, and you will reach the solution. This is a circular argument, however: if the puzzle is not well designed and has multiple solutions, the deductions based on uniqueness are invalid, and will likely lead you to a dead end.

So let's see some examples of those techniques. One I already showed in the Willa's Walk review mentioned above. Some Sudoku techniques are explained on the Hodoku site; let's see now how the same concept can be applied to Zen Garden Puzzle. Look at this position:

Can the stones circled in red be in the right position?

No, because their positions can be swapped, keeping each one in its zone and without moving the other stones:

So if the first position was part of a solution, the second one would be as well, and the solution wouldn't be unique.

How can we avoid this? One of the stones has to be moved out of the way, so that it is no longer possible to make the swap. This is done by placing the left stone in the top left corner of its zone:

This technique can be applied often, and it helps a lot in figuring out the solution quickly. I guarantee that every puzzle in Zen Garden Puzzle has a unique solution, so you are officially authorized to use it :-)

In some puzzles, the uniqueness deductions can be so powerful that they borderline into cheating. I found an excellent analysis of Hitori which I encourage you to read.

Let's now talk about a puzzle game which you surely know, since it is so popular on the App Store: Flow Free.
This game is just the classic Numberlink, or Arukone. In this logic puzzle, there is supposed to be only one rule: join the dots of the same color with lines that don't cross each other. But there's something wrong in Flow Free. Let's see one of its puzzles.

Even if this grid is large compared to easiest ones in the game, satisfying the rule is trivial and done in seconds, for example this way:

What's the problem here? That we used less than half of the available cells.

Why did that happen? Because the solution of the puzzle is not unique.

Flow Free forces you to use the whole grid, even if that's not the point of the puzzle.

So you are forced to make the lines do some uninteresting additional random twists and turns just to appease the game.

It is easy to see why it was done this way: because it makes it trivial to generate millions of puzzles that can be sold at no marginal cost. All one has to do is fill a grid with random lines, mark the endpoints, and propose that as a "puzzle". But that's not what the real puzzle is about.

The focus of Numberlink is finding the paths that connect the dots without crossing each other. That's supposed to be the hard part, and there should be only one way to do it. It's the uniqueness of the solution that implies that the paths (usually) cover the whole grid: because if they didn't, it would be possible to modify some path slightly without intersecting other paths, and the solution would no longer be unique.

Numberlink in its proper implementation is also a very special kind of logic puzzle, because its rule doesn't actually allow one to get far, so it wouldn't appear to be solvable by logic alone. But as soon as one starts to actively use uniqueness for the deductions, the puzzles become logically solvable. You should read this excellent post by +Palmer Mebane on the subject, which is enlightening. Try applying what you'll read there to some true Numberlink puzzle from janko.at, like this one: #14. It's a completely different experience from the one given by Flow Free.

To the best of my knowledge, at the moment there is no game on the App Store which implements Numberlink properly. There is a gazillion of copies of Flow Free, and a couple of original games, but they all have the "you must use all cells" rule.

Do you know of a proper Numberlink app? If so, please let me know in the comments.



©2013 Nicola Salmoria. Unauthorized use and/or duplication without express and written permission is strictly prohibited. Excerpts and links may be used, provided that full and clear credit is given to Nicola Salmoria and nontrivialgames.blogspot.com with appropriate and specific direction to the original content.