Here's another thought: Conway's soldiers problem (https://en.wikipedia.org/wiki/Conway%27s_Soldiers) shows how one can use certain sorts of numerical monovariants to show that some Hi-Q problems can't be solved. Generalizing, let H be the set of holes, define a "position" to mean a subset of H, and call a function f from H to the reals "useful" if, for all positions A,B such that a single jumping-move turns A into B, we have sum_{h in A} f(h) greater than or equal to sum_{h in B} f(h). I call such a function "useful" because it's useful for proving that certain positions can't be reached from other positions. Specifically, if A and B are positions and there exists a useful function f such that sum_{h in A} f(h) < sum_{h in B} f(h), then B cannot be reached from A. Now, given a fixed B, define the "backward cone" of B to be the set of all A such that sum_{h in A} f(h) is greater than or equal to sum_{h in B} f(h) for *all* useful functions f. It's easy to show that if B is reachable from A, then every path from A to B stays in the backward cone of B. My proposal is, the heuristic "Never leave the backward cone of the position you're trying to achieve", if rendered concrete, might make it much easier to solve the puzzle for specific cases like the Hi-Q board (even though the NP-hardness result tells us that this approach is doomed to failure for boards in general). Given that Conway invented the soldier's problem, I'm guessing that the Berlekamp-Conway-Guy book "Winning Ways" explores this approach to Hi-Q, but I don't have my copy handy. Jim On Sat, Mar 14, 2020 at 10:32 PM James Propp <jamespropp@gmail.com> wrote:
I can't think of one but I also can't think of a reason why such a puzzle can't exist.
Jim
On Sat, Mar 14, 2020 at 9:14 PM Cris Moore via math-fun < math-fun@mailman.xmission.com> wrote:
Consider the set of all vectors that look like (-1, -1, 1), surrounded by zeros, and rotations of this. Each such vector corresponds to a hop.
Then if I understand you correctly, a fractional solution would be one that writes the difference between the initial and final states as a linear combination of these vectors with nonnegative coefficients, and a real solution is one where these coefficients are all 0 or 1. (We also need to be able to order these so that no coordinate ever becomes less than 0 or more than 1.)
Can you think of a Hi-Q puzzle that has a fractional solution but no real solution?
- Cris
On Mar 14, 2020, at 1:25 PM, James Propp <jamespropp@gmail.com> wrote:
Thanks, Cris. I didn’t know that it was NP complete (it’s possible that I once knew and then forgot).
What if one allows fractional moves? Equivalently, what if one is allowed to have multiple pegs occupying the same spot, and at any stage you’re allowed to replace every remaining peg by n pegs, for whatever n you choose? That might make the puzzle more tractable.
Alternatively one might allow “negative pegs”.
If one allows fractional *and* negative pegs, then the puzzle just becomes linear algebra and surely is in P, but this variant doesn’t seem to be very playable, at least not with the original physical instantiation of the puzzle.
Another direction might be to pick a cute mathematical structure and then choose the rules of play accordingly. That’s what I did when I designed Swine in a Line:
https://www.google.com/amp/s/mathenchant.wordpress.com/2017/07/17/swine-in-a...
I’m reminded of Lights Out, which also uses linear algebra, but over the field with two elements.
Any thoughts?
Jim
On Sat, Mar 14, 2020 at 1:57 PM Cris Moore via math-fun < math-fun@mailman.xmission.com> wrote:
I’m sure you know that on general board’s it’s NP-complete. On one-dimensional boards (which most children would probably find boring) it’s in P (see a paper by David Eppstein and me).
My favorite thing to do was play it backwards… you can also do a two-player version where the first person to get stuck loses.
- Cris
On Mar 14, 2020, at 11:53 AM, James Propp <jamespropp@gmail.com>
wrote:
I bought a vintage Hi-Q set for my family a few weeks ago:
https://en.wikipedia.org/wiki/Peg_solitaire
Now that I'll be spending lots of time at home with my kids, I'm
thinking
that there should be some good activities we could do with it.
Any ideas?
I know that Berlekamp-Conway-Guy has a section on this, and maybe it even explains how to win, but I don't want to just see the answer; I'd like a "curriculum" that'll Socratically guide me and my kids towards the solution. (Or is it the sort of puzzle where you basically need to use a brute-force approach?)
I kind of like the fact that I don't know the solution; it puts me and my kids more on the same level.
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun