# Jaap's Square-1 Solver with 'Ignore pieces' functionality



## dougbenham (Jun 2, 2009)

Okay so.. I know that many people have been looking for something like this. Over the past 2 days I have spent about 8 hours reading over Jaap's square-1 solver code (C++, which i'm not even familiar with). It was pretty insane how this thing works.

Okay so I've done a few modifications:

Simple aesthetic changes
Perhaps a solution is found at a depth of 5, if you want to search further, you are now prompted to do so
Pieces can be ignored
The solver can attempt to solve using only (U and R2) or (D and R2)

Now this program is in a beta version. *And I would like to first ask about the legality of distributing this program to you all.*

My biggest worry is that I can't release this program because of the following line:
"by Jaap Scherphuis, [email protected], copyright 2003."
Which is located in the readme file distributed with his original work.

*Am I in the legal realms if I decide to distribute this to you all?*


----------



## Johannes91 (Jun 2, 2009)

You should ask Jaap. If he doesn't give you permission, it'd be illegal to distribute.

http://en.wikipedia.org/wiki/Copyright#Exclusive_rights


> Several exclusive rights typically attach to the holder of a copyright:
> 
> - to create derivative works (works that adapt the original work)


----------



## blade740 (Jun 2, 2009)

Can it just ignore pieces, or can it ignore single stickers as well?


----------



## jazzthief81 (Jun 2, 2009)

Doug, I'm excited to try out your modified solver! 

I'm very curious to know how you dealt with the pruning tables when you ignore pieces or restrict the moves. 

When you restrict the moves, you can still use the same tables but they will be much less effective because the values inside it will be big underestimates. 

When you ignore pieces you can generate all equivalent cases and look them up in the table and take the minimum value, or you can decide not to use the pruning tables at all. If you use the same pruning tables as is, you will probably miss solutions because the values inside it aren't necessarily underestimates.


----------



## Johannes91 (Jun 2, 2009)

jazzthief81 said:


> When you ignore pieces you can generate all equivalent cases and look them up in the table and take the minimum value, or you can decide not to use the pruning tables at all.


Or generate new tables. If many pieces are ignored they'll take much less memory.


----------



## AvGalen (Jun 2, 2009)

jazzthief81 said:


> Doug, I'm excited to try out your modified solver!
> 
> I'm very curious to know how you dealt with the pruning tables when you ignore pieces or restrict the moves.
> 
> ...


You are only excited because you will finally be able to solve the bandaged square-1 (U and R2 feature) 

Also,


> Posts: 5,000


which means that I am probably going to do that 5000 cubes in a row solve next weekend!


----------



## jazzthief81 (Jun 2, 2009)

AvGalen said:


> jazzthief81 said:
> 
> 
> > Doug, I'm excited to try out your modified solver!
> ...


Shhhhht! 



AvGalen said:


> Also,
> 
> 
> > Posts: 5,000
> ...



Need some help?


----------



## AvGalen (Jun 2, 2009)

jazzthief81 said:


> AvGalen said:
> 
> 
> > jazzthief81 said:
> ...


A cube meeting might get organised that weekend. More details tonight


----------



## deadalnix (Jun 2, 2009)

