<p>I want a challenging Where's Waldo type game, where the goal is to find some pattern.
But I would want something where you can make your own puzzles, for example by randomly pulling your hand over a board.</p>

<p>Let me give an example.
Suppose that the board is a triangulated large triangle and every vertex is either red, blue or yellow, with the constraints as in Sperner's lemma.
(It shouldn't be too hard to fabricate such a board.)
Then after randomly assigning colors, it is challenging to find a rainbow triangle, since it is PPAD-complete.</p>

<p>The problem with this example is that the board needs to be huge to make it non-trivial, not to mention that for a random large board there would be many rainbow triangles, so in most cases it would be easy to find one.
I think one could reduce the board size by changing the solution from a rainbow triangle to something more complicated, like a given pattern of a dozen points.
It is important that I want the solution to be immediately verifiable, thus of constant size, so games like <em>find a 4-coloring of this planar graph</em> are ruled out.</p>

<blockquote>
  <p>So is there some nice TFNP result that would give such a puzzle?</p>
</blockquote>

CC BY-SA 4.0
2020-02-01T00:22:35.570Z
If the solution is of constant size, say size $c$, and you can verify it in polynomial time, then you can find a solution in polynomial time by exhaustively enumerating all $2^c$ possible solutions.  So I suspect you probably don't literally mean *constant size*.  Perhaps [edit] the question so it isn't trivial?
D.W.
CC BY-SA 4.0
2020-02-01T06:54:01.667Z
The size of the board is $n$, so there are $\binom nc$ possible solutions, which can be quite large. Of course usually not any $c$ fields can form a solution, but the point is that this also depends on $n$.
domotorp
CC BY-SA 4.0
2020-02-01T19:35:35.057Z
That's still solvable in $O(n^c)$ time, which remains polynomial.  So I am not understanding what your question is.  (It's also not a constant-size solution; it takes $O(c \log n)$ bits to encode the solution.)  Are you looking for concrete parameters where this is hard, in concrete running time rather than asymptotic running time?  What counts as "challenging"?  Actually I notice you haven't really given any explicit requirements on how hard the puzzle must be to solve.  So what are your requirements?
D.W.
CC BY-SA 4.0
2020-02-02T20:34:39.000Z
You're absolutely right in that this is not a well-defined question and the answer can be subjective.
domotorp
<puzzles><board-games><ppad>
Generating Where's Waldo?
domotorp
# Generating Where's Waldo?

(Asked by: username_0 on 2020-01-31)

I want a challenging Where's Waldo type game, where the goal is to find some pattern.
But I would want something where you can make your own puzzles, for example by randomly pulling your hand over a board.

Let me give an example.
Suppose that the board is a triangulated large triangle and every vertex is either red, blue or yellow, with the constraints as in Sperner's lemma.
(It shouldn't be too hard to fabricate such a board.)
Then after randomly assigning colors, it is challenging to find a rainbow triangle, since it is PPAD-complete.

The problem with this example is that the board needs to be huge to make it non-trivial, not to mention that for a random large board there would be many rainbow triangles, so in most cases it would be easy to find one.
I think one could reduce the board size by changing the solution from a rainbow triangle to something more complicated, like a given pattern of a dozen points.
It is important that I want the solution to be immediately verifiable, thus of constant size, so games like *find a 4-coloring of this planar graph* are ruled out.

> So is there some nice TFNP result that would give such a puzzle?

**Tags:** puzzles, board-games, ppad
> **Comments:**
> **username_1**: If the solution is of constant size, say size $c$, and you can verify it in polynomial time, then you can find a solution in polynomial time by exhaustively enumerating all $2^c$ possible solutions.  So I suspect you probably don't literally mean *constant size*.  Perhaps [edit] the question so it isn't trivial?  
> **username_0**: The size of the board is $n$, so there are $\binom nc$ possible solutions, which can be quite large. Of course usually not any $c$ fields can form a solution, but the point is that this also depends on $n$.  
> **username_1**: That's still solvable in $O(n^c)$ time, which remains polynomial.  So I am not understanding what your question is.  (It's also not a constant-size solution; it takes $O(c \log n)$ bits to encode the solution.)  Are you looking for concrete parameters where this is hard, in concrete running time rather than asymptotic running time?  What counts as "challenging"?  Actually I notice you haven't really given any explicit requirements on how hard the puzzle must be to solve.  So what are your requirements?  
> **username_0**: You're absolutely right in that this is not a well-defined question and the answer can be subjective.  

---

## 0 answers

