Archived

This topic is now archived and is closed to further replies.

Solving Soma cube (Updated with images/pieces)

This topic is 5308 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm trying to write a little problem to solve a Soma cube varient. Each piece is represented by a 6x6x6 array of booleans, and will be a brute-force method of trying every combination all the pieces together which fit into the cubes bounds. Edit: Knocked up a picture of all the pieces: So, my initial idea for producing a solution would be to create a 'board' and a corresponding set of 'pieces'. I've already got code for rotating pieces, checking if adding a piece at a position is valid, and inserting a piece, but need to figure out how to pull it all together. My idea is to: - Take first non-inserted piece, check against position/rotation in board. - If can be inserted:    - Clone current board+pieces, insert newly cloned current piece into new board    - recurse. - Move to next position/piece. Is this going to produce a solution? I know a depth-first is probably not the most efficient or fastest, but assuming that a solution exists, this should find it (or all of them?) eventually? Any good websites that deal with this kind of problem? Edit: Cleaned up image [edited by - OrangyTang on June 6, 2003 6:05:23 PM]

Share this post


Link to post
Share on other sites
Provided your methods can find every possible valid position for each piece considered at each step a depth/breadth first search will find all the solutions.

Nice problem you''ve given yourself there. Let us know how you get on.




ai-junkie.com

Share this post


Link to post
Share on other sites
Great. Time for me to figure out a clean way to find every possible rotation position.

Its one hell of a tough puzzle - the actual thing is a wooden block construction, which has never been completed in approx. ~2 years of ownership. Maybe if i could get images of the pieces then i''d post it for people to attempt to solve it themselves..

Share this post


Link to post
Share on other sites
quote:
Original post by OrangyTang Maybe if i could get images of the pieces then i''d post it for people to attempt to solve it themselves..
Heh. The link you posted shows all 7 pieces at the top of the page (or I would assume that they are the 7 pieces - I don''t know why the image wouldn''t be accurate).

Good luck with the program. It''ll be interesting to hear how you made out.



Jason Doucette - online resume page: www.jasondoucette.com
projects / games, real-time graphics, artificial intelligence, world records, wallpapers / desktops / backgrounds
"Great minds discuss ideas, average minds discuss events, small minds discuss people." - Anna Eleanor Roosevelt, 1884-1962

Share this post


Link to post
Share on other sites
Having been heavily involved in the online community that studied the Eternity Puzzle I can tell you that bit-boards are very efficient for representing your problem, particularly for checking piece overlap during placement.

As to your rotation issue, just choose a primary orientation for each piece. Set into it 3 Cartesian axes. Then, for each rotation about the z-axis, consider rotations about the x and y axes. Check for duplication of state given the rotation sequence. The easiest way to do this is to encode your pieces, enumerate all possible rotation sequences, remove duplicates and then label all unique rotations (encoding the rotation sequence as the label is also a good idea).

This is a great problem to test your search skills on and to try different search algorithms, which are invaluable for game AI. Let us know how you go.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
quote:
Original post by Jason Doucette
Heh. The link you posted shows all 7 pieces at the top of the page (or I would assume that they are the 7 pieces - I don''t know why the image wouldn''t be accurate).


A normal Soma cube is pretty easy (by hand i mean), or at least getting it to fit into a cube is easy - some of the bizzar constructs are tricky as hell.

However i''m trying to solve a puzzle in the same style, but totally different pieces. Although it still works off of a 3x3xx3 grid, some pieces have half cubes as part of their shape - hence my using a 6x6x6 grid. Also, each cube is either white or black, and the final solution is supposed to be checkered on every side.

Last night, i got a basic search as i mentioned above ''working''. It managed to find a solution if i handed it just two pieces, and just 5 pieces (taking just under about half a minute). Drunk on my own sucess, i handed it the complete set of nine pieces - but with 20 minutes of no activity and jamming up the computer by using all CPU I had to kill it. So i need to change my code to actually show some sort of visual progress..

Share this post


Link to post
Share on other sites
quote:
Original post by fup
What''s the Eternity puzzle?




It was a 209 piece jigsaw puzzle where every piece was unique and made up of 12 drafters triangles to form a polygon. The creator of the puzzle offered 1 million pounds sterling for the first person to solve the puzzle within 3 years. It went off 1 year after launch, much to the chagrin of the creator. The solution found was obtained using an EM algorithm to learn an approximation to the conditional probability distribution of being able to solve the puzzle with the remaining pieces, given the remaining space to be filled.

I was heavily involved in an online community that worked on the puzzle. There was another solution found, but that person was pipped by one week by the eventual winners.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
quote:
Original post by OrangyTang
However i''m trying to solve a puzzle in the same style, but totally different pieces. Although it still works off of a 3x3xx3 grid, some pieces have half cubes as part of their shape - hence my using a 6x6x6 grid. Also, each cube is either white or black, and the final solution is supposed to be checkered on every side.
Aha. I thought it was strange that you would have missed the pictures on the link you gave. This problem sounds much more complicated... I''m still interested in your progress. Keep us updated!



Jason Doucette - online resume page: www.jasondoucette.com
projects / games, real-time graphics, artificial intelligence, world records, wallpapers / desktops / backgrounds
"Great minds discuss ideas, average minds discuss events, small minds discuss people." - Anna Eleanor Roosevelt, 1884-1962

Share this post


Link to post
Share on other sites
Updated the original post with a quick image of all the pieces. Its a bit shaky but i exagerated the proportions to try and make it obvious which are half pieces and which are whole cubes.

A cookie to anyone who can solve it

Share this post


Link to post
Share on other sites
quote:
Original post by OrangyTang
Also, each cube is either white or black, and the final solution is supposed to be checkered on every side.
I would think this would make the search easier, since there are only so many places each piece can go. Also, when you have a half black cube, only another half black cube can fit in the empty space to fill the rest of the cube - this limits the number of pieces that can be chosen to be put there. Perhaps using a 3x3x3 array would be easier (at least in the theory of the solution). What do you think?



Jason Doucette - online resume page: www.jasondoucette.com
projects / games, real-time graphics, artificial intelligence, world records, wallpapers / desktops / backgrounds
"Great minds discuss ideas, average minds discuss events, small minds discuss people." - Anna Eleanor Roosevelt, 1884-1962

Share this post


Link to post
Share on other sites
More progress I entered the Soma pieces as an easier test of the algorithm, and if i hardcode the first piece to a position i know has a solution (just to trim the tree a little) it finds a solution within about a minute. I''ve reworked it so it actually plays nice with other apps as well. The Soma cube is much simpler and has less pieces though..

Left it solving the full bastard-cube set when i went to work, got back after it had been running all day and no solution found I think i''m going to add colour checking, as it was trying pieces that were obviously wrong to me, yet the program is blind to it. Adding colour checking should also have a side effect of aligning the pieces to the 3x3x3 grid properly

Colour checking is hopefully none too difficult, i also have one more piece of information to go on - the pieces have one more black cube than white cubes, therefore the corners of the solution have to be black. I''m still going to stick with the 3x3x3 grid, it makes dealing with the half pieces easier, as i don''t have to write a bunch of special case code everywhere.

Oh, i''m also tempted to add Timkin''s suggestions to remove duplicate rotation/translation combinations, but since the algorithm probably works in its current state i''m tempted to leave it alone. Then again, i''d also like the results to be calculated in my lifetime

Share this post


Link to post
Share on other sites