Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum
 It is currently Sat Apr 19, 2014 3:41 pm

 All times are UTC - 5 hours

 Page 1 of 1 [ 22 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: 7x7x7 solver applicationPosted: Fri Jun 10, 2011 3:06 pm

Joined: Wed Jun 08, 2011 2:39 pm

Top

 Post subject: Re: 7x7x7 solver applicationPosted: Fri Jun 10, 2011 10:15 pm

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Not that I'm aware of but then it also depends on the purpose of the program. Optimal solving of the 7x7x7 is way beyond what a classical computer will ever be able to do.

It wouldn't be too difficult to write a program that just solves in phases though. centers->edges->corners. The program doesn't actually have to be very "smart" either, you can use hill-climbing with backtracking to solve most (or all) of each phase.

I if your goal is to get a solution to a physical 7x7x7, just entering in the state would be awful, much less following the (hundreds?) of moves it would give you to solve it.

_________________
Prior to using my real name I posted under the account named bmenrigh.

Top

 Post subject: Re: 7x7x7 solver applicationPosted: Sat Jun 11, 2011 12:08 am

Joined: Mon Oct 18, 2010 10:48 am
I'm curious, how are the algorithm tables for the fastest solution for a 3x3 built (and used)?

How would it be mirrored in a 2x2? 4x4? 7x7?

_________________
--Noah

I don't know half of you half as well as I should like and I like less than half of you half as well as you deserve.

Top

 Post subject: Re: 7x7x7 solver applicationPosted: Sat Jun 11, 2011 2:12 am

Joined: Sun Oct 08, 2006 1:47 pm
Location: Houston/San Antonio, Texas
NType3 wrote:
I'm curious, how are the algorithm tables for the fastest solution for a 3x3 built (and used)?

How would it be mirrored in a 2x2? 4x4? 7x7?

The current fastest computer assisted method for solving a standard Rubik's Cube is Cube Explorer, which is largely based off of Kociemba's Algorithm.

The basic idea is that the computer searches for the shortest path from the scrambled position to a "halfway point" and then finds the shortest path from the solved position to the same "halfway point".

The interesting part is how the program defines this "halfway point". The halfway point is some state of the Rubik's Cube that can be reached by only doing the following moves: U, U2, U', D, D2, D', F2, B2, R2, L2 (so basically, you're only allowed to use 180 degree turns except both U and D may still be 90 degree turns). This alone gives quite good solutions, but I know there are also several predefined subsets of states that deviate slightly from this strategy to produce even shorter solutions. I'm not sure if the exact details of these specialized subsets are public knowledge or not...

The reason this works is the convenient and fairly effective use of this strange halfway point idea. Although the jump from scrambled to solved is too great of a distance to search by computer in a reasonable amount of time, the two individual halves of the solution are just small enough to find optimal solutions by computer in a reasonable amount of time. More info can be found here: http://kociemba.org/cube.htm. Although Cube Explorer does give very good solutions (and I mean VERY GOOD!), there is no proof that it always gives perfectly optimal solutions.

Even if you could find a way to define an effective "halfway point" for a larger puzzle (4x4 or 7x7 or others), the remaining halves will almost certianly each be much too large to solve optimally, so although it would cut down on the time required to search, it would not be enough. The next best way you could extrapolate this idea is to find multiple "checkpoints" and find optimal solutions between them. But this of course, banks on being able to conveniently define some effective checkpoints. Perhaps not impossible, but I imagine it would be quite difficult to find a set of complimentary checkpoints that actually do lead to a decent solution.

I hope this shed a little light on the subject. If anyone more experienced in the subject finds an error or can elaborate even more, feel free to point it out/do so, but this is my understanding of how it works.

Peace,
Matt Galla

Top

 Post subject: Re: 7x7x7 solver applicationPosted: Sat Jun 11, 2011 5:28 am

Joined: Fri Nov 05, 2010 2:20 am
Location: Wherever
Allagem wrote:
NType3 wrote:
U, U2, U', D, D2, D', F2, B2, R2, L2

doesnt "U, U2 U'" equal to U2? same for "D,D2,D'" so the "real" algorithm is U2,D2,F2,B2,R2,L2

_________________
A budding puzzle designer!

Check out my Shapeways shop!

Top

 Post subject: Re: 7x7x7 solver applicationPosted: Sat Jun 11, 2011 10:09 am

Joined: Mon Oct 18, 2010 10:48 am
Thank you for that immersing reply!

This makes me curious, what is god's number on a 7x7? If one can divide it up into a reasonable set of ten moves each, then, though it would take some tinkering to get the checkpoints down, it should be fully feasible.

_________________
--Noah

I don't know half of you half as well as I should like and I like less than half of you half as well as you deserve.

Top

 Post subject: Re: 7x7x7 solver applicationPosted: Sat Jun 11, 2011 3:15 pm

Joined: Sun Oct 08, 2006 1:47 pm
Location: Houston/San Antonio, Texas
rubikcollector123 wrote:
Allagem wrote:
U, U2, U', D, D2, D', F2, B2, R2, L2

doesnt "U, U2 U'" equal to U2? same for "D,D2,D'" so the "real" algorithm is U2,D2,F2,B2,R2,L2

Sorry, perhaps I didn't explain it well enough, but you are misunderstanding. U, U2, U', D, D2, D', F2, B2, R2, L2 isn't an algorithm. It's a set of allowed moves. Let me try to explain it a different way....

Imagine you had a special Rubik's Cube with some sort of weird internal mechanism. On this special Rubik's cube you can rotate the front, back, left, and right faces 180 degrees only. The U and D faces you can still rotate 90 degrees, but you are not allowed to rotate any of the other faces just 90 degrees. Now on this special puzzle you will not be able to reach every state that a normal Rubik's Cube can reach. For example, on the special puzzle the 4 edges in the middle layer between the U and D faces are stuck there - they cannot intermingle with the other edges. Also if U is white and D is yellow, then no matter how much you mix the special cube, you will only ever get white and yellow stickers on the U and D faces. In this way the orientation of every piece on the puzzle is completely determined by its location. Corners CANNOT be rotated and edges CANNOT be flipped.

NOw let's define a set G of Rubik's Cube states. A scrambled position of the Rubik's Cube is in set G if and only if it is a reachable position on this special Rubik's Cube. Now then, the way Kociemba's algorithm works is that it finds the shortest path to get a scrambled puzzle to ANY state that is in G. During this phase, the computer is allowed to use any move it wants.

After that is done, the computer switches to using the special Rubik's Cube. From now on, the computer is NOT allowed to use a 90 degree rotation of any of faces F, R, B, or L. It then finds the shortest path to solve the scrambled state in state G that it reached in the previous step. By the way when I say "the computer finds the shortest path", I mean that it basically tries all possible moves and checks to see if they would accomplish the goal. If not, it tries longer and longer sequences until it finds a solution.

Is that better?

Peace,
Matt Galla

Top

 Post subject: Re: 7x7x7 solver applicationPosted: Sat Jun 11, 2011 3:26 pm

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
NType3 wrote:
Thank you for that immersing reply!

This makes me curious, what is god's number on a 7x7? If one can divide it up into a reasonable set of ten moves each, then, though it would take some tinkering to get the checkpoints down, it should be fully feasible.

Unfortunately this won't find an optimal solution, just a pretty good one. To see why, suppose you are a few 10s of moves away from reducing the puzzle to a 3x3x3 (say 30 moves). There could be hundreds of choices of the 10, 10, 10 moves you did to reduce the puzzle. All may seem equivalent but some may reduce to a 3x3x3 that can be solved in 14 moves while another choice may reduce to a 3x3x3 that needs 18 moves. Since there isn't really a way to anticipate how seemingly equivalent choices now will affect the available choices later setting fixed checkpoints usually prevents a truly optimal solution from being found.

Your idea of setting checkpoints and slowly working your way through them via brute-force is a viable computer solving strategy and it is roughly what I was referring to when I said "hill-climbing". You usually wouldn't specify a fixed number of moves for each checkpoint though. For edge pairing for example, you might decide to pair one edge group at a time. It may turn out that for the first few pairs you only need 3 moves each. You'd set progress-based rather than move-based goals.

_________________
Prior to using my real name I posted under the account named bmenrigh.

Top

 Post subject: Re: 7x7x7 solver applicationPosted: Sat Jun 11, 2011 4:33 pm

Joined: Mon Oct 18, 2010 10:48 am

As in, have the program solve the 7x7 to a state from inside to outside where all the layers operate and have the same 'pieces' as a 3x3.

For example, the inner edges of a 7x7 form 3x3 edge pairs, as well as the corners. Then, it 'pairs' the next set of centers outward, and so on. That way, you turn a 7x7 into three consecutive 3x3 solves.

Edit: Has anyone here programmed something like this? I'd like a couple tips as to how to set up a virtual 7x7 (using java, but you don't need to know it to give advice )

_________________
--Noah

I don't know half of you half as well as I should like and I like less than half of you half as well as you deserve.

Top

 Post subject: Re: 7x7x7 solver applicationPosted: Mon Jun 13, 2011 2:18 pm

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
NType3 wrote:
Edit: Has anyone here programmed something like this? I'd like a couple tips as to how to set up a virtual 7x7 (using java, but you don't need to know it to give advice )

I'm sure there are NxNxN solvers out there, I seem to remember coming across a few. I think Don Hatch even wrote a N^M solver for n >= 2 and m >= 3.

I don't think anyone has written a 7x7x7 solver with efficiency/fewest moves in mind though.

If you are going to write a solver, I'd suggest doing it piece+twist based rather than sticker based. For the 1-sticker center pieces it doesn't matter but for the edges and corners having a piece+twist based puzzle is much for flexible when you want to check for certain properties. I wrote a Pentultimate solver that was sticker-based and I ended up having to re-write it as piece+twist based to classify the routines it found and to make other things much easier.

As for actually programming the twists, I have never figured out a good, generic way to implement all of the different orientations for the same twist in the same code. That is, turning U is really the same as turning D if you just reorient D so that it is in the U position. Of course the same goes for all of the other faces. I know others such as Gelatinbrain have figured this out. I end up having to manually define what pieces go where and how they twist for each of the different possible moves. It would be much better to figure out how to more generically determine all of the variations from one meta-twist description. That is, program the essence of what a twist is, not the mechanics of how a F or a U or a whatever twist actually works. I tried looking at the source code to some other Rubik's cube programs to see how they did it but I never studied their implementation well enough to figure it out.

I did see one very compact implementation by Andrey Astrelin of a 3x3x3x3 and instead of defining a 4-dimensional array of pieces he defined a 5-dimensional array. One set of nested for-loops handled all the different twist types including slices with a slice mask. It was quite impressive but I didn't understand how to apply that concept to other puzzles.

One thing that might help is that when you are updating the state of the puzzle during a twist, don't try to do it in-place. Just copy the updated state of each piece to the new location in a new puzzle state and then replace the old state with the new one.

I've very busy over the next 2+ months moving to a new location with a new job otherwise I'd probably write a solver myself. If you do end up writing one it would be fun to see who can optimize the program's solving strategy the best to get the fewest moves to solve a 7x7x7.

_________________
Prior to using my real name I posted under the account named bmenrigh.

Top

 Post subject: Re: 7x7x7 solver applicationPosted: Mon Jun 13, 2011 2:55 pm

Joined: Fri Feb 08, 2008 1:47 am
Location: near Utrecht, Netherlands
Jaap's Website is an absolutely fantastic resource if you want to make your own solver: http://www.jaapsch.net/puzzles/compcube.htm
It deals with making indices and transition tables. If you break the 7x7x7 down in to subsections (such as permutation and (if applicable) orientation for each type of piece) then you could make an index and build a transition table for each of those.
Clearly the algorithm he describes takes far too much time for solving a 7x7x7 but if you set sub-goals the time will be acceptable. Trying to find a 50 move solution using IDA* would take far too much time (10^50 is a huge number) but if you set 10 sub goals which each take 10 moves to reach you end up with a 100 move solution but it takes only 10*10^10=10^11 time which is far more acceptable.

Writing the code for simulating moves is not very nice. It takes very good spacial thinking to track the pieces as they move and write the appropriate code. I made a 2x2x2 solver and it took my friend hours to figure out which way the pieces moved around and it took even more time to get the bugs worked out.
If you want to simulate the permutation of a 2x2x2, you should start with an array of length 8 and start out with A[] = {0, 1, 2, 3, 4, 5, 6, 7, 8} as the solved position. To do a U move you could write something like "temp=A[0]; A[0] = A[3]; A[1] = A[2]; A[2] = A[1]; A[1] = temp;".

_________________
Tom's Shapeways Puzzle Shop - your order from my shop includes free stickers!
Tom's Puzzle Website

Buy my mass produced puzzles at Mefferts:

Top

 Post subject: Re: 7x7x7 solver applicationPosted: Mon Jun 13, 2011 3:31 pm

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
TomZ wrote:
Writing the code for simulating moves is not very nice. It takes very good spacial thinking to track the pieces as they move and write the appropriate code. I made a 2x2x2 solver and it took my friend hours to figure out which way the pieces moved around and it took even more time to get the bugs worked out.
If you want to simulate the permutation of a 2x2x2, you should start with an array of length 8 and start out with A[] = {0, 1, 2, 3, 4, 5, 6, 7, 8} as the solved position. To do a U move you could write something like "temp=A[0]; A[0] = A[3]; A[1] = A[2]; A[2] = A[1]; A[1] = temp;".

I wound up taking this approach too. For example, here is a snippet for handing a penultimate face twist:

Code:
[ # face 1 (light blue)
[[5, 1, 0, 3, 4, 10,
2, 7, 8, 9, 6, 11],
[2, 1, 1, 0, 0, 0,
1, 0, 0, 0, 1, 0]],
[[0, 4, 3, 8, 13,
5, 6, 2, 12, 9,
10, 1, 7, 17, 14,
15, 16, 11, 18, 19],
[0, 2, 1, 1, 0,
0, 0, 0, 0, 0,
0, 0, 1, 2, 0,
0, 0, 2, 0, 0]]
],
[ # face 2 (green)
[[1, 6, 2, 0, 4, 5,
7, 3, 8, 9, 10, 11],
[1, 0, 1, 2, 0, 0,
1, 1, 0, 0, 0, 0]],
[[3, 2, 7, 12, 4,
5, 1, 11, 8, 9,
0, 6, 18, 13, 14,
15, 16, 17, 10, 19],
[2, 1, 1, 0, 0,
0, 0, 0, 0, 0,
0, 1, 2, 0, 0,
0, 0, 0, 2, 0]]
],

That's a [4][] array for each move where [0][] is centers, [1][] is center twists, [2][] is corners and [3][] is corner twists. Using this strategy though you have to manually define the the permutation and orientation effects for each twist. I'm SURE there is a way to program it such that you only have to specify how a single twist works and then via some logic and geometry that automatically defines what moves and what gets twisted for all moves. It's pretty tedious and error-prone to define the permutations and orientations for each move. I just haven't figured out how to take the additional step of abstraction to reduce the per-twist definitions.

_________________
Prior to using my real name I posted under the account named bmenrigh.

Top

 Post subject: Re: 7x7x7 solver applicationPosted: Mon Jun 13, 2011 5:44 pm

Joined: Mon Oct 18, 2010 10:48 am
Okay, thanks! Got all that.

My question is, how do you keep track of orientation? What reference point do you have and how do you use it?

_________________
--Noah

I don't know half of you half as well as I should like and I like less than half of you half as well as you deserve.

Top

 Post subject: Re: 7x7x7 solver applicationPosted: Mon Jun 13, 2011 5:57 pm

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
NType3 wrote:
Okay, thanks! Got all that.

My question is, how do you keep track of orientation? What reference point do you have and how do you use it?

It sounds hard but it actually turns out to be quite easy. For corners you arbitrarily pick a 0-sticker, 1-sticker, and a 2-sticker. Then when you do a move, you look at a piece that has moved and if it's 0-sticker moves into the spot that was occupied by the 0-sticker then the twist is +0. If it moves into the 1-sticker spot the move does +1 twist, etc.

So to use a cube for example, I'd label the U face (say, white) stickers as the 0-sticker for each of the 4 top corners. Then looking at that piece and moving clockwise the next sticker would be the 1-sticker and the other the 2-sticker. For the bottom I'd label the bottom face (say, yellow) as the 0-sticker and number the others clockwise like the top.

If you did this then a turn of the top face would do +0 twist to the top 4 corners (that is, no twist). A clockwise twist of the F face would move the bottom-left corner to the top-left corner and the 0-sticker would move into the 2-sticker spot to that corner would be twisted +2. The top-left corer would move to the top-right corner and the 0-sticker would move to the 1-sticker position so that would do +1 twist. You get the idea.

To track twist you just do "current_twist + new_twist modulus 3".

The actual labels you pick for the {0,1,2} stickers for each piece doesn't matter as long as you are consistent. I'd pick something that seems logical and is easy for you to figure out the twist of each piece for each move.

For the 2-sticker pieces like edges you use the same strategy but you only have +0 and +1 twist and the modulus is 2.

For the face centers of a cube you have +0, through +3 twist modulus 4.

Hopefully this description isn't too complicated.

_________________
Prior to using my real name I posted under the account named bmenrigh.

Top

 Post subject: Re: 7x7x7 solver applicationPosted: Mon Jun 13, 2011 6:15 pm

Joined: Mon Oct 18, 2010 10:48 am
And, when the cube is solved, the numbers assigned to the stickers on each corner is the same?

_________________
--Noah

I don't know half of you half as well as I should like and I like less than half of you half as well as you deserve.

Top

 Post subject: Re: 7x7x7 solver applicationPosted: Mon Jun 13, 2011 6:24 pm

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
NType3 wrote:
And, when the cube is solved, the numbers assigned to the stickers on each corner is the same?
Yeah in the solved state the 0-sticker is in the 0-spot and so forth for every piece. That is, every piece has a twist of 0. When the puzzle isn't solved, if you can still say things like "this piece is in the wrong position but the orientation is correct (because the twist is 0)" or even "this piece is in the correct position but the orientation is wrong".

If you program the puzzle sticker by sticker rather than piece+orientation it is hard to tell if a piece is in the right spot but has the wrong orientation. It also allows you to tell how pieces twist in 3-cycles.

_________________
Prior to using my real name I posted under the account named bmenrigh.

Top

 Post subject: Re: 7x7x7 solver applicationPosted: Mon Jun 13, 2011 6:57 pm

Joined: Mon Oct 18, 2010 10:48 am
How do the pieces correlate to each other, though? It doesn't make sense to be able to assign any random number of the three to a sticker, so long as each corner has all three numbers.

_________________
--Noah

I don't know half of you half as well as I should like and I like less than half of you half as well as you deserve.

Top

 Post subject: Re: 7x7x7 solver applicationPosted: Mon Jun 13, 2011 7:09 pm

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
NType3 wrote:
How do the pieces correlate to each other, though? It doesn't make sense to be able to assign any random number of the three to a sticker, so long as each corner has all three numbers.

In absolute terms the meaning of twist is ambiguous or undefined. All that matters is what happens when you do a move and that twist is relative. A piece moves from some arbitrary defined set of labels to another. You can setup the labels in any way you want. In one labeling system a twist of the U face might not change the orientations of any piece and with a different set of labels it does. The important thing is that you whatever labeling system you pick, you stick with it for defining what happens for each move. If you do then twists will always be tracked properly. It is the relative change in orientation from one position to another during a twist that matters. No matter how you pick your labeling, you will see that twisting the same face 4 times in a row always cancels out any orientation changes and the net change of each piece is 0.

