This one is tougher.
Start with a square. Suppose the top and bottom of the square can be either straight or have an interlocking pattern, as shown in the two examples below:
And suppose the left and right of the square can be either straight, concave or convex, as shown in the examples below:
That gives $2 \times 3 \times 2 \times 3 = 36$ possible squares.
Is it possible to create a $6 \times 6$ jigsaw puzzle (outside borders straight) with these $36$ pieces? Rotation or flipping of pieces is not allowed.