Home » blogs » quadricode's blog

First Post, General Puzzle Solving

Submitted by quadricode on Fri, 09/19/2008 - 02:51.
Hello.

A quick introduction: I'm Robert Smith, I'm 18, and I live in the US. I used to be quite into speedcubing, starting around 2003, but I have since moved into the more "theoretical" aspects of the cube. I also like mathematics, and, fortunately, programming. Anyway, that's that.

I have been writing a "general puzzle solver," whose goal is to be able to solve any (permutation) puzzle with (almost) any method. Quite quickly, we see there are definitely limits to this (e.g., we couldn't solve any scrambled 10x10x10 cube in a single phase). But, if some certain requirements are met, solving any puzzle should be an ability with this program.

I am actually designing it to be a "speedcubers' toolbox." I want it to be the first and last stop to finding a good algorithm for speedsolving puzzles. But, nonetheless, it could be used for analysis as well, and I am designing it with speed in mind.

The program was inspired by Kociemba's algorithm, Thistlethwaite's algorithm, Jelinek's (J)ACube, Krig's ksolve, and Reid's optimal cube solver. Also, Pochmann's thesis on his "Hume" program, Jaap (considering I probably incorrectly spelled aforementioned names, I won't try to spell his last name), Singmaster, and Longridge provided some ideas and mental motivation for the program. So, I hope the list of inspirations maybe gives some credibility to this project of mine; I am not just making a program that would attempt to solve a cube in O(n!^3) amortized time. ;)

Anyway, writing the program has been well underway for a while now, and I have a clear road-map of what I plan on doing and getting done. Here are some plans for the first release, though they are by no means any sort of guarantee:

*Puzzle specification via a definition file
-structure (piece names, orientation/permutation, ignored pieces, equivalent pieces (e.g., 2-color cube)
-possible moves (names and effect, uses cycle notation -- which is much less cumbersome than using ordinary "permutation index" notation)
-replicators (name and effect, e.g., P2 = twist move P twice)
-invalid following moves (an assumption is made that a move cannot be followed by its inverse)

*Method specification via a definition file
-specify for which puzzle the method is for
-specify possible turn metrics with names (moves could be weighted if need be, e.g., an R move is better and physically less costly than a B move)
-specify steps, which include which metric to use, and the goal state (ignored pieces/orientations/permutations allowed)

*'Automated heuristics' (heuristics are dynamically generated at runtime)

*Cross-platform support (it is written in C/C++)

Many of these have been implemented already (like all datastructures, file parsing, etc.). There are also of plenty future goals, such as solving every state under certain conditions, and outputting tables in HTML with associated cube images; or fast genetic algorithms.

The program is called 'qsolve', sort of like 'ACube' and 'ksolve'. I have not decided if the program will be open source or not. However, it will be free for personal use, of course. Also, it will come with documentation more sophisticated than a README.TXT, as well as some puzzle/method definition files.

Anyway, I thought now was an appropriate time to "make an announcement", and I'd be interested in hearing general questions and maybe some suggestions/comments/proposals/etc. Especially from the people here, who've done very good work. :D

Take care,

Robert
» quadricode's blog | login or register to post comments

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

A generic puzzle solver is a

Submitted by anubis on Fri, 09/19/2008 - 06:57.
A generic puzzle solver is a great idea - one that I've had for a while and even created one myself as a proof of concept, although I haven't had time to work on it and improve it. When I saw that Pochmann had also created one and now another one is out there as well, I decided to share my thoughts. First, I'd like to warn you that my solver is SLOW and can run out of memory and I haven't gotten around to improving it. It isn't based off of any other solvers out there and takes a very naive approach to solving the puzzle and I've only tried it using a 2x2x2 (which it can't solve anything more than ~7 moves from solved on a semi-modern PC due to memory/time) - so don't expect much out of it ;)

Rather than go into details explaining my simple code, I'm just going to explain a few of the odd bits. While it is very simple to extend the code to use what you referred to as replicators above (in fact, my original implementation did this), I instead store each different variation on a move (:u, :u2, :uprime) in it's totality in order to speed things up and keep the code simple. Also, you'll notice a few oddities in the solver. The first of these is that I limit the number of moves I try to 6 - this is just to keep the code from going on too long. The second is the way I check for solved which could definitely be improved. Because my internal representation of the puzzle does not try and rotate itself to any predefined state, I needed something quick and simple that could tell me whether the puzzle was solved - and my solution was to use a regular expression to reduce the current permutation of stickers to the number of runs of the same sticker - by controlling how the puzzle is configured this means that (at least in simple puzzle cases) it is solved when the number of runs = number of sides (this shouldn't be hardcoded, but I was lazy :p)

If you are aiming to create a true generic solver, here are some of the fun puzzles you are going to have to think about - shape-shifting puzzles, supercubes, bandaged puzzles (including the Square-1 of course), and things like this: http://twistypuzzles.com/forum/viewtopic.php?f=9&t=10684

Good luck! Feel free to ask any questions about my less-than-perfect code :p - http://www.overthemonkey.com/generic-solver.tar.gz
» login or register to post comments

Hehe, very cool, thanks for s

Submitted by quadricode on Fri, 09/19/2008 - 14:54.
Hehe, very cool, thanks for sharing. Obviously there are many, many improvements that could be made. And I know you know that. But it was short and simple. :}

Along with speed, I am keeping memory in mind, as that is almost more important than speed. Since the intended use of the solver will be for "regular computers" (I understand that, that is relative), I can't fill the RAM with a 5TB table, obviously.

Also, all moves will be "precalculated," meaning that the replicated moves will be determined (as if the move was just a single move) at runtime, since it could get impractical to apply repeated moves several times.

Anyway, thanks again.

Robert
» login or register to post comments

Good luck on this project

Submitted by Bruce Norskog on Sun, 09/21/2008 - 13:29.

I think this is a highly ambitious project. I think you will find that you will have to make some compromises from what you are hoping to achieve. But I'll encourage you to keep at it and see what you can accomplish. I'm sure there is room for improvement over existing general puzzle solvers.

Getting good performance in terms of solution length and speed for a program hard-coded for a specific puzzle can be difficult enough, even using fairly large amount of memory. Trying to get similar performance for a user-defined puzzle, particularly complicated ones, I believe is very difficult to achieve. It appears to me that existing general puzzle solvers (ksolve, Hume) are very limited in their ability to solve large/complicated puzzles.

You didn't mention use of symmetry reduction. This can be greatly beneficial in reducing memory and increasing execution speed. But it would definitely add some complexity. I am guessing it might be quite difficult to determine what symmetry reduction can be used for each method step automatically. It might need to be specified as part of the puzzle definition and/or method definition. But it's probably necessary I would think to compete in performance and memory usage with some of the other solvers.

Given your age, I assume you haven't taken a course in abstract algebra (including group theory). You should at least read up on group theory, particularly as to its relation to permutation puzzles (if you haven't already). Jaap's site has such a brief group theory tutorial.

