Solving the cube puzzle (programatically)
Daniel Kersten
As most of you know, we tried to solve those cube puzzles that Google brought by writing a solver program in Python :-)
If anyone else is interested, our efforts are on github: http://github.com/dublindan/pycon_cube
Feel free to join in! If anyone wants commit access, just give me your github username and I'll add you. Or fork the repository and send me pull requests - whichever you prefer.
Hoping to soon solve the puzzle :-D
Dan.
--
Daniel Kersten.
Barry Alistair
--
You received this message because you are subscribed to the Google Groups "Python Ireland" group.
To post to this group, send email to python...@googlegroups.com.
To unsubscribe from this group, send email to pythonirelan...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/pythonireland?hl=en.
Daniel Kersten
So far, theres code for placing, rotating and moving the shapes around and calculating collisions. The actual "solving" is still a work in progress.
Some interesting solutions have been proposed. Maciej and Tim and others are working on a genetic algorithm, I believe. I am looking at using simulated annealing. Other people are trying other approaches. Fun for everyone.
Daniel Kersten.
Leveraging dynamic paradigms since the synergies of 1985.
Maciej Bliziński
> Yes, we heard that too. Thats what makes this an interesting puzzle to try
> and solve using Python!
>
> So far, theres code for placing, rotating and moving the shapes around and
> calculating collisions. The actual "solving" is still a work in progress.
> Some interesting solutions have been proposed. Maciej and Tim and others are
> working on a genetic algorithm, I believe. I am looking at using simulated
> annealing. Other people are trying other approaches. Fun for everyone.
solutions to a similar puzzle, Soma Cube: "these are easily generated
by a simple recursive backtracking search". I myself warmed up to the
idea of an exhaustive search, as it cuts off large branches of the
tree early on. It would be cool to find all the solutions!
Here is the rundown of tasks:
- data entry - done
- puzzle piece parser - Victor Hugo, done
- rotation - Maciej, x done, y and z underway
- moving - Victor Hugo, down/right are done, left/up underway
- searching the solution space - Raphael - underway
I think it's best if we try few different approaches to the solution
space search.
Maciej
Maciej Bliziński
> - data entry - done
> - puzzle piece parser - Victor Hugo, done
> - rotation - Maciej, x done, y and z underway
I've finished that part. There's also code for generating all 24 rotations.
> - moving - Victor Hugo, down/right are done, left/up underway
In total, 6 directions are needed, we have 2 now.
Anybody else made progress?
I've created a separate utility script to display the pieces. I think
that we might have some errors in the data entry.
http://paste.pocoo.org/show/239943/
Maciej
Victor Hugo Germano
I did the cube.py class in a hurry... so plz, be merciful with the
quality of the code.. :)
2010/7/21 Victor Hugo Germano <vict...@gmail.com>:
> hey there...
>
> the cube.py file has a algoritm to:
> - move all possible position on a 2d space, generating (without
> rotation) 136 diferent position for the pieces
> which mean that we only need to:
> (pseudo code)
>
> for each piece:
> - Move down and right untill u cannot move anymore (already working)
> - get the next rotation for that piece
> - start over
>
>
> at the end we will have all the possible rotations/movements for each piece
>
> cheers
>
>
>
>
> 2010/7/21 Maciej Bliziński <maciej.b...@gmail.com>:
>> --
>> You received this message because you are subscribed to the Google Groups "Python Ireland" group.
>> To post to this group, send email to python...@googlegroups.com.
>> To unsubscribe from this group, send email to pythonirelan...@googlegroups.com.
>> For more options, visit this group at http://groups.google.com/group/pythonireland?hl=en.
>>
>>
>
>
>
> --
>
> Victor Hugo Germano
> Fone: Ireland, Dublin - 0852442485
> Email: vict...@gmail.com
> Skype: victorhugogermano
>
--
Victor Hugo Germano
Fone: Ireland, Dublin - 0852442485
Email: vict...@gmail.com
Skype: victorhugogermano
Victor Hugo Germano
the cube.py file has a algoritm to:
- move all possible position on a 2d space, generating (without
rotation) 136 diferent position for the pieces
which mean that we only need to:
(pseudo code)
for each piece:
- Move down and right untill u cannot move anymore (already working)
- get the next rotation for that piece
- start over
at the end we will have all the possible rotations/movements for each piece
cheers
2010/7/21 Maciej Bliziński <maciej.b...@gmail.com>:
> --
> You received this message because you are subscribed to the Google Groups "Python Ireland" group.
> To post to this group, send email to python...@googlegroups.com.
> To unsubscribe from this group, send email to pythonirelan...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/pythonireland?hl=en.
>
>
--
Victor Hugo Germano
Daniel Kersten
Maciej Bliziński
> hey there...
>
> the cube.py file has a algoritm to:
> - move all possible position on a 2d space, generating (without
> rotation) 136 diferent position for the pieces
> which mean that we only need to:
> (pseudo code)
>
> for each piece:
> - Move down and right untill u cannot move anymore (already working)
I think you need to use 3 directions to make sure it's in a corner.
> - get the next rotation for that piece
Yes, that'll be given as a list; there's a function that expands one
listo-format piece to its 24 rotations.
> - start over
>
> at the end we will have all the possible rotations/movements for each piece
Cool.
There's still something wrong with the displaying of the pieces, I've
tried to find out where the bug is, but I didn't succeed. Will look
more into it tomorrow.
Maciej Bliziński
> I believe make_binary works now. In my tests it was shifted left one bit, so
> I adjusted it by specifying start=1 in the enumerate (so the range is now
> 2**63 ... 2**0, instead of 2**64 ... 2**1).
Yup, it's working fine now. I've started another branch, called
visual-data, e.g.:
http://paste.pocoo.org/show/241181/
This way it's easier to read.
I also finished the code generating all the rotations and all the
positions. If you call the MatcherData() method of the AllTheWays
class, you'll get the data ready for use for any solution seeking
algorithm.
Victor, I couldn't really use your piece moving code, because it
wasn't generic enough to extend it to all 6 directions. Instead, I've
hard-coded a move in one directions and extended it to all 6
directions by rotating the piece pre- and post-move. The Mover class
is now in the pieces.py file.
Daniel Kersten
I'm ever so slowly working on two different things (though at the speed I'm going, I won't promise anything). One is a simulated annealing approach to solving the cube and the other is using pyglet and opengl to visualise the pieces in 3D. Not really putting too much effort into it at the moment, but having fun with it anyway :-) I suppose I should commit it to github, though its just tinkering and experimenting at the moment.
2010/7/25 Maciej Bliziński <maciej.b...@gmail.com>2010/7/24 Maciej Bliziński <maciej.b...@gmail.com>:
> I also finished the code generating all the rotations and all the
> positions. If you call the MatcherData() method of the AllTheWays
> class, you'll get the data ready for use for any solution seeking
> algorithm.
I've made more progress: the first implementation of the recursive
backtracking search is working, albeit slowly.
The existing code is here:
http://github.com/dublindan/pycon_cube/tree/visual-data
The way to run the script is:
./puzzle_tool.py -l
So far, I haven't found a single solution. What do you guys think
would be the best way to improve this program?
Maciej
--
You received this message because you are subscribed to the Google Groups "Python Ireland" group.
To post to this group, send email to python...@googlegroups.com.
To unsubscribe from this group, send email to pythonirelan...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/pythonireland?hl=en.
--
Daniel Kersten.
Leveraging dynamic paradigms since the synergies of 1985.
Maciej Bliziński
> I suppose I should commit it to github, though
> its just tinkering and experimenting at the moment.
You can experiment in a separate branch, and push that branch to
github, just the way the visual-data branch pushed. It's always fun
to see what other people are coding!
Maciej Bliziński
> I wonder is there any opportunities to run the recursive backtracking
> algorithm in parallel using multiprocessing? Looking at the code, I don't
> see any obvious areas to parallelise... Though, even just starting two
> instances searching from either end of the search space might help?
The solution space can be certainly divided into disjunctive parts.
I'm not sure how difficult would it be to make the parts equal in size
(or computation time).
For starters, you can divide the space by the first element. For
example, you can start with [0] instead of [] and stop when it reaches
[1]. There are 384 rotations and positions of the first element, so
you can relatively easily divide the search among 384 workers.
Maciej Bliziński
> Could anyone provide a definition of the original problem itself? (I
> never saw the cube!)
It's the Bedlam Cube:
http://en.wikipedia.org/wiki/Bedlam_cube
A little bit like 3D Tetris, but here you have a fixed set of blocks
and no time constraints. However, you have to make them fit into a
perfect 4x4x4 cube. The idea is to find a solution, i.e. the way to
fit them all. Finding all solutions (there is more than just one)
would be even better.
Maciej Bliziński
http://www.danieltebbutt.com/bedlam.html
It's depressingly fast. It takes it between one and two seconds to
find a random solution.
Kevin Noonan
This sounds cool. I like the way you're collaborating on the solution.
Could anyone provide a definition of the original problem itself? (I
never saw the cube!)
Ciao,
Kevin.
Daniel Kersten
2010/7/24 Maciej Bliziński <maciej.b...@gmail.com>:
> I also finished the code generating all the rotations and all the
> positions. If you call the MatcherData() method of the AllTheWays
> class, you'll get the data ready for use for any solution seeking
> algorithm.
I've made more progress: the first implementation of the recursive
backtracking search is working, albeit slowly.
The existing code is here:
http://github.com/dublindan/pycon_cube/tree/visual-data
The way to run the script is:
./puzzle_tool.py -l
So far, I haven't found a single solution. What do you guys think
would be the best way to improve this program?
Maciej
--
You received this message because you are subscribed to the Google Groups "Python Ireland" group.
To post to this group, send email to python...@googlegroups.com.
To unsubscribe from this group, send email to pythonirelan...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/pythonireland?hl=en.
--