Hello guys,
I'm trying to solve the game with a simple recursive backtracking algorithm, but after level 60+ it became terribly slow. I couldn't come up with any idea on optimizing the algorithm. I made a sudoku solver with the same technique and there I could select the path by selecting the branch with the lowest subbranches. Is there anyway I could do this with mortal coil game?
Thanks in advance.
optimizations
Hi badZeppelin,
I'm not sure that choosing a branch based on which has the fewest sub-branches is workable. As the levels become larger the number of possibilities is immense, the CPU grunt needed to enumerate them all would be considerable. It would of course depend on how many levels of sub-branches you explored though.
It wouldn't hurt to give your idea a try though, even if it doesn't work you'll learn something new about why it doesn't work and how this type of problem can best be analysed.
If it doesn't work for Mortal Coil you should definently try that approach on the One Of Us puzzle. Choosing the option with the fewest branches maximizes the options that are available further down the path and can be quite effective for Hamiltonian path problems.
Try doing a few levels of Mortal Coil by hand and see if you can work out how to tell when a solution isn't viable. Then try and apply that to your algorithm to prune unworkable branches and shrink the solution space.
Good luck, hope I haven't steered you too far wrong.
I'm not sure that choosing a branch based on which has the fewest sub-branches is workable. As the levels become larger the number of possibilities is immense, the CPU grunt needed to enumerate them all would be considerable. It would of course depend on how many levels of sub-branches you explored though.
It wouldn't hurt to give your idea a try though, even if it doesn't work you'll learn something new about why it doesn't work and how this type of problem can best be analysed.
If it doesn't work for Mortal Coil you should definently try that approach on the One Of Us puzzle. Choosing the option with the fewest branches maximizes the options that are available further down the path and can be quite effective for Hamiltonian path problems.
Try doing a few levels of Mortal Coil by hand and see if you can work out how to tell when a solution isn't viable. Then try and apply that to your algorithm to prune unworkable branches and shrink the solution space.
Good luck, hope I haven't steered you too far wrong.
-
badZeppelin
- Posts: 2
- Joined: Wed Dec 23, 2009 1:07 pm