I have also been working on a general puzzle solver of sorts. Its focus is on doing breadth-first searches (or what I like to think of as God's algorithm calculations) so I think it is quite different from what your program is attempting to do. My project is pretty much on hold at the moment for lack of time and something I am giving higher priority to. Right now, it is using polymorphism with one base class for defining a puzzle, and another base class for controlling how the analysis is done. So new code needs to be written and compiled into the program in order to do a new analysis. I would like to eventually allow it to carry out analyses for at least relatively simple puzzles without having to add code into the program itself.

» login or register to post comments

It is quite ambitious, I agre

Submitted by quadricode on Sun, 09/21/2008 - 18:04.
It is quite ambitious, I agree. I have been working on it for a while (more extensive planning than actually writing code [blindly]), and I do see the difficulty in making a solver able to solve bigger and more complicated puzzles.

I was thinking a lot about symmetry reduction. It could, and probably would, be very beneficial. As of now, it isn't a priority, per se, because I am not entirely sure how I would implement it.

Without being modest, I have studied a lot of math, and do so often. I'd like to say I know more than people my age. And, no, I did not find it at all offensive or demeaning about your assumption, since it is, actually, a good one.

Anyway, since I like permutation puzzles, abstract algebra and group theory have been particularly interesting to me. Actually, I dipped my toes in it when writing an efficient number-theoretic transform (like an FFT, but does convolution in Z/pZ for certain primes p. This is especially useful when an FFT presents round-off error for very large signals.) for my "bignum" routines a few years ago.

I was actually thinking about implementing some group-theoretical algorithms in the program, to calculate certain things like the size of a group given certain generators (specifically, moves). Such numbers could help determine the feasibility of a provided solution, I guess.

Oh, by the way, your 4x4x4 solver information was interesting.
» login or register to post comments