28
$\begingroup$

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.
$\endgroup$
10
  • 2
    $\begingroup$ Related: puzzling.stackexchange.com/questions/49557/… $\endgroup$ Nov 11 '20 at 16:56
  • $\begingroup$ I find this question very interesting! Maybe this will help: en.wikipedia.org/wiki/List_of_impossible_puzzles $\endgroup$
    – JKHA
    Nov 11 '20 at 17:31
  • $\begingroup$ It seems like this question is meant to be about what we call [grid-deduction] puzzles, so I've edited that tag in -- if that's not accurate, feel free to edit it back out. $\endgroup$
    – Deusovi
    Nov 11 '20 at 17:37
  • 1
    $\begingroup$ @Deusovi, maybe I'm wrong but I feel this question is more a question about meta on puzzles and does have little with grid-deduction tag. $\endgroup$
    – JKHA
    Nov 11 '20 at 17:38
  • 1
    $\begingroup$ Yeah, grid deduction isn't really what I'm going for. It's most often applied to those kinds of puzzles, but isn't specific to it. Maybe something like "logic-puzzles"? Dunno. $\endgroup$ Nov 11 '20 at 17:59

11 Answers 11

24
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Oooh, good counter example. Thanks :) $\endgroup$ Nov 11 '20 at 18:47
  • $\begingroup$ I'm no longer convinced that this works anymore. Consider it a different way: If we assume a unique solution, we can rule out that the addends do not include a "1": If one of them was a 1, the other addend could either be a 2 or a 3, making it not unique. So, the answer must be 2,2. $\endgroup$ Nov 13 '20 at 7:41
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$ Nov 13 '20 at 14:32
  • $\begingroup$ I guess this assumes that a solution can be validated by a computable function? Maybe for the puzzles we care about, a valid solution should be self-evident. Or, if we say a solution includes a proof of correctness (and is hence self-evident), then a proof by person 1 might use the assumption of uniqueness and person 2 would reject this proof. Another proof might (or might not) exist that doesn't use this assumption but we don't know if/when person 2 will find it by enumeration. $\endgroup$
    – tehtmi
    Nov 14 '20 at 23:46
10
$\begingroup$

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:

enter image description here

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'.

enter image description here

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.

$\endgroup$
13
  • 1
    $\begingroup$ "In the extreme case, you can enumerate all possible solutions". For slitherlink, and many other grid deduction puzzles, yes. For grid deduction puzzles filling in real numbers in boxes, no. $\endgroup$ Nov 11 '20 at 17:51
  • 1
    $\begingroup$ @SE-stopfiringthegoodguys I'm not familiar with any [grid-deduction] puzzles that allow arbitrary real numbers. If you know of any that do allow arbitrary real numbers (which can't immediately be whittled down to a countable set of numbers, and still have unique solutions), I'd be interested to hear about them! $\endgroup$
    – Deusovi
    Nov 11 '20 at 17:57
  • $\begingroup$ Here's a very boring one: Pick a function $f$ that maps two real numbers to a real number. On a grid with the clues being a real number for each row and column, fill in the grid such that cell_ij = f(rowClue_i,columnClue_j). (This puzzle does not qualify for OPs question though). $\endgroup$ Nov 11 '20 at 18:11
  • $\begingroup$ @SE-stopfiringthegoodguys Hm, fair enough. (Though I may argue that you can limit things to the computable reals -- it seems to me that if the solution has to be checked for correctness by an algorithm, the only allowable involved numbers would be the computable reals. And there are countably many of those.) $\endgroup$
    – Deusovi
    Nov 11 '20 at 18:15
  • 1
    $\begingroup$ @supercat Yes, but that's an additional constraint on the solution, not a "uniqueness" constraint on puzzle construction. It happens to look like a uniqueness deduction on a regular Sudoku puzzle, but this would be a variant rule added to the ruleset, so you'd still be making deductions solely from the rules. $\endgroup$
    – Deusovi
    Nov 12 '20 at 18:59
8
$\begingroup$

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

$\endgroup$
2
  • 3
    $\begingroup$ The solution is an integer, so there can be only 1 solution with n=1. $\endgroup$
    – Sleafar
    Nov 12 '20 at 18:48
  • 1
    $\begingroup$ I probably don't get it, given that this answer received so many upvotes, but to me the answer seems incorrect. If you do not add the assumption that there is a unique solution, you will still find the unique solution n=1 given that n is an integer (if n was not an integer, the answer could have also been infinity). $\endgroup$ Feb 6 at 13:31
7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Cheryl's Birthday was the first thing that came to my mind when I read the question! It's such an implicit assumption - that Cheryl has only one birthday - that it's sooooo easy to miss it. But the puzzle cannot be solved without it. $\endgroup$
    – Vilx-
    Nov 13 '20 at 13:56
3
$\begingroup$

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).

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
+50
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ Why is the center square any different than the left/right square? $\endgroup$ Nov 13 '20 at 18:15
  • $\begingroup$ @NathanMerrill By Tapa rules you can have no 2 by 2 fully shaded. If you shade one side, then the center cannot be shaded, but the other side may or may not be, giving multiple solutions. If the center square is shaded, both sides must be shaded, giving a "unique" solution in that sub case. $\endgroup$ Nov 13 '20 at 20:57
  • $\begingroup$ The other side can't be shaded, right? Because you can't create a loop. $\endgroup$ Nov 13 '20 at 21:07
  • $\begingroup$ Loops are OK in Tapa $\endgroup$ Nov 13 '20 at 21:47
  • 2
    $\begingroup$ @Deusovi I know we're quibbling about semantics, because I agree with you. But...there is a difference. On either side, whether it is shaded or unshaded, there are multiple solutions. But in the middle, unshaded leads to multiple solutions, while shaded leads to a "unique" solution. So of the six steps available to you, only one leads to a "unique" solution. So I can obviously not choose the cup of wine in front of me! $\endgroup$ Nov 14 '20 at 21:44
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ You can also solve it without the uniqueness assumption, but it is a lot more work. Let the radius of the sphere be $r$. You solve the problem with ordinary calculus and the $r$ cancels out. The solution you are thinking of is much easier, but this does not answer the question. $\endgroup$ Nov 13 '20 at 16:18
0
$\begingroup$

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.

an example highlighting a unique rectangle in a sudoku puzzle

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.

$\endgroup$
0
$\begingroup$
  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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.