Come to nantes open and do this there ! (and bring me with you in you, I'm in Amsterdam ).

More seriously, if the solution is underestimate in the prunning table, we will only loose time, but not miss solution. I don't understand what you mean lars . . .


----------



## Johannes91 (Jun 2, 2009)

deadalnix said:


> More seriously, if the solution is underestimate in the prunning table, we will only loose time, but not miss solution.


The depths in the pruning table are lower bounds. If these are actually not lower-bounds and there could be shorter solutions, the search will back-track and miss them.

For example, the pruning table could give depth 5 for some position, but if some pieces are ignored, there might be a 4-move solution. If the search has exactly 4 moves left, it will back-track and miss the solution, because the pruning table said that the position can't be solved in less than 5 moves.


----------



## jazzthief81 (Jun 2, 2009)

deadalnix said:


> More seriously, if the solution is underestimate in the prunning table, we will only loose time, but not miss solution.



Yes, that's exactly what I meant when I talked about restricting moves, because restricting moves will only make the solutions longer:


jazzthief81 said:


> When you restrict the moves, you can still use the same tables but they will be much less effective because the values inside it will be big underestimates.



But when you ignore pieces, solutions will get shorter and the pruning values are *not* necessarily underestimates anymore and hence the conclusion:


jazzthief81 said:


> If you use the same pruning tables as is, you will probably miss solutions because the values inside it aren't necessarily underestimates.


I don't know how Doug implemented the 'ignore pieces' functionality, but I'm guessing he still fills up those positions on the puzzle with actual pieces and simply doesn't check those pieces to determine whether a position is solved.


----------



## masterofthebass (Jun 2, 2009)

as for the copyright issue:

I would assume that the open source nature of the program could maybe allow the copyright to fall under one of the many open source licenses that exist. Jaap doesn't explicitly mention how his work is copyrighted, and with the vagueness that he uses, the copyright could technically only apply to the contents of the readme


----------



## AvGalen (Jun 2, 2009)

deadalnix said:


> Come to nantes open and do this there ! (and bring me with you in you, I'm in Amsterdam ).


I actually considered that, but 5000 (+ some) solves will really take me the entire weekend. Driving and a competition would really distract me.

masterofthebass: please don't confuse open source and licensing!


----------



## Johannes91 (Jun 2, 2009)

masterofthebass said:


> I would assume that the open source nature of the program could maybe allow the copyright to fall under one of the many open source licenses that exist.


When someone releases code under a license, he still keeps the copyright, but gives other people permission to use the code under some conditions. This surely needs to be explicit. Assuming that you can use some work under the conditions of <insert your favourite license here> without asking the author isn't ok.



masterofthebass said:


> Jaap doesn't explicitly mention how his work is copyrighted, and with the vagueness that he uses, the copyright could technically only apply to the contents of the readme


There's actually no need to mention it at all under the Berne Convention. If you can show that you're the author, you have the copyright even if you haven't said it anywhere.


----------



## deadalnix (Jun 2, 2009)

Ha yes, that's obvious 

I was thinking about limitations moves (that can only incrase the solution size) but you are right, the pruning table computation have to be remade for ignored pieces.


----------



## Mike Hughey (Jun 2, 2009)

AvGalen said:


> Also,
> 
> 
> > Posts: 5,000
> ...


Ugh. I've been enjoying the fact that I've occasionally beaten you on 3x3x3 speedsolving in the weekly competitions the past few weeks. I suspect that after you do this, I'll once again be as far behind you on 3x3x3 speedsolving as I was a year or two ago.



Looking forward to seeing Arnaud averaging sub-20!


----------



## AvGalen (Jun 2, 2009)

Mike Hughey said:


> AvGalen said:
> 
> 
> > Also,
> ...


I have done all monthly competitions twice (keyhole, then F2L) in one sitting yesterday. That were 24 * 6 * 2 = 288 solves in a row. It took about 4 hours, including scrambling, inspection, writing down times, etc. I will post those results tonight and will try to see if there is an upward or downward trend in these results.

I am expecting you to easily beat me on 3x3x3 next week because my hands will probably hurt quite a lot. 

If you want to keep up with me, can I suggest you doing a 2500++ round? You actually have kids that can scramble for you, so you should be able to do that in about 20 hours


----------



## dougbenham (Jun 2, 2009)

okay so I just got home from school. now it seems that you are all quite familiar with the problems that are faced with implementing this new functionality. now first things first, i emailed jaap and he said
"Yes, go right ahead.My only condition is something you would have done anyway, and that is that you include something like 'Based on code written by Jaap Scherphuis' and the url to my site."
So I made a change to the program, at the start of the program it displays, "Jaap's Square-1 Optimizer v2.0 BETA http://www.jaapsch.net/ (modified by Doug Benham, [email protected])".

now before i give you the link to the *BETA* version of the modified solver, there are some things i must address.

"Perhaps a solution is found at a depth of 5, if you want to search further, you are now prompted to do so"
Quite simple feature, if a certain depth returns solution(s), the program displays the following line, "Continue searching? (type 'n' then press enter to stop, otherwise just press enter)", and proceeds accordingly. Quite a straight-forward change, the reason I did this was to give the option to find less than optimal solutions.

"Pieces can be ignored"
There is now another argument that you can supply to the solver. In the following format: "sq1optim A2B3C1D45E6F7G8H -t ----------------".
Now in place of each '-' you can place a certain character to specify the target piece.

- = Exact match
X = Any edge (top/bottom)
Y = Any corner (top/bottom)
K = Top layer edge
L = Bottom layer edge
M = Top layer corner
N = Bottom layer corner

"The solver can attempt to solve using only (U and R2) or (D and R2)"
There are 2 more new arguments that can optionally be supplied to the solver. '-onlytop' and '-onlybottom'. Quite simple to get the functionality working.. However, the pruning tables will not treat this well.

Last and most important issue
The pruning tables.. I have not done anything to them. Now of course you are asking, "Won't this result in unoptimized solutions?!". The answer is yes. For the moment I have only implemented the functionality of these features. Now there is a little quick and dirty fix that can help those pruning tables out. In the search() function there are a few lines of code:

```
if( pr1.table[shp ][e0][c0]>l+1 ) return(0);
if( pr2.table[shp ][e1][c1]>l+1 ) return(0);
if( pr2.table[shp2][e2][c2]>l+1 ) return(0);
```

which I changed to:

```
if( pr1.table[shp ][e0][c0]>l+[B]pruneamount[/B] ) return(0);
if( pr2.table[shp ][e1][c1]>l+[B]pruneamount[/B] ) return(0);
if( pr2.table[shp2][e2][c2]>l+[B]pruneamount[/B] ) return(0);
```

The prune amount is another optional argument that can be supplied to the solver. '-p x', x is the prune amount. By default it is 2. I would recommend a low # such as 1, 2, 3, 4, or 5. The higher the number, the less solutions the pruning will throw out, thus the more computing time necessary to find a solution. However, the lower the number, the more likely that the solver will throw out a more optimal solution.

Hopefully this little feature will result in less of the solutions being thrown out as they are deemed suboptimal. *However, this is a temporary solution and is not a good solution. I know.. you all saw the topic's title and had your hopes up high. But this project will continue and I will soon have the program functioning with correct pruning tables.

Now as for the download.. https://u.pcloud.link/publink/show?code=XZtaB97Z1Pk778JswCYfxwpKb3CoIhStK12y. It includes the newly compiled exe and the modified c++ source code file.*



Johannes91 said:


> jazzthief81 said:
> 
> 
> > When you ignore pieces you can generate all equivalent cases and look them up in the table and take the minimum value, or you can decide not to use the pruning tables at all.
> ...



Could you perhaps help me out in doing this? I'm not sure how to go about this. I've looked at JACube's source code a bit and I'm not sure how the 'ignored pieces' functionality is being put into the pruning tables.


----------



## dougbenham (Jun 2, 2009)

Here's an example for this case:







(Source: http://www.cubezone.be/square1step3.html)

Position denotes a 3 cycle of edges, including the DF, UB, and UL edges. The target state says that the only thing that matters is the orientation (all pieces must be in their correct layers, not correct position). -a states that all solutions must be found. -m states that the middle layer doesn't matter. The -w states that the solution should be optimal in the twist metric. The -p 5 helps ensure that no optimal solutions are missed. -onlytop states that only the U and R2 moves can be made (no D moves).

"sq1optim A2B5C3D41E6F7G8H -t MKMKMKMKLNLNLNLN -a -m -w -p 5 -onlytop"

Here is the output:
"Jaap's Square-1 Optimizer v2.0 BETA http://www.jaapsch.net/ (modified by Doug Benham, [email protected])

Initializing...
5. Shape transition table
4. Colouring 1 transition table
3. Colouring 2 transition table
2. Colouring 1 pruning table
1. Colouring 2 pruning table
0. Finished.

Flags: Twist Metric, Find All Solutions
Position to solve: A2B5C3D41E6F7G8H
Searching depth 0..
Searching depth 1..
Searching depth 2..
Searching depth 3..
Searching depth 4..
Searching depth 5..
Searching depth 6..
Searching depth 7..
Searching depth 8..
Searching depth 9..
Searching depth 10..
4,0/5,0/3,0/3,0/2,0/1,0/1,0/2,0/3,0/10,0/2,0 [10|21]
4,0/5,0/3,0/3,0/2,0/1,0/1,0/2,0/3,0/10,0/5,0 [10|21]
4,0/5,0/3,0/3,0/2,0/1,0/1,0/2,0/3,0/10,0/8,0 [10|21]
4,0/5,0/3,0/3,0/2,0/1,0/1,0/2,0/3,0/10,0/11,0 [10|21]
Continue searching? (type 'n' then press enter to stop, otherwise just press enter)

Searching depth 11..
4,0/3,0/2,0/3,0/1,0/2,0/2,0/1,0/3,0/3,0/10,0/2,0 [11|23]
4,0/3,0/2,0/3,0/1,0/2,0/2,0/1,0/3,0/3,0/10,0/5,0 [11|23]
4,0/3,0/2,0/3,0/1,0/2,0/2,0/1,0/3,0/3,0/10,0/8,0 [11|23]
4,0/3,0/2,0/3,0/1,0/2,0/2,0/1,0/3,0/3,0/10,0/11,0 [11|23]
4,0/5,0/3,0/1,0/2,0/2,0/1,0/3,0/3,0/1,0/9,0/2,0 [11|23]
4,0/5,0/3,0/1,0/2,0/2,0/1,0/3,0/3,0/1,0/9,0/5,0 [11|23]
4,0/5,0/3,0/1,0/2,0/2,0/1,0/3,0/3,0/1,0/9,0/8,0 [11|23]
4,0/5,0/3,0/1,0/2,0/2,0/1,0/3,0/3,0/1,0/9,0/11,0 [11|23]
4,0/5,0/3,0/3,0/2,0/1,0/1,0/2,0/3,0/4,0/6,0/2,0 [11|23]
4,0/5,0/3,0/3,0/2,0/1,0/1,0/2,0/3,0/4,0/6,0/5,0 [11|23]
4,0/5,0/3,0/3,0/2,0/1,0/1,0/2,0/3,0/4,0/6,0/8,0 [11|23]
4,0/5,0/3,0/3,0/2,0/1,0/1,0/2,0/3,0/4,0/6,0/11,0 [11|23]
Continue searching? (type 'n' then press enter to stop, otherwise just press enter)"

So at depth 10, I decided to continue searching for more solutions, resulting in the depth 11 solutions being found.

*If you have any questions, suggestions, or if you have a way to fix the pruning table problem, let me know!*


----------



## deadalnix (Jun 3, 2009)

To fix the prunning table issue, I simply suggest to compute table with the following flag :

1/ ignoring edge
2/ edge corect orientation
3/ edge corect permutation

1/ ignoring corners
2/ corners corect orientation
3/ corners corect permutation

The number of table to précompute isn't so important. I you have 2 "don't care permutation" edges, then use the 2 and if you have 2 "don't care orientation" edges, then use the 1 . The pruning table can be sub-optimal in these case, but allox an optimal solution to be found.

To allow automated computations, you should add a paramter xxx move more than optimal and xxx move max instead of press n or enter.


----------



## dougbenham (Jun 3, 2009)

deadalnix said:


> To fix the prunning table issue, I simply suggest to compute table with the following flag :
> 
> 1/ ignoring edge
> 2/ edge corect orientation
> ...



Well I understand the concept/theory behind the new tables. I'm just not sure how to programmatically implement it. Perhaps someone that is familiar with the program can help me out.

Here is a snippet of the pruning table calculator:

```
l=1;
do{
	n=0;
	if( turnMetric ){
		for( i0=0; i0<NUMSHAPES; i0++ ){
		for( i1=0; i1<70; i1++){
		for( i2=0; i2<70; i2++){
		if( table[i0][i1][i2]==l ){
		for( m=0; m<3; m++){
			j0=i0;j1=i1;j2=i2;
			w=0;
			do{
				j2=sctc.tranTable[j0][j2][m];
				j1=scte.tranTable[j0][j1][m];
				j0=stt.tranTable[j0][m];
				if( table[j0][j1][j2]==0 ){
					table[j0][j1][j2]=l+1;
					n++;
				}
				w++;
				if(w>12){
					exit(0);
				}
			}while(j0!=i0 || j1!=i1 || j2!=i2 );
		}}}}}
	}else{
		for( i0=0; i0<NUMSHAPES; i0++ ){
		for( i1=0; i1<70; i1++){
		for( i2=0; i2<70; i2++){
			if( table[i0][i1][i2]==l ){
				// do twist
				j0=stt.tranTable[i0][2];
				j1=scte.tranTable[i0][i1][2];
				j2=sctc.tranTable[i0][i2][2];
				if( table[j0][j1][j2]==0 ){
					n+=setAll(j0,j1,j2,l+1);
				}
			}
		}}}
	}
	cout<<"     l="<<(int)l<<"  n="<<(int)n<<endl<<flush;
	l++;
}while(n!=0);
```


----------



## deadalnix (Jun 3, 2009)

I don't know the program source code. But I know it use different tables when different metrics are used. So you should find somewhere a table selection/generation if it doesn't exist. It's where you should handle new cases.

Another solution is to generate the table « on the fly » adapted with the given case as JAcube does.


----------



## dougbenham (Jun 3, 2009)

deadalnix said:


> So you should find somewhere a table selection/generation if it doesn't exist. It's where you should handle new cases.


Thats exactly what I posted above. That code is the code that generates the pruning table.



deadalnix said:


> Another solution is to generate the table « on the fly » adapted with the given case as JAcube does.


This is a given. Of course it is going to need to be generated on the fly. I have looked at JACube source code and found the pruning table generation code, but I am still having difficulty understanding how it implements the 'ignore pieces' functionality.


----------



## dougbenham (Aug 19, 2017)

8 years later and I got a request to re-upload the program. You can find it here:
https://github.com/dougbenham/Square1-Optimizer

Enjoy!


----------



## 1973486 (Aug 19, 2017)

This seems quite useful, mainly just the suboptimal bit though.


----------



## LucasSousa (Jan 30, 2018)

dougbenham said:


> 8 years later and I got a request to re-upload the program. You can find it here:
> https://drive.google.com/file/d/0B-pU1cYLS-PENkdwVnZlQ3M2U1k/view?usp=sharing
> 
> Enjoy!



Very good! Thanks for the new link.
Actually can someone use this to generate good nonParity-PBL algorithms?


----------



## LucasSousa (Oct 21, 2018)

dougbenham said:


> 8 years later and I got a request to re-upload the program. You can find it here:
> https://drive.google.com/file/d/0B-pU1cYLS-PENkdwVnZlQ3M2U1k/view?usp=sharing
> 
> Enjoy!



Sad but the link broken again! If someone have the program or its sources upload it again please? Thank!


----------



## dougbenham (Oct 22, 2018)

LucasSousa said:


> Sad but the link broken again! If someone have the program or its sources upload it again please? Thank!


https://github.com/dougbenham/Square1-Optimizer


----------



## LucasSousa (Oct 31, 2018)

dougbenham said:


> https://my.pcloud.com/publink/show?code=XZtaB97Z1Pk778JswCYfxwpKb3CoIhStK12y


Thank you, man!

Can I start translating this to Java?


----------



## dougbenham (Oct 31, 2018)

LucasSousa said:


> Thank you, man!
> 
> Can I start translating this to Java?


Sure! Post up your results when you finish


----------



## N's-cvt (Apr 25, 2020)

I was trying to use the ignore function in the square-1 solver and it kept closing the program so can someone please take a look and see if there is something I am doing wrong:

D:\Games\sq1opt22>sq1optim.exe A2B3C1D45E6F7G8H -t-k-k-k----------
Jaap's Square-1 Optimizer v2.2 BETA http://www.jaapsch.net/ (modified by Doug Benham, [email protected])

Initializing...
5. Shape transition table..
4. Colouring 1 transition table..
3. Colouring 2 transition table..
2. Colouring 1 pruning table..
1. Colouring 2 pruning table..
0. Finished.

Flags: Turn Metric, Find Only First Solution
Position to solve: A2B3C1D45E6F7G8H
Searching depth 0..

"Has stopped working"


----------



## effperm (Oct 20, 2020)

dougbenham said:


> https://my.pcloud.com/publink/show?code=XZtaB97Z1Pk778JswCYfxwpKb3CoIhStK12y


"The link is deleted by the owner."
-pCloud

Can you make another link?


----------



## dougbenham (Oct 20, 2020)

f96 said:


> "The link is deleted by the owner."
> -pCloud
> 
> Can you make another link?


https://github.com/dougbenham/Square1-Optimizer


----------



## qwr (Oct 20, 2020)

dougbenham said:


> https://u.pcloud.link/publink/show?code=XZtaB97Z1Pk778JswCYfxwpKb3CoIhStK12y


please don't use these file upload sites. Put it on github or something. you can even release binaries there.


----------



## dougbenham (Oct 21, 2020)

qwr said:


> please don't use these file upload sites. Put it on github or something. you can even release binaries there.


What do you mean? This is a Google Drive alternative. What's the difference between downloading it from there or Github?


----------



## qwr (Oct 21, 2020)

dougbenham said:


> What do you mean? This is a Google Drive alternative. What's the difference between downloading it from there or Github?


these kinds of file uploading services never stick around as long as they should, as evidenced by



f96 said:


> "The link is deleted by the owner."
> -pCloud
> 
> Can you make another link?



plus they have annoying popups asking you to signup. since it's source code, you can put the code on github although idk what license it is released under.


----------



## dougbenham (Oct 21, 2020)

qwr said:


> these kinds of file uploading services never stick around as long as they should, as evidenced by
> 
> 
> 
> plus they have annoying popups asking you to signup. since it's source code, you can put the code on github although idk what license it is released under.


That makes sense. However in this case it was my fault as I really did delete the link a while back by accident. I'll put it on github when I get a moment.


----------



## dougbenham (Oct 21, 2020)

Okay, it's hosted here: https://github.com/dougbenham/Square1-Optimizer


----------



## bostoncuber314 (Jun 13, 2022)

Hi all. I'm new to the forum and very excited to join this community. I'm playing with Jaap and Doug's code, and my goal is to build an interactive Square-1 solver.

- Is there any Square-1 graphic library? I could find roofpig for the 3x3, but so far I haven't find anything similar for the Square-1. I really like cubedb.net visuals.

- Is the Square-1 solvable with only top or only bottom rotations, in general? Except for simple hand-built cases, the -onlytop and -onlybottom flags seem to loop forever.

Thanks all.


----------

