Jump to content
  • Advertisement

Archived

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

OrangyTang

Solving Soma cube (Updated with images/pieces)

This topic is 5614 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
Advertisement
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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!