• 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

Renslay

Member
Joined
Aug 1, 2011
Messages
1,716
Location
Hungary
WCA
2005HANT01
YouTube
Visit Channel
Hi! I just tried it and defined the Floppy cube. It is fun! :)

Code:
Name Floppy

# def-file by Norbert Hantos

Set CORNERS 4 2
Set EDGES 4 2

Solved
CORNERS
1 2 3 4
EDGES
1 2 3 4
End

Move R
CORNERS
1 3 2 4
0 1 1 0
EDGES
1 2 3 4
0 1 0 0
End

Move F
CORNERS
1 2 4 3
0 0 1 1
EDGES
1 2 3 4
0 0 1 0
End

Move L
CORNERS
4 2 3 1
1 0 0 1
EDGES
1 2 3 4
0 0 0 1
End

Move B
CORNERS
2 1 3 4
1 1 0 0
EDGES
1 2 3 4
1 0 0 0
End

Edit: Hm, I think the orientation of the corners is not necessary.
 
Last edited:

Renslay

Member
Joined
Aug 1, 2011
Messages
1,716
Location
Hungary
WCA
2005HANT01
YouTube
Visit Channel
I just don't understand something. I defined a puzzle:

Code:
Solved
BIG 
1 1 2 2 3
SMALL
1 1 1 1 1 2 2 2 2 2 3 3 3 3
End

And of course I defined the moves. Then I give this scramble:

Code:
Scramble test
BIG
1 1 2 2 3
SMALL
3 1 2 3 2 2 3 1 1 2 2 3 1 1
End

The program solves it in 16 moves, which is nice. However, I try to find a solution where only the permutation of the 1s are interesting for me. Therefore I try:

Code:
Scramble test
BIG
1 1 2 2 3
SMALL
? 1 ? ? ? ? ? 1 1 ? ? ? 1 1
End

This is the same as above, just ? instead of numbers other than 1 on the small pieces. Here, the program couldn't find a solution (it goes even to depth 22 and further, but God's number for the whole puzzle is 21). However, if I give some "hint":

Code:
Scramble test
BIG
1 1 2 2 3
SMALL
?3 1 ?2 ?3 ?2 ?2 ?3 1 1 ?2 ?2 ?3 1 1
End

It finds again the 16 moves solution. What do I do wrong, why the second example does not working?
 

Carrot

Member
Joined
Feb 9, 2009
Messages
1,910
WCA
2008ANDE02
YouTube
Visit Channel
Code:
Solved
BIG 
1 1 2 2 3
SMALL
1 1 1 1 1 2 2 2 2 2 3 3 3 3
End

Ignore
SMALL
0 0 0 0 0 1 1 1 1 1 1 1 1 1
End

You need to put the Ignore in the Def file to activate the ?s

Code:
Scramble test
BIG
1 1 2 2 3
SMALL
?3 1 ?2 ?3 ?2 ?2 ?3 1 1 ?2 ?2 ?3 1 1
End

it may sound silly, but you actually NEED to put a valid piece after the ?. It's silly but I hope it works. if it doesn't I swapped the 0 and 1's in the Ignore in the def. (it's binary for ignore and don't ignore)
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
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
The Mac version fix is cool, but I'm not particularly happy with you doing all this easy-but-impressive-looking stuff behind my back and attaching your username and/or website to it. You know, this kind of thing makes me a LOT less eager to work on useful tools for the cubing community in the future.

This is the same as above, just ? instead of numbers other than 1 on the small pieces. Here, the program couldn't find a solution (it goes even to depth 22 and further, but God's number for the whole puzzle is 21). However, if I give some "hint"
If you aren't also putting an Ignore command in the .def file to tell ksolve you are ignoring pieces, that would be why it isn't working. Basically, if it does not know you are ignoring pieces, it uses the wrong pruning table and thinks a lot of perfectly good solutions are impossible. I'd love to only have this in the scramble file, but then it would have to compute pruning tables for each scramble as it goes, and in almost all cases that'd be way slower.

The substate structure uses unmanaged pointers for its int arrays. Either smart pointers should
be used, or explicit resource management should be done.
Interesting; if I am leaking memory this way I definitely want to fix it. What data structure changes do you recommend I make (put the substate in a smart pointer? put the orientation/permutation arrays in smart pointers? switch to a pair of smart-pointered vectors?)?
 

tim

Member
Joined
Nov 22, 2006
Messages
1,692
Location
Karlsruhe, Germany
WCA
2007HABE01
YouTube
Visit Channel
The Mac version fix is cool, but I'm not particularly happy with you doing all this easy-but-impressive-looking stuff behind my back and attaching your username and/or website to it.

