Are 'zero-one' jigsaw puzzles NP-complete?
Since you mentioned you are interested in solving this problem for small values of $n$, I would suggest that you try implementing this in a SAT solver or as an integer linear program (ILP).  Either one will be able to encode the constraints, but in a slightly different way:


For SAT, there is a very clean encoding of the choice of which tile goes into each square, and a slightly less clean encoding of the constraint regarding the number of each kind of tile (using bit arithmetic).
For ILP, there is a very clean encoding of the constraint regarding the number of each kind of tile available, and a slightly less clean encoding of the constraints on which tiles can be adjacent to each other (but it is still expressible, since you can express arbitrary boolean formulas in ILP).


I would expect that for small or medium sized $n$, this approach might work efficiently.