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

TwistyPuzzles.com Forum

It is currently Tue Jul 22, 2014 11:17 pm

All times are UTC - 5 hours



Post new topic Reply to topic  [ 3 posts ] 
Author Message
 Post subject: Is this packing of polyominoes possible?
PostPosted: Fri Feb 28, 2014 6:56 pm 
Offline

Joined: Sun Nov 23, 2008 2:18 am
Realizing that the free tetrominoes and pentaminoes have a combined area of 80 squares, I was wondering if it is possible to arrange them to form a 9*9 square with a 1*1 hole at its center. If not, does relaxing the location of the hole make it possible?

Also, how many ways can you select 9 unique free nonominoes such the set chosen can form a 9*9 square?

_________________
Just so you know, I am blind.

I pledge allegiance to the whole of humanity, and to the world in which we live: one people under the heavens, indivisible, with Liberty and Equality for all.

My Shapeways Shop


Top
 Profile  
 
 Post subject: Re: Is this packing of polyominoes possible?
PostPosted: Fri Feb 28, 2014 10:06 pm 
Offline

Joined: Mon Aug 18, 2008 10:16 pm
Location: Somewhere Else
For your first question, yes it is extremely doable. Jaap's fantastic little solver program found its first solution in 0.6 seconds after putting in the shapes.

For your second question, I don't think the solver could handle it. The smaller, similar problem for solving a 6x6 square with hexominoes has more than 100,000 solutions according to the program and it was starting to get bogged down at that point so I stopped the search. It's likely there are more solutions than can be computed.


Top
 Profile  
 
 Post subject: Re: Is this packing of polyominoes possible?
PostPosted: Sat Mar 01, 2014 9:31 am 
Offline

Joined: Sun Nov 23, 2008 2:18 am
Considering how fast the number of n-minoes grows with increasing n, I should have expect the problem of dividing an n*n square into n n-minoes to have even faster growth in number of solutions.

If a computer can find a solution in under a second, the 9*9 square packing of tetrominoes and pentaminoes sounds like a good first build for such puzzles.

Looking at Wikipedia's article on the nonominoes, I see that the vast majority are asymmetric, and only six have higher symmetry. The D4 nonominoes are obviously the 3*3 square and the cross formed by two I pentominoes intersecting at their middle square, but I can't easily visualize the D2 nonominoes without a description, nor does the article mention if any of the nonominoes with holes are symmetric. If we require the solution to include both D4 nonominoes, any D2 nonominoes that lack a hole, and restrict the choice for the remainding pieces to the symmetric nonominoes, does the problem become tractable while still producing a solution? If all 4 of the D2 nonominoes lack holes, are their any solutions containing both D4, all 4 D2, and one each with a line of reflection aligned to the grid, a line of reflection at a 45 degree angle to the grid and point symmetry?

I would ask for a link to Jaap's solver, but I have a feeling I wouldn't be able to use it.

_________________
Just so you know, I am blind.

I pledge allegiance to the whole of humanity, and to the world in which we live: one people under the heavens, indivisible, with Liberty and Equality for all.

My Shapeways Shop


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

All times are UTC - 5 hours


Who is online

Users browsing this forum: No registered users and 4 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