What data structure should I use to represent this board?

Question

 --- --- --- ---
| o | o | o | o |
 --- --- --- ---
| o | o | o | o |
 --- --- --- ---
| o | o | o | o |
 --- --- --- ---
| o | o | o | o |
 --- --- --- ---

Pieces go between the circles. The goal is to fill the entire board. I need a way to represent the board's contents. The pieces can be rotated and flipped. I tried using a matrix but that didn't work out very well.

Edit: Example pieces:

Answer 1

I think a matrix would work OK, but you need to be careful how you fit the pieces together. Here's an illustration of how the pieces shown above might fit into a 3×3 puzzle:

I've coloured the circles alternately yellow and blue in a checker-board fashion, but you should actually consider each circle as a set of four quadrants so you'll need a 6×6 matrix in this case. The puzzle pieces can then be represented as 8-connected collections of cells that follow the colouring of the cells where they are placed, but have the ability to flip between blue and yellow (e.g., the "diamond" piece is coloured Y B / B Y as shown, but would flip to B Y / Y B if you moved it to the next gap below):

         Y Y B B Y Y
         Y Y B B Y Y    Diamond:  Moustache:   Snake:
         B B Y Y B B
         B B Y Y B B      Y B          Y         Y Y
         Y Y B B Y Y      B Y          B       B
         Y Y B B Y Y                 Y

So this is what your matrix would look like with these pieces added to it. You can see that the "moustache" and "snake" pieces have the same shape, but are coloured differently:

It should then be quite straightforward to solve the puzzle by using a constraint satisfaction algorithm.