• 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

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
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.

So basically, while the original ksolve gives the user full control over defining canonical sequences, with the new version the user don't have any control over that whatsoever. I think it's great that the program can handle canonicalization automatically, but I don't think I particularly like its choice being forced upon me. And it seems to me the ForbiddenPairs feature has been made pretty much obsolete unless you want to prohibit certain non-commuting 2-move sequences for some reason.
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
Well, for ksolve+ v1.1 I've made a change that if you explicitly forbid one of the two parallel possibilities (e.g. FL UB) it will not automatically forbid the other one. The Helicopter Cube example you gave will generate the 3-move sequence now. So you can have control over which of the two canonical sequences it chooses, although if you are looking for the choice of generating both FL UB and UB FL, that is not currently an option.

And yes, ForbiddenPairs/ForbiddenGroups should be pretty much obsolete, although if someone does want to use them (for generating algs without particularly un-ergonomic move sequences, perhaps?) they are still available.
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
Version 1.1 is out: http://mzrg.com/rubik/ksolve+/ksolve_v1.1.rar

- I fixed the two problems Bruce mentioned.
- Orientation is now optional (you can leave it out anywhere and ksolve+ will just use all 0's). This should save time writing definition files, especially for puzzles with no orientation.
- MoveLimits is now in the scramble file instead of the definition file. You can put a limit on single moves (F2 2) or one move and all its powers (F* 2). I also added some optimizations to make move-limited alg searches run a bit faster.
 

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
This runs great for me in OSX using wine, but I'd prefer a native build for OSX/Linux.
How hard would it be to remove Windows-specific code?

Also, I'd be interested in tracking the revision history. Would you consider posting a versioned repository somewhere? (I'm always a fan of things on GitHub!)
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
I could be wrong, but I think the only Windows-specific code is the stuff in pruning.h that checks which of two files is newer. You're welcome to try to rewrite those small parts (probably shouldn't need much changed) and recompile it.

And no, I really dislike using stuff like GitHub for personal development. There's too much overhead for me (sometimes I can spend more time trying to figure out how to send in the updated code than I actually spent writing it :|). I've just been keeping sub-versions in folders, which I guess I could zip up and send to you if you really want.
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
Version 1.2: http://mzrg.com/rubik/ksolve+/ksolve_v1.2.rar

- Everything runs way faster (roughly 2-3 times for my test cases). This is partly due to turning on gcc's maximum optimization (sorry I didn't think of this sooner :p) and partly due to code optimizations which have the biggest effect on bandaged puzzles (such as the Bicube) and on puzzles with permutation-only pieces (such as 2gen Megaminx).
- Various other code improvements
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
Version 1.3: http://mzrg.com/rubik/ksolve+/ksolve_v1.3.rar

- Optimized indexing code for non-unique permutations (so puzzles with indistinguishable pieces will run faster)
- Changed data structure for moves, everything runs faster
- God's Alg tables can be generated for puzzles with > 2^63 positions, although it's slower
- God's Alg command prints algs for antipode positions
- Comments no longer require a space after the #, and they work in scramble files too
- In .def file, can omit parts of a move/solved state
 

MarcoRossi

Member
Joined
Jan 2, 2011
Messages
4
Location
Italy
Can anyone explain me how the orientations are defined? I don't understand even the 2x2x2 def files.
For example move R is:

CORNERS
1 3 6 4 2 5 7
0 2 1 0 1 2 0

Why the orientation of the piece "3" is 2 and of piece "6" is 1?
 
Last edited:

Kare

Member
Joined
Jun 12, 2006
Messages
21
Location
Sweden
WCA
2004KRIG02
View attachment ksolveParallel.zip

Sorry it took so long to get started with the threading, work came in the way.

I have changed the search to consider each initial move a different task. Eg "find a 12 move solution starting with R" is one task, "find a 12 move solution starting with U2" is another. Each core on the computer will be assigned one task, and when one task is finished the core will get a new one if any remains. Output algs will no longer be sorted.

The only change is in treeSolve(...).

Program needs to be built with openmp. I think most compilers support that, but it might be an optional item you need to install. I used mingw-gcc on windows and had to install openmp as an optional package.

With gcc you need to build and link with -fopenmp

With mingw-gcc on windows the exe will be dependant on libgomp-1.dll and pthreadGC2.dll, both was included when I got the openmp package. For linux it seems to just work.

Performance is decent, but I was expecting better scaling than this. On my machine (4 cores, no hyper threading) I get the following for your 3x3x3_RFU computations.

Your binary: 658s
Your source, built by me: 654s
Threaded program, one thread: 653s
Threaded program, two threads: 432s
Threaded program, four threads: 342s


My change looks horrendous with all the code duplication, but when I tried to fix that by breaking it out to a function (ie, treeSearch calling foo() which in turn calls the next treeSearch level) I took a big performance hit.

It would be quite easy to also parallelize the table generation. Each table (edges permutation, corners orientation etc) can be considered one task and easily distributed, but with tables saved on disk it's not that much of an advantage.
 

Kirjava

Colourful
Joined
Mar 26, 2006
Messages
6,121
WCA
2006BARL01
YouTube
Visit Channel
Aww yea, I knew this would come in handy

