Is there a puzzle that is only solvable by assuming there is a unique solution?

Question

Is it possible to construct a puzzle that is:

1. Solvable if you assume there is a single unique solution
2. Not solvable if you do not make this assumption

My intuition says that the answer is "No", but I'm struggling to prove it one way or another.

By "puzzle" I mean:

• Something that is (typically) solvable by using logical steps, no guessing required.
• Does not have to be perfect-knowledge (e.g. minesweeper puzzles allowed)
• Does not have to conform to a 2D grid. I'm pretty sure that all logical puzzles can be mapped to an n-D grid, however.

Answer 1

At least not if the solution space is a countable infinite set, or smaller.

In that case, we can compute the finite time person 2) will need to find the solution found by person 1) by enumeration, making the strategy of 2) a computable function and therefore violating the constraints of the question.

---

Response to edit:

The "does not have to be perfect-knowledge" point changes things up a bit. It allows puzzles of the following type:

"I have a hidden number that's either 3 or 4. Give me two natural numbers that sum to my hidden number".

1. Assuming a unique solution, we can rule out that the number is 4 since both 1+3 and 2+2 would be valid solutions, making them not unique. We have now logically deduced that the solution is 1+2. (The deduction would be "iff 1+3 is a valid solution, so is 2+2. But since this puzzle has a unique solution, that can not be the solution".)

2. Not assuming that the solution is unique, we can not rule out that the hidden number is 4. The puzzle can thus not be solved without guessing.

Allowing imperfect-knowledge puzzles thus leads to the opposite conclusion, that such puzzles are indeed possible.

---

A discussion later:

An interesting fact to point out is that if one assumes a unique solution to the puzzle above, one may arrive at different conclusions by attacking it with different unique arguments. One such argument could be "if one addend is 3, 1+3 = 4 is a unique solution to the puzzle, so that's the solution". What this does is implicitly allow the puzzle to have multiple solutions, making a unique argument allowed to pick any (or none) of the solutions.

This does not change much in that 1) will find a solution while 2) will not, but it is a different and incompatible interpretation of the puzzle. Nevertheless, it still says that the answer to the question is "yes, such puzzles are possible".

For a more rigorous proof that avoids multiple interpretations like this, one must have clear definitions of what exactly "solve" means, and how "hidden information" works.

Answer 2

No.

