# New puzzle solver



## Sébastien.felix (Jul 10, 2008)

Hi all, 
I'm working on a puzzle solver which can be adapted for EVERY puzzle. I add many options like ignore pieces, just consider orientation, just consider permutation, determine the allowed locations for a piece after an alg, select restricted moves.

I would like to know if anyone see another options that would be cool, for any kind of puzzle?

This solver is created to have 2 modes :
1-compute single algs
2-compute entire sets of algs(like OLLs, PLLs, 4*4*4 PLLs with parity...etc)

The 2nd mode of the solver will probably need to use "shared calculus" to be efficient.

So if anyone has any idea to make this program better, i'm open to every idea!

Thanks everybody

Sébastien


----------



## JBCM627 (Jul 10, 2008)

*Every* puzzle? So everything from Square-1 to Megaminx? And other puzzles, like domino cubes, or even Magic? I am curious how you would implement this; would you let the user define their own puzzles, or what?

Also, will it have only an optimal solver, or will you include a multi-phase solver like Cube Explorer that will create solutions quickly, as opposed to optimally?


----------



## Sébastien.felix (Jul 10, 2008)

For each puzzle I have to set up the program, but when its done, its done forever. I can configure it for all n*n*n cubes, megaminx, pyraminx, sq1 needs a little modification but it works. I can let users define their own puzzle but only when my program will work(in fact I do it with the collaboration of 2-3 other cubers).
Now i just configured it to find the optimal sequences, because I created it to be a "speedcubing" solver, I mean that it will find speedcubing's algorithms. The quickness of the alg wasn't one of my goal. The program will be relatively fast, but not as quick as ACube or Cube Explorer. My goal was to create the more complete program i could.


----------



## JBCM627 (Jul 10, 2008)

Sounds like a great idea. Would it still be possible to implement an N-phase solver? You can probably let the user define what move groups to restrict the solver to in each phase.

This could also come in handy if you wanted to restrict moves in general... such as, if you wanted to allow moves on F R and U faces only, to solve a certain position.

This will be nice to have though. Perhaps include a scramble option to generate a scramble instead of a solve?


----------



## Kare (Jul 11, 2008)

I have built a somewhat general solver where the user may model puzzles in a text-file. The big things I have been missing myself are

* Separation steps, ie top edges at the top and bottom edges at the bottom but not solved.

* Multi-phase solving. For big puzzles the numbers of positions to search is way to large to find optimal solves. 

* Your mode-2, letting the program generate all possible cases would be wonderful.

* Puzzles where the possible twists depend on the position. Square-1 is one example of this, so is the bandaged cube. My solver can do this, but does so in a really uggly way and is to slow for square-1.

* Error messages. Check all data given by the user for all errors you can imagine. Its not fun to code, but modeling puzzles is hard and finding the misstakes by hand is even worse.

Making the program able to take advantage of all ram present in the machine might be usefull for large puzzles where you need to use pruning tables that are not complete. Multi-core processors are quite common and this problem should not be to hard to parallelize. And talking about parallelization, for even bigger problems it might be usefull to be able to distribute the computation over multiple computers. In its most primitive form this could be done by generating sets of possible solutions to try and then distributing the sets manually to you friends. But grid-computations is of course of low priority, speed will come from good algorithms not computing power.

For practical speedsolving purposes the problem with large puzzles can sometimes be avoided. Mitchell Stern managed to find really nice LL-algs for the megaminx using the restriction that only three sides could be turned. Having the ability to just tell the program to disallow some twists would be much more convinient than treating it as a separate puzzle. (note: with three sides allowed a megaminx dont have 20 corners, just 10 or 11, this makes tables of all permutations and orientations possible)

For those of you who want to try my program it can be downloaded at www.svekub.se/files/ksolve.zip and source (probably useless for anyone but me) at www.svekub.se/files/ksolvesrc.zip


----------



## Sébastien.felix (Jul 11, 2008)

My solver uses matrix, complex numbers and group theory(very basical things), and my job was just to find a way to represent any puzzle, and to determine how to check the datas, the algorithm won't be a brute force one but we're not looking for a quick answer, just for the most efficient one. We will distribute the computation to many computers(in fact the most we can) in order to compute the datas the fastest we can...
With the representation I use, separation steps are easy to determine. But i didnt program the SOLVING algorithm, just the testing algorithms with my representation.
I'm actually still working on my mode-2(on the algorithm who can determine the number of cases).

For errors, I can check them for all n*n*n cubes. But i dont know many things about megaminx and pyraminx(i need to study megaminx a little to find the restrictions).
And of course i will restrict the twist you can use, to find the best algs in each sub-group(like Rw/R/U OLLs, Rw/R/U/F OLLs...etc). Same thing for bigger cubes, so the computing part won't be too long.

