As long as I’ve had Ricochet Robot, I’ve thought about how neat it would be to have a computer program that would solve those puzzles that seem a bit too hard for the humans to solve.
Well, now I have one.
I’ve been studying Data Structures and Algorithmics lately in the University and I’ve learned the ways to do such things, so I decided to code the program. I started yesterday, coded for few hours and ended up with something that quite didn’t work: a recursive solution. As Ricochet Robot puzzles have no real end, you can keep on moving the robots as long as you wish, this kind of depth-first solution is no good. I thought I had a better solution to the problem, but obviously I had forgotten it.
Well, today it came back to me as I was walking to my Algorithmics exercises, I sketched it in pseudocode while waiting for the exercises to begin and now it works. Well, the program is a bit limited as it only supports one board configuration right now, but that’s just fine detail. The main thing is that it counts each and every move, each level at a time until it finds a solution.
There’s one problem — it’s a bit slow. Even though it works approximately 10.000 solutions per second, it’s still very slow, because there are literally thousands of moves. Just watch how the amount of moves piles up on each level: 15 -> 255 -> 3503 -> 40735 -> 403055 — and that’s all I know, because the program’s still counting… Oops, now it stopped, as it ran out of memory. All this, and it was only counting solutions five moves deep!
So, there’s still work to do before computer beats humans in Ricochet Robot, but maybe if I just had more powerful computer (perhaps I should try this one on the University unix machines … or maybe not).
2 responses to “Ricochet Robot solver”
You may not actually be running out of memory, but just overflowing the stack. In that case you can revise your solution to use iteration instead of recursion. Of course you *will* run out of memory eventually, but you should be able to go deeper than 5 levels by not using recursion. Good luck and post a demo!
You can download a ricochet robots solver here : http://ricochetrobots.fr.st