New puzzle solver

S

Sébastien.felix

Member
Joined
Dec 28, 2007
Messages
16
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
 
*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?
 
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:D(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.
 
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? ;)
 
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
 
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
 
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.
Click to expand...
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?
Click to expand...
Well, many programmers read this forum. There's also Domain of the Cube Forum.
 
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:D.

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
 
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
 
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...
 
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
 
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.
 
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:D.
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
 
You must log in or register to reply here.

Similar threads

OreKehStrah
Megaminx Puzzle Definition V1 for Trangium's Batch Solver
Replies
3
Views
1,252
OreKehStrah
OreKehStrah
imvelox
My own sliding puzzle solver
Replies
7
Views
2,986
TDM
TDM
L
Problem with Square-1 optimiser (from Jaap's puzzle page)
Replies
1
Views
1,306
blade740
blade740
S
kumi na tano 3.00 - sliding tile puzzle suboptimal solver
2
Replies
20
Views
15,473
stannic
S
Jteddy
Speedsliding 2026
Replies
8
Views
183
pi=3.14
pi=3.14
Back
Top