That's totally understandable. But why do you not want to use Github (or any other comparable service)? I think this software would benefit from open sourcing it (in this case I mean: putting it somewhere to make it a) easily accessible and b) easy to contribute to). There are many capable coders in our community (and basically everyone knows C), but sending you files with fixes or improvements (like the linux port) is a pain in the ass and I personally don't want to do it.
 

Jakube

Member
Joined
Feb 3, 2011
Messages
790
Location
Austria
WCA
2011KOGL01
YouTube
Visit Channel
If you aren't also putting an Ignore command in the .def file to tell ksolve you are ignoring pieces, that would be why it isn't working. Basically, if it does not know you are ignoring pieces, it use the wrong pruning table and thinks a lot of perfectly good solutions are impossible. I'd love to only have this in the scramble file, but then it would have to compute pruning tables for each scramble as it goes, and in almost all cases that'd be way slower.

It should only have to be in the scramble file.
Your comment made me realize, that I had an ignore command in the definition file. It bugged me a while, that it wasn't able to find 12 move solutions in a reasonable time. After removing the command, ksolve finds 13+ solutions in a second.

Maybe you can save multiple pruning tables and always pick the best one. And if there's a scramble with a new ignore type, the generate a save new ones. I guess, people only use a small number of different ignore definitions, so it wouldn't have to generate the pruning tables at every scramble. Only if it should ignore new pieces.

Or just simply print a warning, if the program sees, that the current pruning tables doesn't match the scramble, like "Using different ignore setting might speed up the search" or "ksolve might not find all solutions because of wrong ignore settings".
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
Jakube: I agree that's how it should be, but it could mean having to keep track of multiple potentially-large pruning table files, loading and unloading large amounts of data into memory between scrambles, and recalculating any or all of that pruning table data whenever the definition file is changed. Really the problem is that I don't want the software to become bloated and slow just for the sake of a single feature, and I am worried this could do just that. A chunk of extra speed or efficiency could be very valuable to people searching in particularly difficult/complex puzzles.

That's totally understandable. But why do you not want to use Github (or any other comparable service)? I think this software would benefit from open sourcing it (in this case I mean: putting it somewhere to make it a) easily accessible and b) easy to contribute to). There are many capable coders in our community (and basically everyone knows C), but sending you files with fixes or improvements (like the linux port) is a pain in the ass and I personally don't want to do it.
I don't mind using a version control system if people want to actively contribute, and it seems like they do. I really do dislike the way git works (as a program and concept) and find most of its jargon incomprehensible, but if people are absolutely dead set on using git and github over something like SVN/Google Code I'll get down to figuring it out eventually.
 
Last edited:

rokicki

Member
Joined
Oct 31, 2008
Messages
301
Interesting; if I am leaking memory this way I definitely want to fix it. What data structure changes do you recommend I make (put the substate in a smart pointer? put the orientation/permutation arrays in smart pointers? switch to a pair of smart-pointered vectors?)?

Let's chat by email; mine should be pretty obvious and I'm not sure I remember what yours was.

But for a quick fix I'd recommend (I've never used these myself but I have heard a lot of good things
about them) the reference-counted pointers (std::shared_ptr) for your int* in substate.

You'll probably need to give substate a default constructor, a copy constructor, a destructor, and
an assignment operator, but these are pretty boilerplate.

-tom
 

tim

Member
Joined
Nov 22, 2006
Messages
1,692
Location
Karlsruhe, Germany
WCA
2007HABE01
YouTube
Visit Channel
I don't mind using a version control system if people want to actively contribute. I really do dislike the way git works (as a program and concept) and find most of its jargon incomprehensible, but if people are absolutely dead set on using git and github over something like SVN/Google Code I'll get down to figuring it out eventually.

Yeah, git is unfortunately far from easy to understand, but IMO worth learning. I especially found learning how git works internally very rewarding [1][2]. It's surprisingly simple.
Anyway, SVN+google code or mercurial+bitbucket would be fine as well.

[1] http://www.youtube.com/watch?v=GYnOwPl8yCE
[2] http://www.youtube.com/watch?v=1ffBJ4sVUb4 (funny, but not as accurate and detailed as [1])
 
Last edited:

rokicki

Member
Joined
Oct 31, 2008
Messages
301
Another fix is to replace int* with vector<int> in substate and make the relevant other
changes throughout. This may be simpler or may be harder.

Neither of these solutions will be particularly efficient.
 

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
The Mac version fix is cool, but I'm not particularly happy with you doing all this easy-but-impressive-looking stuff behind my back and attaching your username and/or website to it. You know, this kind of thing makes me a LOT less eager to work on useful tools for the cubing community in the future.

I do put an attribution where I can, e.g. "Versioned mirror of Kare's / qqwref's ksolve+ puzzle solver." on the top of GitHub.
This particular time, the demo page didn't have an attribution because it is a minimal test page (i.e. based on this instead of this) but I've added them now.

