# ksolve+ v1.0 - general-purpose algorithm finder

Discussion in 'Software Area' started by qqwref, Oct 17, 2013.

Welcome to the Speedsolving.com. You are currently viewing our boards as a guest which gives you limited access to join discussions and access our other features. By joining our free community of over 30,000 people, you will have access to post topics, communicate privately with other members (PM), respond to polls, upload content and access many other special features. Registration is fast, simple and absolutely free so please, join our community today!

1. ### RenslayMember

Aug 1, 2011
Hungary
WCA:
2005HANT01
Renslay
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: Jan 7, 2014
2. ### RenslayMember

Aug 1, 2011
Hungary
WCA:
2005HANT01
Renslay
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?

3. ### CarrotMember

Feb 9, 2009
WCA:
2008ANDE02
Minxer2011
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)

4. ### qqwrefMember

7,832
17
Dec 18, 2007
a <script> tag near you
WCA:
2006GOTT01
qqwref2
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.

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.

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?)?

5. ### timMember

Nov 22, 2006
Karlsruhe, Germany
WCA:
2007HABE01
cin9247
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.

6. ### JakubeMember

790
2
Feb 3, 2011
Austria
WCA:
2011KOGL01
JakubeBLD
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".

7. ### qqwrefMember

7,832
17
Dec 18, 2007
a <script> tag near you
WCA:
2006GOTT01
qqwref2
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.

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: Jan 8, 2014
8. ### rokickiMember

253
1
Oct 31, 2008
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

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

9. ### timMember

Nov 22, 2006
Karlsruhe, Germany
WCA:
2007HABE01
cin9247
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.

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

Last edited: Jan 8, 2014
10. ### rokickiMember

253
1
Oct 31, 2008
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.

11. ### Lucas GarronSuper-Duper ModeratorStaff Member

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: Jan 8, 2014
12. ### cubizhSuper ModeratorStaff Member

596
25
Oct 2, 2011
Portugal
WCA:
2014GOME07
cubizh
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.

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.

13. ### RenslayMember

Aug 1, 2011
Hungary
WCA:
2005HANT01
Renslay
Thanks to ksolve, I was able to construct a full solving method for a brand new puzzle!

14. ### RanzhaFriendly, NeighbourhoodlyStaff Member

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: Jan 9, 2014
15. ### qqwrefMember

7,832
17
Dec 18, 2007
a <script> tag near you
WCA:
2006GOTT01
qqwref2
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: Jan 23, 2014
16. ### joeyMember

Apr 8, 2007
WCA:
2007GOUL01
cardologist
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.

17. ### cubizhSuper ModeratorStaff Member

596
25
Oct 2, 2011
Portugal
WCA:
2014GOME07
cubizh
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.

18. ### TheNextFeliksMember

Oct 27, 2012
KCKS
WCA:
2013POPE01
TheNextFeliks
How does one write a proper define file? I am just using the JavaScript one on cubing.net btw and I love it.

318
0
Jun 17, 2010
WCA:
2012BIER01

20. ### TheNextFeliksMember

Oct 27, 2012
KCKS
WCA:
2013POPE01
TheNextFeliks
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.