Enumerating polyominoes with depth first search

Polyominoes are shapes made of joined squares.

Free polyominoes are shapes where reflections and rotations are counted as the same shape. (imagine turning over or rotating bits of cardboard)

consider the case of the free tetrominoes (made of 4 squares)

how do we enumerate them systematically ?

start with the straight line one

 
take the rightmost square and rotate it round clockwise repeatedly

this gives one of them

rotate the same square again to give another

there are no more to generate by moving this square since all the possible ones are rotations or reflections of the ones we’ve already got,

so start again with the last one and rotate the rightmost square again

this gives one more new configuration

finally start again with the last one formed and rotate the rightmost square again (this time twice) to get the last one

so we’ve now got all 5 of them

Have you noticed that this process is recursive ? 

in fact we are walking the graph of the tetromino, where two nodes are adjacent if they can be converted one to the other by moving one square.

this is done by a depth first algorithm

think about how the graph is walked

our algorithm would be

1. start at the first node
2. take the first right turn that has not already been visited
3. repeat until you reach a terminal node
4. backtrack until you find a node with an untraversed edge
5. treat this node as root and repeat from step 1 until no more untraversed edges left

 

can you use this process to try and write some code to find how many n-ominoes there are for any n ?