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
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
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
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
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
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
The initial state and final state of Hi-Q both have D_4 symmetry. Are there solution paths that more or less preserve this symmetry along the way? Jim Propp On Sat, Mar 14, 2020 at 10:50 PM James Propp <jamespropp@gmail.com> wrote:
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
Here's an alternate way to play. Two people alternate adding one peg to an initially empty board. Your goal as a player is to make sure the puzzle can always be solved...that is, it is possible to jump pegs until there is just one peg left on the board. In effect you are both constructing a puzzle. So the first peg can go anywhere, and the second peg must go next to the first peg, the third peg need not be directly adjacent to the first two. At any point you can, instead of taking your turn, challenge the other player to solve the puzzle. If they can, you lose. If they can't you win. If you try this game, let me know how it plays. I invented this style of play as an alternate activity for the Rush Hour pieces, but it should work fine for peg solitaire. I suspect you'll want to put an upper limit on the number of pegs, cuz the game gets really hard really fast. Scott On Tue, Mar 17, 2020 at 5:22 PM James Propp <jamespropp@gmail.com> wrote:
The initial state and final state of Hi-Q both have D_4 symmetry. Are there solution paths that more or less preserve this symmetry along the way?
Jim Propp
On Sat, Mar 14, 2020 at 10:50 PM James Propp <jamespropp@gmail.com> wrote:
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
math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
For the classic, "perfect win", you must end up with a single peg in the center hole. This configuration is the complement of the starting position, in which there are pegs in every hole *except* the center. An interesting (and useful) observation is that a valid move (a jump) is the same running backwards and forwards if you complement the board: X X O -> O O X Complement and time-reverse: O O X <- X X O This means that if you write a solution finger that searches for solutions, keeping track of configurations it's seen, you can stop at the halfway point. When you reach that point, simply see if you've encountered the complement of the position. If so, you can piece the two together to form a complete solution. I coded this back in the mid-80s, and even with the speed and memory limitations of the time, it was able to solve it very quickly (there are many, many solutions). Tom James Propp writes:
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
That's a cute trick! I think what I'm looking for is an arsenal of such tricks that turn solving Hi-Q into more than a test of patience and/or programming prowess. Jim On Sat, Mar 14, 2020 at 6:58 PM Tom Karzes <karzes@sonic.net> wrote:
For the classic, "perfect win", you must end up with a single peg in the center hole. This configuration is the complement of the starting position, in which there are pegs in every hole *except* the center.
An interesting (and useful) observation is that a valid move (a jump) is the same running backwards and forwards if you complement the board:
X X O -> O O X
Complement and time-reverse:
O O X <- X X O
This means that if you write a solution finger that searches for solutions, keeping track of configurations it's seen, you can stop at the halfway point. When you reach that point, simply see if you've encountered the complement of the position. If so, you can piece the two together to form a complete solution.
I coded this back in the mid-80s, and even with the speed and memory limitations of the time, it was able to solve it very quickly (there are many, many solutions).
Tom
James Propp writes:
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
participants (4)
-
Cris Moore -
James Propp -
Scott Kim -
Tom Karzes