Anyway i'm open to any kind of collaboration. I've always find nice if we could find enough people to work on it, because such a solver(mode-2 : this mode will generate entire sets of algs in many sub-groups) would be a very nice improvement for all puzzle solvers.
Is there a place where I can dialog with some "cube solving algorithms coders" to exchange some ideas?

have fun

sebastien


----------



## Johannes91 (Jul 11, 2008)

Sébastien.felix said:


> Anyway i'm open to any kind of collaboration. I've always find nice if we could find enough people to work on it, because such a solver(mode-2 : this mode will generate entire sets of algs in many sub-groups) would be a very nice improvement for all puzzle solvers.


Start an open source project, perhaps? Depending on the language(s) used, there might be many people willing to contribute. I've talked with quite a few people who are interested in writing puzzle solvers.



Sébastien.felix said:


> Is there a place where I can dialog with some "cube solving algorithms coders" to exchange some ideas?


Well, many programmers read this forum. There's also Domain of the Cube Forum.


----------



## Sébastien.felix (Jul 14, 2008)

Hi all,
After having worked on my solver, now I can do separation steps, I can solve using a N-phase solver(but i need to configure manually each subgroup of moves (like <F2/B2/R/L/U/D>)). My mode-2 is operational, and I can solve puzzle with restricted moves(like square-1). I can also check orientation or permutation errors.

I can solve the cube using brute-force, N-Phase solver or another way of solving very promitting.

Thx Kare for telling me what to check.

For N-Phases solver, i would like to know which subgroups would be usefull. I have already configured all groups of Human Thistlethwaites Algorithm plus <R/U/D>,<R2/U/D> and <R/F/U>. I'm open to every interesting idea.

thx all

sebastien


----------



## rachmaninovian (Jul 14, 2008)

when will it be up?


----------



## badmephisto (Jul 14, 2008)

That sounds pretty great! In the other solvers the feature that I always missed was some way to specify some rules on final state in form of constraint satisfaction problem. So you could enter initial state, and give rules for how the final state should look like. 
So for example could it find a ZBF2L alg if I give it initial state, and then final state is that
1. 2 layers are done
2. UF UB UR UL are correctly oriented

Something along those lines. It may be a little harder seeing as your solver is so very general, but the rules I have provided above there are pretty specific to a 3x3 cube. I dont know


----------



## Sébastien.felix (Jul 14, 2008)

rachmaninovian : It will be ended in september because i'm on hollydays now, so i'm a litle bit lazy.

badmephisto:this is exaclty what i can do with my solver. I think that the mode-2(computing entire sets of algs) wont be able on the single version. But if enough people use the "shared calculus" program, I will compute all sets of algs asked.

Enjoy it...and dont hesitate if you have any idea...


----------



## rachmaninovian (Jul 15, 2008)

ha ha thanks this program would be great for me and many others..will there be any graphics?


----------



## badmephisto (Jul 15, 2008)

rachmaninovian said:


> ha ha thanks this program would be great for me and many others..will there be any graphics?


that's probably a secondary issue at this stage, but a GUI eventually would be nice.

May I ask also what programming language you are developing this program in?


----------



## Sébastien.felix (Oct 24, 2008)

Hi everyone,

Because of the lack of free time, i didn't worked on the solver for a long time, but a week ago i work again on it and i got troubles on the interface. I fully have in mind what i need but i can't speed time to master C/C++ enough. I'm working on a console program (it's almost finished) but a nice interface would be much better!!
So if anyone is skilled enough, the cube community and I yell to this person to post here.

Have fun

Sébastien


----------



## badmephisto (Oct 27, 2008)

well just give us what you have. Its in C or C++? I've never done interface in those but maybe one option would be a standalone app, in any programming language that just executes the binary, reads the output using standard out, and then takes care of all the rendering, bells and whistles.


----------



## Lucas Garron (Oct 27, 2008)

I know that Robert Lang used http://www.wxwidgets.org/ for TreeMaker. I haven't really tried to use it myself, but it seems to be very useful, and hopefully not too difficult to use.

However, if you can get your program to work well enough in command line, I think that's already a lot for now.


----------



## Sébastien.felix (Oct 31, 2008)

My program is in C, but there is some details I want to finish before sending a beta version, first there is ZERO comment on my code source(i know that its not good but i never get lost) and all variables are named in french with weird names. 
Thx lucas, i'm going to check that, but i'm really not a programming specialist, my C program use very basic programming(but interesting maths )...
I'll keep everyone aware of my improvements..

have fun

sebastien


----------

