ksolve+ v1.0 - general-purpose algorithm finder

[qqwref]

ksolve+ is a C++ program that can find algorithms for many different puzzles - any simple permutation puzzle you can think of, and some not-so-simple ones too. This includes 2x2x2, 3x3x3, Megaminx, Square-1, and so on. You write a definition file defining the puzzle, and a scramble file listing the scrambles, and then ksolve+ will find optimal (or near-optimal, if you want) solutions for your scrambles.

The original ksolve was written by Kare Krig, but it hasn't been updated in a few years and I figured it could use some improvement. Apart from some major code rewriting, there are many improvements and new features. Changes include generating/solving random scrambles, ignoring pieces in the scramble file, reading in move sequences as scrambles, computing God's Algorithm tables, optionally using QTM, limiting the allowed number of each type of move, and looking for suboptimal algs. I also made it about 25% faster.

Download link (v1.3):
http://mzrg.com/rubik/ksolve+/ksolve_v1.3.rar
Apart from ksolve+ itself, I have included a readme, a bunch of sample definition and scramble files, and the source code.

Please let me know if you have any problems or if you find any bugs

 

[Tim Major]

It was Ksolve that had the amazing Pyraminx solver. I lost the software and the name, thanks for improving it

Edit: Getting this: The program can't start because libgcc_s_dw2-1.dll is missing
http://stackoverflow.com/questions/...t-start-because-libgcc-s-dw2-1-dll-is-missing
I don't really understand what to do.

 

[qqwref]

Gotcha. Should be fixed now, give it a try.

 

[BurntTheCube]

Can't really get it to open but thats probably because I'm not tech savvy. But it closed like 22 tabs (MY COOKIE CLICKER!!) and downloaded some crappy homepage. 0/10

 

[qqwref]

I put it up on my website instead; the download should be more foolproof now.

 

[Ranzha]

Can't really get it to open but thats probably because I'm not tech savvy. But it closed like 22 tabs (MY COOKIE CLICKER!!) and downloaded some crappy homepage. 0/10

Cookie Clicker autosaves every minute.

 

[Tim Major]

I put it up on my website instead; the download should be more foolproof now.

I extracted, double clicked on ksolve.exe, it opens a small black window (like cmd) and instantly closes with no error message or anything. I can fraps if you want.

 

[oranjules]

you have to launch it from cmd

 

[Tim Major]

you have to launch it from cmd

Yeah I read the readme, I think I understand how to use it now. Thanks. I probably won't actually use this software. I basically understand how to use it, but it's too difficult to use.

 

[Renslay]

If I'm guessing right, one can define a Square-1 by a puzzle with 24 pieces, (12 top, 12 bottom), 8 pairs of them are bandanged, and there are two center pieces (middle layer), where the orientation (permutation?) counts; and define U30, D30 and R180 moves with only permutations.

Edit: well, actually only the orientation of the right "center" counts.

 

[Kirjava]

I'm really glad you improved this, will save me a lot of time hacking together quick solvers.

Name 3 Colour Cube

# Kirjava
# CORNERS URF, ULF, ULB, URB, DRF, DLF, DLB, DRB
# EDGES UF UL UB UR FR FL BL BR DF DL DB DR

Set CORNERS 8 3
Set EDGES 12 2

Solved
CORNERS
1 2 1 2 2 1 2 1
0 0 0 0 0 0 0 0
EDGES
1 2 1 2 3 3 3 3 1 2 1 2
0 0 0 0 0 0 0 0 0 0 0 0
End

Move U
CORNERS
4 1 2 3 5 6 7 8
0 0 0 0 0 0 0 0
EDGES
4 1 2 3 5 6 7 8 9 10 11 12
0 0 0 0 0 0 0 0 0 0 0 0
End

Move R
CORNERS
5 2 3 1 8 6 7 4
1 0 0 2 2 0 0 1
EDGES
1 2 3 5 12 6 7 4 9 10 11 8
0 0 0 1 1 0 0 1 0 0 0 1
End

Move F
CORNERS
2 6 3 4 1 5 7 8
2 1 0 0 1 2 0 0
EDGES
6 2 3 4 1 9 7 8 5 10 11 12
0 0 0 0 0 0 0 0 0 0 0 0
End

Move D
CORNERS
1 2 3 4 6 7 8 5
0 0 0 0 0 0 0 0
EDGES
1 2 3 4 5 6 7 8 10 11 12 9
0 0 0 0 0 0 0 0 0 0 0 0
End

Move L
CORNERS
1 3 7 4 5 2 6 8
0 2 1 0 0 1 2 0
EDGES
1 7 3 4 5 2 10 8 9 6 11 12
0 1 0 0 0 1 1 0 0 1 0 0
End

Move B
CORNERS
1 2 4 8 5 6 3 7
0 0 2 1 0 0 1 2
EDGES
1 2 8 4 5 6 3 11 9 10 7 12
0 0 0 0 0 0 0 0 0 0 0 0
End

Gonna have some fun with this, I always knew there would be a short way to J perm but never thought it'd be like 6 moves.

 

[JustinJ]

This is super awesome! I've been thinking about how something like this would be useful recently, and it would be really nice to have this as a library of some kind so people could make GUI solvers easily (I don't mind CLI, but I think a lot of people who want to find algs do). Do you think it might even be possible to compile it to JavaScript with https://github.com/kripken/emscripten/wiki, and then use it to make in-browser solvers easily?

 

[Kare]

This is great to see. I have been avoiding any development as I felt a major rewrite was needed to clean up the mess and thanks to the magic of open source I won't have too do that

