Zach's Projects

How's that different from not-so-super Marble Jumper?

9x9 vs. 7x7

It's a much greater challenge too. My Pentium 4 system couldn't solve the full 9x9 marble puzzle in 12 hours with simple backtracking. The original 7x7 puzzle only takes a few seconds. Part of why it is taking so long to program is I am trying to find a faster way to solve larger puzzles. It is well documented that the 9x9 has a solution, but I want to create other puzzles too.

It's a much greater challenge too. My Pentium 4 system couldn't solve the full 9x9 marble puzzle in 12 hours with simple backtracking. The original 7x7 puzzle only takes a few seconds. Part of why it is taking so long to program is I am trying to find a faster way to solve larger puzzles. It is well documented that the 9x9 has a solution, but I want to create other puzzles too.

 

I suspect your primary difficulty probably lies in the fact that there are often many possible sequences in which any given set of jumps could be performed. What I would suggest doing is modifying your depth-first search so that once you've evaluated a possible move (e.g. #9 jumps over #10 into #11) and found it fruitless, you mark the two pegs so that you do not consider the move again unless or until something happens to one of those pegs or the void at #11. Unless peg #9 or #10 is moved, or something moves into and out of #11, the position after doing some other moves and then having #9 jump over #10 will be the same as the position one would have if one had #9 jump #10 and then did the other moves. Since the position will have already been evaluated, there's no reason to evaluate it again.

 

I'm not sure if it's actually in practice necessary to worry about #11. To be sure, if a sequence of moves jumps into and out of #11, it would not be possible to perform that particular sequence of moves in that order if one had #9 jump #10 first, but I would expect that one could in every meaningful case swap the moves jumping out of #11 and jumping in. The only time that wouldn't work would be if jumping into #11 is what made it possible to jump out of #11. Such positions can be drawn up, I think, but I don't know if any such positions are winnable.

 

In any case, even if moving a piece into and out of #11 forces you to reconsider having #9 jump #10, there should still be many fewer cases to evaluate than there would be without such pruning.