Consider some variations on Tetravex as a computer game (GNOME Tetravex).
Pieces can be rotated (physical versions of the puzzle can do this). Some sort of knob UI with haptic feedback would be nice. Pieces can be flipped, resulting in mirror image. Up-down and left-right spring-loaded levers would be nice, allowing the user to choose which way to flip, though regular arrow keys are probably just as good. Or, not mirror image: the other side is a completely different piece, creating an additional challenge of choosing which side of the piece to use.
Cube-shaped pieces could extend the theme even further. We might want a physical input device for rotating a selected cube on a display. Although the faces could be completely independent, it would be elegant if wedges across an edge share the same color. There's probably considerable challenge in making the puzzle globally difficult (e.g., having a unique solution).
Toroidal universe.
Various other shapes that tile edge-to-edge: rectangles (only 180 degree rotations, unlike squares), equilateral triangles, regular hexagons.
Higher dimensions: cubes, boxes, 24-cell. The obvious analogue in, say, 3D is to make it a face matching puzzle, but we could also consider keeping it an edge matching puzzle. For example, for cubes, their edges are colored and the 4 cubes that meet at an edge must share the same edge color. Similarly, in 2D (or more), we could consider a vertex matching puzzle.
More than one tile type: useful are uniform tilings and uniform honeycombs in various dimensions, though I think there are nice tilings that are not uniform, for example, rectangles (though that's only one tile type).
Pieces having distinct and distinctive names might be useful for remembering what pieces you have and what they look like. Maybe an image in the center: Faces of people you know.
EmoticonEmoticon