• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

ksolve+ v1.0 - general-purpose algorithm finder

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
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 :)
 
Last edited:

BurntTheCube

Member
Joined
Aug 24, 2013
Messages
27
Location
Tx, USA
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
 

Renslay

Member
Joined
Aug 1, 2011
Messages
1,716
Location
Hungary
WCA
2005HANT01
YouTube
Visit Channel
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.
 
Last edited:

Kirjava

Colourful
Joined
Mar 26, 2006
Messages
6,121
WCA
2006BARL01
YouTube
Visit Channel
I'm really glad you improved this, will save me a lot of time hacking together quick solvers.

Code:
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

Premium Member
Joined
Oct 15, 2008
Messages
635
Location
Waterloo, Ontario, Canada
WCA
2008JAFF01
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

Member
Joined
Jun 12, 2006
Messages
21
Location
Sweden
WCA
2004KRIG02
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

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
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

Premium Member
Joined
Oct 15, 2008
Messages
635
Location
Waterloo, Ontario, Canada
WCA
2008JAFF01
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.
 

AvGalen

Premium Member
Joined
Jul 6, 2006
Messages
6,857
Location
Rotterdam (actually Capelle aan den IJssel), the N
WCA
2006GALE01
YouTube
Visit Channel
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

Member
Joined
May 7, 2006
Messages
231
Location
Norrköping, Sweden
WCA
2004KRIG01
YouTube
Visit Channel
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. :p

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

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
It appears to me that if I specify "ForbiddenPairs" explicitly, the program still forbids certain pairs of its own. For example, if I add:
Code:
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

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
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.
 
Top