I have the same experiences with Alcazar. Alcazar is essentially the problem of finding a Hamiltonian circuit, and now that it seems to be moribund, I'm wondering if anybody could re-implement it as an HTML5 app. It was a very cute game. On Tue, Jun 30, 2020 at 11:06 PM Cris Moore via math-fun < math-fun@mailman.xmission.com> wrote:

in theoretical computer science, UP is the version of NP where we are promised there is a unique solution. UP is intuively easier than NP, but there is a randomized reduction from NP to UP. In less abstract terms, there is a randomized process that turns satisfiable Boolean formulas into Boolean formulas with a unique satisfying assignment (with reasonable probability). Therefore, it is unlikely that UP is much easier than NP.

But more to the point: I love the game Alcazar (which no longer works on my computer, #$%^@$%&) and I did sometimes exploit the “promise” that the solution was unique. That is, if one choice would lead to more than one solution, or none at all, I reasoned that it would lead to none at all — and I took the other choice. The same thing comes up in Sudoku and its variants.

Some puzzle solvers regard this as cheating. I guess the question is whether the question is

. find the solution (using everything you know, including its uniqueness) or . find the solution, including a proof that it is unique.

- Cris

...

On Jun 30, 2020, at 8:50 PM, James Propp <jamespropp@gmail.com> wrote:

Does anyone know of a name attached to this problem-solving tactic?

Jim Propp

---------- Forwarded message --------- From: David Will <daw5de@virginia.edu> Date: Tue, Jun 30, 2020 at 8:17 PM Subject: Question about the self-referential aptitude test To: <jamespropp@gmail.com>

Dr. Propp:

Good evening. I know I'm a bit late to the party, but I just wanted to say I'm a big fan of your self-referential aptitude test, which I just discovered today. In the instructions, you mentioned this idea that the foreknowledge of the puzzle having a unique solution can, in and of itself, be used as a clue when solving the puzzle. I enjoy Japanese-style puzzles, and I've previously encountered this same phenomenon in games such as slitherlink and masyu. I'm also a graduate student in mathematics at the University of Virginia, so I've been curious about this idea from a mathematical perspective. I was hoping you'd be able to answer a quick question.

Do you know of a name for this phenomenon? I'm lacking in knowledge about game theory (is that even the right subject?), so I was unsuccessful in my searches online. I'd like to see if this phenomenon has been studied with any sort of rigor. In particular, I want to know if it would be possible to construct a puzzle that requires this logic in order to be solved (in some loose sense, ignoring brute-force guessing).

Thank you for your time. I'd greatly appreciate it if you'd be willing to entertain my curiosity.

Best, Andrew Will _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com

https://linkprotect.cudasvc.com/url?a=https%3a%2f%2fmailman.xmission.com%2fc...

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

On Jul 1, 2020, at 12:21 PM, Veit Elser <ve10@cornell.edu> wrote:

...

On Jun 30, 2020, at 11:06 PM, Cris Moore via math-fun <math-fun@mailman.xmission.com> wrote:

That is, if one choice would lead to more than one solution, or none at all, I reasoned that it would lead to none at all — and I took the other choice. The same thing comes up in Sudoku and its variants.

I’m not sure I follow. Perhaps you are using symmetry? For example, there are some (>1) symmetry-related choices and one other choice (not related by symmetry to the others). The promise of uniqueness then compels you to choose the odd-man-out.

Right. In Alcazar, for instance, you have to draw a Hamiltonian path through a chamber with obstacles, and there are often subchambers with multiple entrances and exits. If some entrance-exit pair would allow you to draw this path in two different ways, that must not be the right way to go.

There is a class of optimization problems where one knows in advance that the optimum is exceptionally good, either by human design (crypt problems) or natural design/evolution (proteins). Usually such problems have unique solutions (up to symmetry). For such problems I would think that optimization algorithms that do not take advantage of this information are suboptimal to ones that do.

Yes. As another example, the best known algorithm for SAT with unique solutions is faster than the best known for SAT in general (both exponential but the former has a smaller exponent). - Cris

-Veit

Cris Moore moore@santafe.edu The real danger is that such machines, though helpless by themselves, may be used by a block of human beings to increase their control over the rest of the race or that political leaders may attempt to control their populations through political techniques as narrow and indifferent to human possibility as if they had, in fact, been conceived mechanically. — Norbert Wiener