I’m planning to try to write a Rubik’s cube solver, or rather a few tools towards one. One goal is to have a program that can breadth-first search moves from a given arrangement to reach another arrangement. That’ll probably take a significant amount of optimization to allow it to run quickly and efficiently in memory, but to be able to get that working I need a computer model of a Rubik’s cube.
This weekend I put together a Rubik’s cube simulator and a command line interface to allow interaction:
Well, this was supposed to be where I pasted the log of console output of manipulating the cube, but the formatting depends on a uniform-width font and maintaining whitespace, neither of which actually worked when I pasted it. Here’s a screenshot:
It’s still having some issues, but the example sequence I chose doesn’t show them. I also only implemented (almost) the entire set of moves that are valid on a 2-cube, but didn’t try to use any 3-cube specific moves in that sequence. Once I’ve got the last few bugs worked out of that set extending it to n-cube size is just a matter of defining the moves for that size cube puzzle as an extension off the base 2-cube moves. I was planning to have that finished tonight, but I was distracted (see my previous post) and had to settle for just finding the test cases that it fails. Didn’t have time to put them in unit tests, but if they give me enough trouble I might bother with that.
In other news, I wish I’d looked up the problem of representing a Rubik’s cube as an object before I started. I couldn’t think of a way to represent the puzzle in a way that would make manipulating it easy, so I took the approach that I’d store the data in an easily extensible form (arrays of size n*n where n is the size of the cube) and put all the logic to make it work in the code that manipulates the puzzle. This approach (from 1986) flips it around, but the end solution looks a lot simpler than mine. The way I have mine written is easily extensible to larger cubes, but done right I think that approach could be also. Since mine is almost finished I’ll get it working on the 2- and 3-cubes, then I’ll probably put together a 2-cube using that approach and see if it’s actually as simple as it looks (I don’t know APL, but I know what it’s trying to do).
At least my interface is very similar, though there aren’t all that many reasonable ways to represent a cube in ascii, and my input accepts standard cube notation, unlike his. Looking at the other search results it’s surprising that the first Google hit exactly solved one of my problems (that I’d already worked around less elegantly) when all the rest are just software puzzles, not computer science.