I'm glad you're open to something like GitHub for collaborative development. There are a few more easy-but-impressive-looking steps to take. ;-)
I personally prefer the flexibility of git and the fact that GitHub focuses on the code itself (plus, most people are already there), but something else would be fine.
 
Last edited:

cubizh

Member
Joined
Oct 2, 2011
Messages
602
Location
Portugal
WCA
2014GOME07
YouTube
Visit Channel
A chunk of extra speed or efficiency could be very valuable to people searching in particularly difficult/complex puzzles.

One feature I would like to see implemented is the save search upon crash or termination and resume. You can imagine how pissed off I was having ksolve running for an entire week (well, 6 days straight) searching for algs and all of a sudden losing everything due to a CPU overheat emergency shutdown.

qqwref said:
I don't mind using a version control system if people want to actively contribute, and it seems like they do. I really do dislike the way git works (as a program and concept) and find most of its jargon incomprehensible, but if people are absolutely dead set on using git and github over something like SVN/Google Code I'll get down to figuring it out eventually.
tim said:
Yeah, git is unfortunately far from easy to understand, but IMO worth learning. I especially found learning how git works internally very rewarding [1][2]. It's surprisingly simple.
Anyway, SVN+google code or mercurial+bitbucket would be fine as well.

[1] http://www.youtube.com/watch?v=GYnOwPl8yCE
[2] http://www.youtube.com/watch?v=1ffBJ4sVUb4 (funny, but not as accurate and detailed as [1])
I personally prefer the flexibility of git and the fact that GitHub focuses on the code itself (plus, most people are already there), but something else would be fine.
I have used GitHub, but am also not particularly experienced with it beyond the utmost basics, but really mostly because I have not really looked deeply into it. I will look more into it in the future.
Thanks for the links, tim.
 

Ranzha

Friendly, Neighbourhoodly
Joined
Jul 24, 2009
Messages
2,551
Location
Reno, Nevada, United States
WCA
2009HARN01
YouTube
Visit Channel
I made some ksolve+ definition files for Skewb in WCA-style FCN, FCeN, and Hideki Niina's notation that are similar to Thom's def file. The biggest difference is the piece labelling and the inclusion of all pieces. This may cause the solver to run less quickly, but the solver's fast and furious as it is, so no harm done? =D

