Solving the cube puzzle (programatically)

94 views
Skip to first unread message

Daniel Kersten

unread,
Jul 18, 2010, 3:59:13 PM7/18/10
to python...@googlegroups.com
Hey all,

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

unread,
Jul 18, 2010, 4:10:28 PM7/18/10
to python...@googlegroups.com
Fin (the Google guy) told me there were 19,000 combinations to thoser cubes.......hmmmmm!



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

unread,
Jul 18, 2010, 6:09:27 PM7/18/10
to python...@googlegroups.com
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.
--
Daniel Kersten.
Leveraging dynamic paradigms since the synergies of 1985.

Maciej Bliziński

unread,
Jul 21, 2010, 2:58:08 AM7/21/10
to python...@googlegroups.com
2010/7/18 Daniel Kersten <dker...@gmail.com>:

> 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.
My favorite source of unreliable information, Wikipedia, says about
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

unread,
Jul 21, 2010, 6:35:35 AM7/21/10
to python...@googlegroups.com
2010/7/21 Maciej Bliziński <maciej.b...@gmail.com>:

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

unread,
Jul 21, 2010, 6:49:23 AM7/21/10
to python...@googlegroups.com
BTW
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

unread,
Jul 21, 2010, 6:48:47 AM7/21/10
to python...@googlegroups.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

Daniel Kersten

unread,
Jul 21, 2010, 9:37:59 AM7/21/10
to python...@googlegroups.com
hehe, thats ok, we can refactor and cleanup code when it works.

Maciej Bliziński

unread,
Jul 21, 2010, 2:23:58 PM7/21/10
to python...@googlegroups.com
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)

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

unread,
Jul 24, 2010, 7:45:39 AM7/24/10
to python...@googlegroups.com
2010/7/22 Daniel Kersten <dker...@gmail.com>:
> 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

unread,
Jul 25, 2010, 9:58:37 AM7/25/10
to python...@googlegroups.com
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?

On 25 July 2010 14:53, Daniel Kersten <dker...@gmail.com> wrote:
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

unread,
Jul 25, 2010, 10:00:28 AM7/25/10
to python...@googlegroups.com
2010/7/25 Daniel Kersten <dker...@gmail.com>:

> 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

unread,
Jul 25, 2010, 10:14:41 AM7/25/10
to python...@googlegroups.com
2010/7/25 Daniel Kersten <dker...@gmail.com>:

> 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

unread,
Jul 25, 2010, 12:04:08 PM7/25/10
to python...@googlegroups.com
2010/7/25 Kevin Noonan <kno...@gmail.com>:
> 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

unread,
Jul 25, 2010, 4:18:35 PM7/25/10
to python...@googlegroups.com
Have you seen the solver applet in Java?

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

unread,
Jul 25, 2010, 11:20:36 AM7/25/10
to python...@googlegroups.com
Hi guys,

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

unread,
Jul 25, 2010, 9:53:59 AM7/25/10
to python...@googlegroups.com
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.




--
Reply all
Reply to author
Forward
0 new messages