One feature of all these puzzles is that if you treat the tiles as indistinguishable, there's no way to lose; EVERY sequence of explode operations will take you to the same end state, and in the same number of moves every time! This is called the confluence property of the abelian sandpile mode (though some people call it "the abelian property", which I think is a mistake). Jim On Thursday, July 21, 2016, Tom Rokicki <rokicki@gmail.com> wrote:
This puzzle appears to be mostly dominated by shape; the flexibility on explode means that from a given shape you can often get the ordering you need easily.
The eccentricity of the state graph from the goal state appears to be equal to or close to that of just the shape graph (the same puzzle but completely ignoring letters and numbers). For odd sizes, the hardest shape is a single centered vertical stack. At n=9, the hardest position both just considering shape and considering both numbers and shape is a single centered vertical stack (I'm somewhat surprised this is harder than just the reversed numbers). The distance from goal is 30.
Contrast n=5, where the hardest shape is the centered stack with a distance of 5, but the hardest position is (5,4,3,2,1) with a distance of 8 (or two other related positions).
I believe iterated depth-first search with the two separate heuristics, one by the shape, the other by the sum of the distances of the numbers from their homes, will give you an optimal solver that works pretty well.
On Thu, Jul 21, 2016 at 4:58 PM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
If you sum (with multiplicity) the squares of the positions of the tiles, and divide by 2, you get a quantity that goes up by 1 when you explode and goes down by 1 when you unexplode. (To check this, note that if you subtract a^2+b^2 from (a-1)^2+(b+1)^2 you get 2+2a-2b, which equals 2 if a=b and equals -2 if a=b-2.)
This gives us an easy way to compute par, *if* there's a way to get from the initial state to the final state without using any unexplode moves. Most of the puzzles can be done without using any unexplode moves.
This analysis also tells us that you can achieve 0 over par, 2 over par, 4 over par, ... but not 1 over part, 3 over part, 5 over par, ...
The only unfailing algorithm I know for these puzzles is brute force.
Jim Propp
On Thu, Jul 21, 2016 at 7:10 PM, Paul Palmer < paul.allan.palmer@gmail.com <javascript:;>> wrote:
Very interesting.
After playing a couple dozen games, I seem to be able to consistently get "0 over par", although I don't have a conscious strategy.
How does it determine 'par'? Does it have an algorithm for a solution?
On Thu, Jul 21, 2016 at 1:43 PM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
I have an idea for an app that a friend of mine has implemented in CSS: http://mathenchant.org/chipchip/ I’d be interested in people’s comments. Is it fun to play? Are the directions clear?
I’m aware of glitches in the implementation (some of which are browser-specific or platform-specific), and do let me know about them, but those are of secondary interest; what I really want is ideas for making the app more fun, and (from those of you with some relevant experience) a sense of whether the game has commercial potential.
The page runs on laptops and smartphones. If the boundaries between tiles aren't clear, try a different browser (and let me know about the issue).
ChipChip started out as a math game, but James Tanton pointed out that there’s a much bigger market for anagram-syle word-games. So you can play in either Number Mode (the goal is to sort the numbered tiles into ascending order) or Word Mode (the goal is to spell a word). I specifically chose words with no repeated letters; do you think it would be more fun if I dropped this constraint?
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun