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

TwistyPuzzles.com Forum

It is currently Thu Apr 17, 2014 5:42 am

All times are UTC - 5 hours



Post new topic Reply to topic  [ 6 posts ] 
Author Message
 Post subject: Oskar's Gear Shift - Solved by Brute Force
PostPosted: Tue Nov 16, 2010 4:27 pm 
Offline
User avatar

Joined: Wed Jan 07, 2009 6:46 pm
Location: Evanston, IL
Hey everyone,

I recently bought a Gear Shift from Oskar's Shapeways shop http://www.shapeways.com/model/139482/gear_shift.html and I am very happy with it. It is very fun to play with, and it looks really cool when scrambled, but it is difficult to solve, as you have to constantly keep track of the orientation of all the gears.

Luckily, I have a good friend who is a computer science major here at the University of Colorado, and yesterday he wrote a python program to solve the Gear Shift by brute force. Don't worry. No sledge hammers were used.

It does it by doing a breadth-first search of the solution tree. It starts at the scrambled state, and then checks every possible move from there. The beauty is that this puzzle has few enough possible positions that it is not too costly to brute-force the solution.

Actually, we figured out that the puzzle has exactly 1.28 million possible states, which is half the number of possible orientations in which you can place the gears simply by removing them and putting them in however you want. It is possible to end up with it all solved except for a small gear out of place by 1 tooth, but it is impossible to end up with only a big gear turned by 1 tooth, or by any odd number of teeth.

If you have python, feel free to try it out. To run the program, simply scramble your gear-shift, orient the cube with a big gear in the UBL corner, and count the offset of each gear (i.e. how many teeth counter-clockwise is the gear rotated away from the solved orientation). Then open the terminal or command line, navigate to the right folder, and type "python gearshift.py 0 0 0 0 0 0 0 0 ", where you replace each 0 by the counter-clockwise offsets of the scrambled state (look at the source file for an ASCII picture of the cube with the corners labeled). The program will list out the state tree (this should take about 1 to 2 minutes, as it is listing out hundreds of thousands of states), and then it will give you something like:
U x 17
F x 5
L x -15

Again, these are counter-clockwise gear-tooth turns for a large gear on the face that it references. Since this puzzle is linear, these moves can be applied in any order! I don't know of any other puzzle with that property!

The idea behind the program is as follows:
- There are 8 gears. 4 of them have 5 teeth, and 4 of them have 8 teeth.
- A particular state of the puzzle is represented by 8 numbers, corresponding to the counter-clockwise displacement of each gear from its solved orientation. Small gears have orientation 0 through 4, and big gears have orientation 0 through 7. (Orientation state 8 is the same as 0 for a big gear, just as orientation state 5 is the same as 0 for as small gear).
- When you turn a gear on one face by 1 tooth, the similarly sized gear on the diagonal corner turns by 1 tooth in the same clock direction, and the two gears of the other size each turn by 1 tooth in the opposite clock direction.
- For example, if you turn one of the big gears a full revolution counter-clockwise (+8 teeth), the small gears on the face will turn -8 teeth. Now the big gears will be at position 0, and the small gears will be at position -8, which simplifies to position 2 (2 teeth counterclockwise from the starting position).
- Using these rules, the program builds a tree from the scrambled state you give it, and expands the tree until it reaches the state 0 0 0 0 0 0 0 0, where all the gears are in the solved position.

I have attached the file. Since the .py extension is not allowed, I changed the extension to .txt to upload it. Change it back to .py when you download it and it should work fine.

I think that the only impossible states on this puzzle are all equivalent to having the entire puzzle solved except for a big gear rotated by an odd number of teeth. Let me know if you find any more.

This program is by DJ Sutton. Feel free to modify it as you see fit. If you make anything interesting out of it, let us know!

-π (Eitan)


Attachments:
File comment: Change the extension to .py
gearshift.txt [2.47 KiB]
Downloaded 80 times

_________________
Eitan = "EIGHT-ahn"
Buy a Radio Cube 3! Only $150 at Eitan's Shapeways Shop
Check out my video: Twisty Puzzles a la Vi

Top
 Profile  
 
 Post subject: Re: Oskar's Gear Shift - Solved by Brute Force
PostPosted: Tue Nov 16, 2010 7:17 pm 
Offline
User avatar

Joined: Wed May 13, 2009 4:58 pm
Location: Vancouver, Washington
pirsquared wrote:
Since this puzzle is linear, these moves can be applied in any order!
That is a very interesting property. It means you can prune down your search space drastically.
pirsquared wrote:
This program is by DJ Sutton. Feel free to modify it as you see fit. If you make anything interesting out of it, let us know!
Using the knowledge that order doesn't matter, I tried to make something faster and here's what I have. It is used the exact same way as the one you posted. It gives a different result for 0 0 0 0 0 0 2 0. Can you confirm/deny that my solution works too? I don't have a real gear shift to play with :(

btw, you should comment out the print on line 78, that really slows it down.

*edit* I assumed you only need 4 sides to solve this. Is that wrong?

*edit2* this version had a bug, check a few posts down

_________________
Real name: Landon Kryger


