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

 Page 1 of 1 [ 3 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Is this packing of polyominoes possible?Posted: Fri Feb 28, 2014 6:56 pm

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

 Post subject: Re: Is this packing of polyominoes possible?Posted: Fri Feb 28, 2014 10:06 pm

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

 Post subject: Re: Is this packing of polyominoes possible?Posted: Sat Mar 01, 2014 9:31 am

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

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 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 forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ Announcements General Puzzle Topics New Puzzles Puzzle Building and Modding Puzzle Collecting Solving Puzzles Marketplace Non-Twisty Puzzles Site Comments, Suggestions & Questions Content Moderators Off Topic