Something I have been experimenting with but never released is making the computations on multiple cores. A solver is very well suited to parallelization. With OpenMP it's fairly easy to add to a working single threaded program and I know gcc can get it working on both Windows and Linux. If you want any help with OpenMP I would be happy to lend a hand.

 

[qqwref]

Glad this is useful to you guys. I was also thinking of putting up a page of prewritten def files on my site, so if you write up a def file for anything unusual, if you post it or send it over I could put it up.

Do you think it might even be possible to compile it to JavaScript with https://github.com/kripken/emscripten/wiki, and then use it to make in-browser solvers easily?

If you do want to use ksolve+ as a sort of library you definitely could (it's open source and I don't personally mind if you use it in another project). It should be possible to compile to JS too, although I have a feeling the speed would be a problem (a solver specifically written for your puzzle of choice would probably be faster). You're thinking of a solver for a specific puzzle that comes with a prewritten def file, right?

This is great to see. I have been avoiding any development as I felt a major rewrite was needed to clean up the mess and thanks to the magic of open source I won't have too do that

Glad I could help

Something I have been experimenting with but never released is making the computations on multiple cores. A solver is very well suited to parallelization. With OpenMP it's fairly easy to add to a working single threaded program and I know gcc can get it working on both Windows and Linux. If you want any help with OpenMP I would be happy to lend a hand.

Sure, some help with that would be very useful. Would it slow down the program much on a machine with only one or two cores?

 

[JustinJ]

If you do want to use ksolve+ as a sort of library you definitely could (it's open source and I don't personally mind if you use it in another project). It should be possible to compile to JS too, although I have a feeling the speed would be a problem (a solver specifically written for your puzzle of choice would probably be faster). You're thinking of a solver for a specific puzzle that comes with a prewritten def file, right?

Yeah, pretty much, and that could translate input on a graphical puzzle into something ksolve could solve. Maybe I will look into it when I have a chance.

 

[qqwref]

I put up a page on my website with a ksolve+ download and a bunch of .def files: http://mzrg.com/rubik/ksolve+/

I had some new ideas for things to add, so version 1.1 should be coming soon...

 

[AvGalen]

This thread is proof that only a few people in the world are creators and all others are users.
It also felt like I was back in 2000 with seeing C++, commandline, missing references, bad downloadlinks.....and then someone asked "can it be used with javascript"

Great work Michael. I will have a look at it this week and see if I can make a def file for one or more puzzles
BOOKMARKED

 

[Gunnar]

Using openMP

Kåre is in Manilla for a month so I'm not sure if he will respond here, but I can just tell how I've used openMP to parallelize my own little cube solver.

My basic searchFunction looks like this. The pragma call will split the for-loop to be run on as many threads as there are cores. You'd have to import the library <omp.h> and I had to link "\MinGW\bin\pthreadGC2.dll" and set the compiler flag -fopenMP. I think you may find more info on openmp.org, since I'm not very good at explaining this.

bool SearchParallel(Cube scramble, int indexEO, int indexCO, int indexCP, int depth)
{
if(depth == 0)
{
if(scramble.isSolved(indexEO, indexCO, indexCP))
{
cout << endl << "Cube is already solved!" << endl;
return true;
}
}

#pragma omp parallel for
for(int i = 0; i < nrOfAllowedMoves; i++)
{
int move = allowedMoves;
int newIndexEO = transition.transitionTable_EO[PruningTable::SIZE_PRUNE_EO*i + indexEO];
int newIndexCO = transition.transitionTable_CO[PruningTable::SIZE_PRUNE_CO*i + indexCO];
int newIndexCP = transition.transitionTable_CP[PruningTable::SIZE_PRUNE_CP*i + indexCP];
if(Search(scramble.applyMove(move), newIndexEO, newIndexCO, newIndexCP, depth-1, move, -1, moves[move]))
found = true;
}

return false;
}


I also run the creation of the pruning tables in parallel in a manner like this. If the functions execute very quickly the overhead will make it run slower in parallel, but it's great for generating several big pruning tables.

#pragma omp parallel sections
{
#pragma omp section
{
generatePruningTableEO(allowedMoves, nrOfAllowedMoves);
}
#pragma omp section
{
generatePruningTableEP(allowedMoves, nrOfAllowedMoves);
}
#pragma omp section
{
generatePruningTableCO(allowedMoves, nrOfAllowedMoves);
}
}

 

[cuBerBruce]

It appears to me that if I specify "ForbiddenPairs" explicitly, the program still forbids certain pairs of its own. For example, if I add:

ForbiddenPairs
UF UB
FL UB
FR UB
UL UR
End

to the Helicopter_Cube_6gen.def file, and give it the scramble "UF UB FL", it fails to find any 3-move solutions, even though "UB FL UF" doesn't violate any of the given move restrictions. It finds 11-move solutions. In fact, simply including "FL UB" as a forbidden pair is sufficient to make it fail to find any 3-move solutions.

One other thing, if I forget to enter a name for a scramble, the program crashes.

Generally, though, thanks for implementing these improvements.

 

[qqwref]

Yes, the program forbids quite a few pairs of its own. The reason for the problem you encountered is that ksolve+ has apparently already forbidden UB FL due to the two moves being parallel (it always forbids one of the two possibilities when it notices this). When you manually forbid the other possibility (FL UB), it cannot generate UB and FL next to each other in either order. Your move sequence is also equivalent to FL UF UB, which I think is also forbidden by the parallel move code. Thus the 3-move solution is blocked. I think this is more of an unintended effect of your command than an actual bug, since it seems like ksolve+ is working properly given its internal list of forbidden move pairs. I'll add some code to deal with this case, but you should never need to use ForbiddenPairs in the way you did.

I'll look into the nameless scramble thing as well, thanks.