Last edited by GuiltyBystander on Wed Nov 17, 2010 11:15 am, edited 1 time in total.

Top
 Profile  
 
 Post subject: Re: Oskar's Gear Shift - Solved by Brute Force
PostPosted: Tue Nov 16, 2010 9:06 pm 
Offline

Joined: Sat Mar 22, 2003 9:11 am
Location: Marin, CA
Here's a more reasonable hand approach -

1) Rotate the back face until the top back right and top back left corners are done

2) Rotate the bottom face until the bottom back right and bottom back left corners are done

3) Rotate the front face until the bottom front right and bottom front left corners are done

4) Rotate the the right and left faces by some formula (more on this at the bottom)

5) Do steps 1-3 again, and the puzzle will be solved.

Step 4 is the one which is interesting to figure out. Basically, each unit you move the right will result in a particular amount of moving the top front modulo 40, so you should be able to figure things out just based on the positions of those two gears and just moving the right. I think that's more difficult to calculate than one might like though, so instead it's probably better to use the right and left separately.

If you orient the cube so that the top front right gear has 8 teeth, then rotating the right a multiple of 8 will result in that gear being back to where it started after repeating steps 1-3, so what you should be able to do is look at the number of teeth the top front left needs to rotate, and then rotate the right several complete rotations, so the top front right is in the same orientation it was to begin with. How many units each of those complete rotations turns the top front left is annoying to work out by hand - probably your best bet is to try it and see.

You then rotate the left a number of complete rotations of the top front left, and you're all set for the top front right to be fixed after repeating steps 1-3 as well.

It's a little funny to be talking about this puzzle via sequences, because it's completely linear and can be solved much more quickly based on linear equations modulo 40. But it is nice that there are approaches which are reasonable to do by hand.


Top
 Profile  
 
 Post subject: Re: Oskar's Gear Shift - Solved by Brute Force
PostPosted: Wed Nov 17, 2010 9:59 am 
Offline
User avatar

Joined: Wed Jan 07, 2009 6:46 pm
Location: Evanston, IL
Bram wrote:
btw, you should comment out the print on line 78, that really slows it down.

*edit* I assumed you only need 4 sides to solve this. Is that wrong?


That sped it up immensely. But I think you need all 8 sides, don't you?

Bram wrote:
Here's a more reasonable hand approach -
1) Rotate the back face until the top back right and top back left corners are done
2) Rotate the bottom face until the bottom back right and bottom back left corners are done
3) Rotate the front face until the bottom front right and bottom front left corners are done
4) Rotate the the right and left faces by some formula (more on this at the bottom)
5) Do steps 1-3 again, and the puzzle will be solved.

Thanks Bram! I'll definitely try this out!

-π (Eitan)

_________________
Eitan = "EIGHT-ahn"
Buy a Radio Cube 3! Only $150 at Eitan's Shapeways Shop
Check out my video: Twisty Puzzles a la Vi



Top
 Profile  
 
 Post subject: Re: Oskar's Gear Shift - Solved by Brute Force
PostPosted: Wed Nov 17, 2010 11:27 am 
Offline
User avatar

Joined: Wed May 13, 2009 4:58 pm
Location: Vancouver, Washington
pirsquared wrote:
But I think you need all 8 sides, don't you?
I'm guessing you mean 6.

You can never need all six. This is because (U D)x n == (R L) x n == (F B) x n. You can always use one pair to eliminate one other side.
Let pretend the solution is

U: 5
D: 7
R: 17
L: 12
F: 9
B: 6

Applying (U D)x - 5 (R L)x 5 does nothing to the puzzle but it modifies our counts.

U: 0
D: 2
R: 22
L: 17
F: 9
B: 6

We can do this again by applying (R L)x -17 (F B)x17. Again, this does nothing to the pieces, but it does modify our move counts.

U: 0
D: 2
R: 5
L: 0
F: 9
B: 6

I guess this proves you only need to use 4 sides to solve the puzzle. Or as my program solves it, you only need 3 sides + closed form rotation.

I forgot to take some debugging stuff out on the last version I uploaded. Here's a new one.


Attachments:
gearshift2.txt [3.06 KiB]
Downloaded 67 times

_________________
Real name: Landon Kryger
Top
 Profile  
 
 Post subject: Re: Oskar's Gear Shift - Solved by Brute Force
PostPosted: Wed Nov 17, 2010 11:41 am 
Offline
User avatar

Joined: Wed Jan 07, 2009 6:46 pm
Location: Evanston, IL
GuiltyBystander wrote:
I'm guessing you mean 6.


I definitely meant 6. Thanks.

GuiltyBystander wrote:
I guess this proves you only need to use 4 sides to solve the puzzle. Or as my program solves it, you only need 3 sides + closed form rotation.


Cool! I'll pass these notes along to my comp sci friend.

-pi (Eitan)

_________________
Eitan = "EIGHT-ahn"
Buy a Radio Cube 3! Only $150 at Eitan's Shapeways Shop
Check out my video: Twisty Puzzles a la Vi



Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 6 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: No registered users and 3 guests


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

Search for:
Jump to:  

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group