Code:
# Skewb ksolve+ definition file (tested on v1.3 from http://mzrg.com/rubik/ksolve+/)
#
# Notation is FCN as defined here; 
# http://meep.cubing.net/skewb-fcn.html
#
# Kirjava is cool
#
# CORNERS UFL, UBL, UBR, DFR, DFL, DBL, DBR
# CENTRES U F L B R D
# MOVES U D L R

Name Skewb
Set CORNERS 7 3
Set CENTRES 6 1
Solved
CORNERS
1 2 3 4 5 6 7
CENTRES
1 2 3 4 5 6
End
Move R
CORNERS
1 2 4 6 5 3 7
0 0 2 2 0 2 1
CENTRES
1 2 3 5 6 4
End
Move L
CORNERS
6 2 3 1 5 4 7
2 0 0 2 1 2 0
CENTRES
1 3 6 4 5 2
End
Move U
CORNERS
3 2 6 4 5 1 7
2 1 2 0 0 2 0
CENTRES
4 2 1 3 5 6
End
Move D
CORNERS
1 7 3 4 2 6 5
0 2 0 0 2 1 2
CENTRES
1 2 4 6 5 3
End

rob helped fix a mistake
 

Robert-Y

Member
Joined
Jan 21, 2009
Messages
3,289
Location
England
WCA
2009YAUR01
YouTube
Visit Channel
Hi. I've created a definition file for 3x3x3 <R,r,U,F>, but whenever I run it, my laptop seems to freeze.
Can someone please tell me how to run this successfully and if I've made an error in the code? Thanks...

Code:
Name 3x3x3 <R,r,U,F>

# def-file by Robert Yau
# Edges: UF UL UB UR FL BR FR DF DB DR
# Corners: UFL UBL UBR UFR DFL DBR DFR
# Centres: U F D B

Set EDGES 10 2
Set CORNERS 7 3
Set CENTRES 4 1

Solved 
EDGES 
1 2 3 4 5 6 7 8 9 10
0 0 0 0 0 0 0 0 0 0
CORNERS
1 2 3 4 5 6 7
0 0 0 0 0 0 0
CENTRES
1 2 3 4
End

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

Move r
EDGES
8 2 1 7 5 4 10 9 3 6
1 0 1 0 0 0 0 1 1 0
CORNERS
1 2 4 7 5 3 6
0 0 1 2 0 2 1
CENTRES
2 3 4 1
0 0 0 0
End

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

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

EDIT: I figured it out. I defined two moves R and r but ksolve isn't case sensitive so I had to call r something else like Rw.
 
Last edited:

Robert-Y

Member
Joined
Jan 21, 2009
Messages
3,289
Location
England
WCA
2009YAUR01
YouTube
Visit Channel
Here's a fun 3x3x3 one :p

(Just T perm and rotations!)

Code:
Name Tperm

# Robert Yau made this...
# CORNERS URF, ULF, ULB, URB, DRF, DLF, DLB, DRB
# EDGES UF UL UB UR FR FL BL BR DF DL DB DR
# CENTRES U F L B R D

Set CORNERS 8 3
Set EDGES 12 2
Set CENTRES 6 1

Solved
CORNERS
1 2 3 4 5 6 7 8
EDGES
1 2 3 4 5 6 7 8 9 10 11 12
CENTRES
1 2 3 4 5 6
End

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

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

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

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

DrKorbin

Member
Joined
Aug 10, 2011
Messages
707
Location
Russia, Moscow
WCA
2011GRIT01
YouTube
Visit Channel
If def-file or file with scrambles has an empty line at the end, the program crashes.
Code:
...
Pruning tables found on file.
Pruning tables loaded.
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string::at

This application has requested the Runtime to terminate it in an unusual way.
Please contact the application's support team for more information.
 

cubizh

Member
Joined
Oct 2, 2011
Messages
602
Location
Portugal
WCA
2014GOME07
YouTube
Visit Channel
If def-file or file with scrambles has an empty line at the end, the program crashes.
This specific bug can be easily fixed by editing readdef.h and readscramble.h and locate the following code (around line 40), and add the check for size == 0 like the following, for both files:
Code:
                ......
                while(!fin.eof()){
                        string command;
                        fin >> command;
                        // Break if nothing is found on file
                        if (command.size() == 0) {
                                break;
                        }
          
                        if (command == " .......
Hope this helps you.

Also, I asked a friend to help me port it to Linux and so I'd like to share a working Ksolve for Linux version, and I would like to ask the developers to see if they can find a way to integrate the changes into the main code so that a system-independent version can be achieved (which I can't do/test).
 

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
Also, I asked a friend to help me port it to Linux and so I'd like to share a working Ksolve for Linux version, and I would like to ask the developers to see if they can find a way to integrate the changes into the main code so that a system-independent version can be achieved (which I can't do/test).

qqwref doesn't like using GitHub for this, but I track his changes on my repo. I've also added your changes on a branch: https://github.com/lgarron/ksolve-plus/tree/unix
 

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
Last edited:

rokicki

Member
Joined
Oct 31, 2008
Messages
301
So, compiling to JS was easy: http://www.cubing.net/ksolve.js/simple-async.html

Unfortunately, memory usage blows up in the browser (I quickly hit 600MB on the 3x3x3 RFU example).

The substate structure uses unmanaged pointers for its int arrays. Either smart pointers should
be used, or explicit resource management should be done.

(I don't know that this is the only memory leak, but it's the main one I see.)
 
Top