If there is exactly one way to fill out the grid in a valid way, then that can be found without using any logic based on uniqueness. (It may be very painful, and require brute-forcing a lot, but it won't be impossible to find.)

If there are exactly two valid ways to fill out the grid, then uniqueness logic cannot help you. You can never make a deduction of the form "if X happens, then there are multiple solutions, so it can't be X" that rules out exactly one of the two solutions -- because all deductions of that form must rule out the multiple solutions including X!

If there are three or more valid ways to fill out the grid, uniqueness logic can give you any of them! In the extreme case, you can enumerate all possible solutions, and say: "It's either solution #7, or it's not solution #7. If it's not #7, then there are multiple solutions. Therefore it's solution #7."

So, no matter what, you can't make a puzzle solvable with only uniqueness logic. You might be able to make one that's easier with uniqueness logic, but not one that's only possible with it.

---

Of course, you may not be convinced by my last case there -- it seems very artificial. There are more natural examples that demonstrate the problem, though.

The paper "Uniqueness in Logic Puzzles" has a good explanation of why this is, and they give a particularly good example of how uniqueness logic can go wrong when there are multiple solutions. They give this Slitherlink puzzle, that has exactly three possible solutions:

And then show that, depending on where you check for uniqueness, you'll get to a different solution. If you check a segment near the top left, you'll find that solution (c) is 'the correct one'; if you check a segment near the bottom right, you'll find that solution (b) is 'the correct one'.

This is a relatively trivial example, but this could be embedded as one corner in a larger puzzle (with the loop escaping in the bottom right rather than wrapping around). If it was embedded like that, an experienced Slitherlink solver could very easily notice one of those. And if they used uniqueness logic, they would get either solution (b) or (c) without ever realizing something was wrong.

---

It may be possible to have only one "natural" solution if you assume uniqueness: that is, a "natural" set of uniqueness deductions will lead to only one of the solutions. But now we've left the realm of pure logic, and you're looking for something that will be "natural" to every single solver -- this would be very subjective, and unlikely to work for all but the most trivial examples.

Answer 3

Find any integer $n$ such that $n$ is the number of solutions to this puzzle.

Answer 4

I know this question has already been answered (and in a better way than I could ever have!) but I feel like it is worth bringing up the generic category of puzzle "Knowledge Puzzle" or "Induction Puzzle", which kind of fits the original description. (This category includes problems like the "coloured hats" puzzle group, and things like Cheryl's Birthday.)

They are "logical" (the "actors" in the puzzle are always considered perfect logicians, or the setups usually make no sense), you don't have all of the information (in fact lack of information is usually the premise of the puzzle), but the "answer" is usually the solve path, and not the end-state of the puzzle world (which is usually given to you).

In a sense, Cheryl's Birthday as presented is literally two people discussing a logic puzzle of the usual grid-kind but with (different) imperfect information and whittling down between them to one answer because they can remove option paths where there is more than one end-state.

Answer 5

Is it possible to construct a puzzle that is:

1. Solvable if you assume there is a single unique solution

2. Not solvable if you do not make this assumption

How about this one:

Given a function on the natural numbers, $F: \mathbb N \Rightarrow \{0,1\}$, such that the probability that $F(n)=1$ is $2^{-n}$, find all $n$ such that $F(n)=1$.

If you assume there is a single unique solution, you'll eventually find it. But if you allow for the possibility that there are zero or multiple solutions, you can't.

Answer 6

Whereas the question has already been answered, here is a corroboration on answering it with "yes", by providing a minimalistic mathematical example. Many non-linear relations contain one or multiple points with unique characteristics or singularities, which you can exploit in such a riddle. Consider for example a parabola $y=x^2$. Find me the numerical and real value of $x$. You can't solve this unless either I provide you the numerical value of $y$, or if I provide you the given that there is a unique solution for $x$: generally, every value of $y$ returns two solutions ($x=\sqrt{y}$ and $x=-\sqrt{y}$), except for the unique case $y=0$ (the minimum), in which case $x=0$. Note that the term non-linear is crucial here. Many grid-deduction puzzles are based on linear algebra, which cannot exhibit such behavior (despite being multi-dimensional).

Answer 7

I'm interested in the community's take on this trivial example using Tapa rules:

2 3 2
_ _ _
_ _ _
_ _ _
2 3 2

Basic rules force the second and fourth rows to be all shaded. For either side of the middle row, one could argue that shading that square leads to multiple solutions, but you cannot make that argument for the middle square. So there is a philosophical argument to be made that middle square is the "right" square to shade.

This of course does not obviate @Deusovi's argument at all, because once you convince yourself you cannot shade a side, you're now free to shade the other side. Just a logical observation I find interesting.

Answer 8

Puzzle I: Uisng standard set theory $\mathsf{ZFC}$ (i.e., the Zermelo-Frenkel axioms, including the Asiom of Choice), find a set $x_0$ such that $\phi(x_0)$ holds, where $$\phi(x)\equiv (\mathsf{CH}\leftrightarrow x=\emptyset). $$ Here, $\mathsf{CH}$ is short for the continuum hypothesis.

You cannot solve this puzzle, i.e., you cannot exhibit any concrete set $x_0$ of which you can prove that $\phi(x_0)$ holds. Indeed, if you could exhibit such $x_0$, I shall take for granted that it is possible to at least decide whether $x_0$ is the empty set or not${}^1$ - otherwise I would refrain from saying that $x_0$ has been described in a sufficiently concrete way to call it a solution to the puzzle in the first place. Hence, we could ultimately prove either $\mathsf{CH}$ or its negation. But is is known that $\mathsf{CH}$ is independent of $\mathsf{ZFC}$, i.e., neither it nor its negation can be proved.

Puzzle II. Assume that puzzle I has a unique solution. Find it.

That's easy: the empty set. And apparently the additional assumption boils down to assuming $\mathsf{CH}$.

---

${}^1$ For those arguing that my postulate that it should be decidable whether $x_0$ is empty or not is a bit handwavy, we might try to fix this at reasonable cost. Using Gödel's methods, one can certainly formalize $\psi(x)\equiv$ "there exists a proof that $x=\emptyset$ or there exists a proof that $x\ne\emptyset$". Now use $$\phi(x)\equiv (\mathsf{CH}\leftrightarrow x=\emptyset)\land \psi(x)$$ in the puzzles instead.

Answer 9

Yes.

I have a sphere with a hole drilled through the centre. The length of this hole is 1 metre. What is the remaining volume of the sphere. ie. the 'Donut'

If you decide I'm honest and not sending you on a wild goose chase, then you can solve this without calculus in your head.

Answer 10

EDIT: I realise now that the example given doesn't require uniqueness to solve the puzzle, but I'll leave the example below for those interested.

I can give an example of a Sudoku where you can use uniqueness logic to get to a solution. However, uniqueness is not the only way to get to that solution, so this is probably not pertinent to your question.

The above is taken from http://hodoku.sourceforge.net/en/tech_ur.php, which describes "unique rectangles" in sudoku. The cell R2C2 "must be" 3, as if it were not, we would have a fatal rectangle of 89s, where there are two valid placements of 8s and 9s that have no bearing on the rest of the puzzle. If it's not a 3 then there are multiple solutions. If it is a 3 then there is exactly one solution. So it must be a 3, as there must only be one solution.

Answer 11

1. I am thinking of a number X. Find Y such that the square of Y is X.

2. What if I tell you there is only one such Y?