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