I guess that's probably pretty confusing. You really shouldn't pick some crazy labeling though. I think my original suggestion of making the U face stickers 0 for the top corners and the D face stickers 0 for the bottom corners and then setting the remaining stickers on each piece to 1 and 2 clockwise about the piece makes the most sense. It means that twists of the U and D faces are +0 twist for all of their corners. It also means that F2, B2, R2, L2 is also +0 twist for all corners.

_________________
Prior to using my real name I posted under the account named bmenrigh.

Top

 Post subject: Re: 7x7x7 solver applicationPosted: Mon Jun 13, 2011 7:36 pm

Joined: Mon Oct 18, 2010 10:48 am

So for the edge pieces, would the same system effectively remain? The top and bottom stickers are 0, and the opposite stickers are 1? If so, what happens to the middle edges?

Would it be easier, for the edges, to make opposite faces be the same number?

_________________
--Noah

I don't know half of you half as well as I should like and I like less than half of you half as well as you deserve.

Top

 Post subject: Re: 7x7x7 solver applicationPosted: Mon Jun 13, 2011 7:46 pm

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
NType3 wrote:

So for the edge pieces, would the same system effectively remain? The top and bottom stickers are 0, and the opposite stickers are 1? If so, what happens to the middle edges?

Would it be easier, for the edges, to make opposite faces be the same number?
Yeah you should start with a 3x3x3 if only because it feel good to make progress and when you take on too much at once it's easy to get bogged down and not make as much progress.

For edges, you would use the same system where the top and bottom stickers are 0. For the middle edges the choice is mostly arbitrary. If I were labeling them I'd make the right sticker 0. That is, when you are holding the cube upright and looking straight at the edge then the right sticker would be 0 and the left one 1. That would mean that if you turned the F face clockwise the left middle edge would move to the top and the twist would be +1. The top edge would move to the middle right and the twist would be +0, etc.

Just to be clear, while corners are mod 3, edges are mod 2.

So for edges 1 twist + 1 twist = 0 twist
For corners 1 twist + 1 twist = 2 twist and 2 twist + 2 twist = 1 twist and so forth.

When you get your 3x3x3 programed you should do some basic checks like turning each face 4 times to make sure the cube is still solved. If you make any mistakes usually they show up in simple checks. I know when I programmed the Pentultimate this way I made a ton of mistakes. You get much better at it with practice.

_________________
Prior to using my real name I posted under the account named bmenrigh.

Top

 Post subject: Re: 7x7x7 solver applicationPosted: Mon Jun 13, 2011 8:30 pm

Joined: Mon Oct 18, 2010 10:48 am

I'll post back here with updates and such.

_________________
--Noah

I don't know half of you half as well as I should like and I like less than half of you half as well as you deserve.

Top

 Post subject: Re: 7x7x7 solver applicationPosted: Tue Jun 14, 2011 9:14 pm

Joined: Wed May 13, 2009 4:58 pm
Location: Vancouver, Washington
bmenrigh wrote:
I've very busy over the next 2+ months moving to a new location with a new job otherwise I'd probably write a solver myself. If you do end up writing one it would be fun to see who can optimize the program's solving strategy the best to get the fewest moves to solve a 7x7x7.
That would be fun. This reminds me of a competition to build a solve for the 3x3x3 (Just fyi, it is incredibly hard to find what you want searching for "fastest solver" or "shortest algorithm" ). They rated programs by code length, speed, and solution length. The first rating clearly led to crazy obfuscation with macros and such, but the other two parameters would be great metrics. Contest Rules - Winners

I'm curious what other solving method people might come up with. If anyone organizes a competition, I would love to try. I don't know how much time I could put into it (I should be working on my thesis), but I'd love to take a shot.

btw, gl with the move & job.

_________________
Real name: Landon Kryger

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 22 posts ]

 All times are UTC - 5 hours

#### Who is online

Users browsing this forum: No registered users and 1 guest

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ Announcements General Puzzle Topics New Puzzles Puzzle Building and Modding Puzzle Collecting Solving Puzzles Marketplace Non-Twisty Puzzles Site Comments, Suggestions & Questions Content Moderators Off Topic