Polyomino generator

Question

Write a program that prints the shapes of one-sided polyominoes.

Given input 4 (tetrominos), a sample output would be:

 *   *         *     *
 *   *    **   **   **  *
**   **   **    *   *  ***  ****

You are not restricted with respect to orientation, ordering or layout as long as polyominoes are not connected and not duplicated. (E.g. you can print the shapes in a column rather than a row)

Provide code that inputs a number from 3 to 6 and outputs the one-sided polyominoes of that size. The expected number of polyominoes output are 2, 7, 18, and 60 for 3, 4, 5, and 6 as inputs respectively.

Shortest code wins, present your solution for number 4.

Answer 1

Python, 398 392 chars

n=input()
r=range
T=lambda P:set(p-min(p.real for p in P)-min(p.imag for p in P)*1j for p in P)
A=[]
for i in r(1<<18):
 P=[k%3+k/3*1j for k in r(18)if i>>k&1]
 C=set(P[:1])
 for x in P:[any(p+1j**k in C for k in r(4))and C.add(p)for p in P]
 P=T(P)
 if not(C^P or P in A or len(P)-n):
  for y in r(4):print''.join(' *'[y+x*1j in P] for x in r(6))
  A+=[T([p*1j**k for p in P])for k in r(4)]

Polyominos are represented as sets of complex numbers representing the cells of the polyomino. For example, T takes a polyomino and translates it so the minimum real and imaginary coordinates are 0.

The outer loop iterates through all 2^18 3x6 grids, generating a potential polyomino P, making sure P is connected (by computing C, the part of the polyomino connected to P[0]), checking that P isn't in the list A of previously found polyominos, and verifying that P has exactly n cells. Any new polyomino is added to A in all 4 rotations.

It takes two minutes or so to run to completion. Here's the result for n=4:

**    
*     
*     

*     
**    
*     

**    
**    


 *    
**    
*     

*     
*     
**    

*     
**    
 *    

****  

Answer 2

Ruby, 266 241 320 (227 without reflections)

Given the input restrictions, it's easier to just use a bitmap of all the polyominos.

puts [%w[13 3],%w[1vqxip 1s9b3b],%w[1j85qxc81ax0oxld 1db08aq5w1vdul13 172qaw25hgn8jn5t],%w[5l91ancci09g0iuurrdbkbrsl58jjiodia8irxlivoufjjse42o4l8hlcz 3qbvfj70ksz14cngk9exust0w1qjshykauo6yvyyn3j6oefyy1xc58hsoj 26c0102a8vw34q88pktwlkepxzcslicg6ydtrz4zhyyutd4bukh73187qb]][gets.hex-3].map{|n|n.to_i(36).to_s(2).tr'10','* '}

Old version (outputs just the free polyominoes):

puts [%w[13 3],%w[9iz3 a5z],%w[cfu9zai70z b3tsb0pge1 12t8eks810j],%w[5wgmz704fjqc593xfwrmkwb7k0j9ztr31v fr8weq5t88qdxp93hit2fh8899qcbr2a9f 10r578ajcw2n15dwywsm0ep601kiv41cco3]][gets.hex-3].map{|n|n.to_i(36).to_s(2).tr'10','* '}

Output for n=4:

** **  *    *  ****  **   *
**  ** *** ***      **  ***

Answer 3

Golfscript, 221 chars

Also 221 bytes. Inspired by Lowjacker's approach, but moderately different in actual implementation (and produces one-sided rather than two-sided polyominos).

Because some of the characters used, while valid Unicode codepoints (and one byte each in UTF-8), are non-printable, I present the base-64 encoding of the script:

fidAQEAVRRVALVs9TUZFUwhgA0BrdjVXGm4VOl8aDgMZfBdoVQQzNk0YLQ9eXCciBhwQH0ADDW9E
KlomSXgoLBxxI1oEeB9XPm51GF43bHBKQzl3WQ5vXTJCTABfEz4bJBlaWX0XL2QVDF5ZXFw5BxpF
IzNUKmUtYwEEfQEKckMSbjAlQmhYHShQaAtjK1QFbnt5WQokFkNkHgNlL35cXCU6Hj8nIkAiLz0x
MjdiYXNlIDRiYXNlWzNdL3tbKVxbMl0vLi0xJUAqXXt7eyIgKiI9fSVuK30vbn0vfS8=

And the script itself with the magic strings substituted:

~"@@@Magic@strings@go@here""@"/=127base 4base[3]/{[)\[2]/.-1%@*]{{{" *"=}%n+}/n}/}/

Example execution:

$ golfscript.rb poly.gs <<<"4"
****


***
*

*
***

**
**


***
 *


**
 **

 **
**