The piece labelling was meant to mirror Meep's Skewb Solver 2.2. Also, for solvers using Sarah's method (and thus Hideki Niina's notation), choose the set of moves you want to include in your def file. Turns about all eight corners are defined below.

Fixed Corner Notation, WCA-style:
Code:
# Skewb ksolve+ definition file (tested on v1.3 from http://mzrg.com/rubik/ksolve+/)
#
# Notation is Fixed Corner Notation (FCN) as defined here: 
# https://www.worldcubeassociation.org/regulations/#12h
#
# Ranzha
#
# centres U F R D B L
# corners UFR, UBR, UBL, UFL, DFR, DBR, DBL, DFL
# moves U R L B

Name Skewb
Set corners 8 3
Set centres 6 1
Solved
corners
1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0
centres
1 2 3 4 5 6
End
Move U
corners
1 7 3 2 5 6 4 8
0 2 1 2 0 0 2 0
centres
5 2 3 4 6 1
End
Move R
corners
1 5 3 4 7 6 2 8
0 2 0 0 2 1 2 0
centres
1 2 4 5 3 6
End
Move L
corners
1 2 3 7 4 6 5 8
0 0 0 2 2 0 2 1
centres
1 6 3 2 5 4
End
Move B
corners
1 2 6 4 5 8 7 3
0 0 2 0 0 2 1 2
centres
1 2 3 6 4 5
End


Fixed Centre Notation:
Code:
# Skewb ksolve+ definition file (tested on v1.3 from http://mzrg.com/rubik/ksolve+/)
#
# Notation is Fixed Centre Notation (FCeN) as defined here: 
# http://ranzha.cubing.net/skewb/notation.html
#
# Ranzha
#
# centres U F R D B L
# corners UFR, UBR, UBL, UFL, DFR, DBR, DBL, DFL
# moves F R L B

Name Skewb
Set corners 8 3
Set centres 6 1
Solved
corners
1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0
centres
1 2 3 4 5 6
End
Move F
corners
8 2 3 4 5 1 7 6
2 0 0 0 1 2 0 2
centres
1 4 2 3 5 6
End
Move R
corners
1 5 3 4 7 6 2 8
0 2 0 0 2 1 2 0
centres
1 2 4 5 3 6
End
Move L
corners
1 2 3 7 4 6 5 8
0 0 0 2 2 0 2 1
centres
1 6 3 2 5 4
End
Move B
corners
1 2 6 4 5 8 7 3
0 0 2 0 0 2 1 2
centres
1 2 3 6 4 5
End


Hideki Niina's notation:
Code:
# Skewb ksolve+ definition file (tested on v1.3 from http://mzrg.com/rubik/ksolve+/)
#
# Notation is in the style of Hideki Niina as defined here: 
# http://rubikskewb.web.fc2.com/skewb/notation.html
#
# Ranzha
#
# centres U F R D B L
# corners UFR, UBR, UBL, UFL, DFR, DBR, DBL, DFL
# moves F R L B f r l b

Name Skewb
Set corners 8 3
Set centres 6 1
Solved
corners
1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0
centres
1 2 3 4 5 6
End
Move F
corners
1 4 3 5 2 6 7 8
1 2 0 2 2 0 0 0
centres
2 3 1 4 5 6
End
Move R
corners
6 2 1 4 5 3 7 8
2 1 2 0 0 2 0 0
centres
3 2 5 4 1 6
End
Move L
corners
3 2 8 4 5 6 7 1
2 0 2 1 0 0 0 2
centres
6 1 3 4 5 2
End
Move B
corners
1 7 3 2 5 6 4 8
0 2 1 2 0 0 2 0
centres
5 2 3 4 6 1
End
Move f
corners
8 2 3 4 5 1 7 6
2 0 0 0 1 2 0 2
centres
1 4 2 3 5 6
End
Move r
corners
1 5 3 4 7 6 2 8
0 2 0 0 2 1 2 0
centres
1 2 4 5 3 6
End
Move l
corners
1 2 3 7 4 6 5 8
0 0 0 2 2 0 2 1
centres
1 6 3 2 5 4
End
Move b
corners
1 2 6 4 5 8 7 3
0 0 2 0 0 2 1 2
centres
1 2 3 6 4 5
End


Rotations:
Code:
# Skewb ksolve+ definition file for rotations (tested on v1.3 from http://mzrg.com/rubik/ksolve+/)
#
# Ranzha
#
# moves x y z

Name Skewb
Set corners 8 3
Set centres 6 1
Solved
corners
1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0
centres
1 2 3 4 5 6
End
Move x
corners
5 1 4 8 6 2 3 7
0 0 0 0 0 0 0 0
centres
2 4 3 5 1 6
End
Move y
corners
2 3 4 1 6 7 8 5
0 0 0 0 0 0 0 0
centres
1 3 5 4 6 2
End
Move z
corners
4 3 7 8 1 2 6 5
0 0 0 0 0 0 0 0
centres
6 2 1 3 5 4
End

In my few days of using it, I'd like to commend all contributors to ksolve+. This solver is fast, efficient, well-documented--truly revolutionary.
 
Last edited:

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
Honestly, because of what lgarron did, I'm really not particularly excited about putting any more time into this thing. I made a ton of huge changes since Kare's version, completely rewrote the readme, and put a lot of time in, but I'm sure soon enough anyone who googles it will just think "oh it's yet another lgarron project, he's so awesome". I'm probably going to release a last version at some point, to fix some bugs, and then that's it. For the record, ksolve was all done by Kare and everything after that and until ksolve+ v1.3 was done by me; the next version I put on my site will have contributions from others.
 
Last edited:

joey

Member
Joined
Apr 8, 2007
Messages
4,413
WCA
2007GOUL01
YouTube
Visit Channel
Nowhere does it say anything about Lucas? Your name is definitely on there.

You could also ask Lucas to take it down, or make your own account on github.
 

cubizh

Member
Joined
Oct 2, 2011
Messages
602
Location
Portugal
WCA
2014GOME07
YouTube
Visit Channel
Honestly, because of what lgarron did, I'm really not particularly excited about putting any more time into this thing. I made a ton of huge changes since Kare's version, completely rewrote the readme, and put a lot of time in, but I'm sure soon enough anyone who googles it will just think "oh it's yet another lgarron project, he's so awesome". I'm probably going to release a last version at some point, to fix some bugs, and then that's it. For the record, ksolve was all done by Kare and everything after that and until ksolve+ v1.3 was done by me; the next version I put on my site will have contributions from others.
I think everyone that matters knows and appreciates your efforts in rebooting ksolve and sharing it openly for the benefits of all, regarding general puzzle solving.
 

TheNextFeliks

Member
Joined
Oct 27, 2012
Messages
2,414
Location
KCKS
WCA
2013POPE01
YouTube
Visit Channel
Ok. This is great. But I can't figure out the Ignore. I am trying to do OLL so avoiding the permutation. Could someone post an example? I am trying to find algs for the I case with bars on both sides.
 
Top