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