Hinomaru: The Japanese Flag Puzzle
In 2001, the 21st annual International Puzzle Party was held in Tokyo, and I decided to honor the hosts with a puzzle based on the simple, elegant design of the Japanese flag, also known as Hinomaru (literally, "the circle of the sun"). To start, I drew the flag's design on a 6-by-4 rectangle and then broke it up into twelve 1-by-2 dominoes. Then, to make things tricky, I also colored the backs of all of the dominoes in ways that make them look like potential fronts. Thus, all of the dominoes are double-sided, and it's not at all obvious which side is the front! Add to this the high degree of symmetry in the flag design, which makes the piece placements even more ambiguous, and you have a very difficult puzzle.
(At the 2007 IPP in Australia, six years later, someone came up to me during the Exchange and said, "I spent a long, long time solving that flag puzzle of yours." He then handed me his Exchange puzzle. "This," he said, "is my revenge!" Needless to say, I haven't solved his puzzle yet...)
The Hinomaru puzzle has a unique solution (up to swapping pieces with the same face-up design), and that solution leaves only the front face looking like the flag; the backs of the pieces look entirely random when solved (no helpful hints there!).
I also have an all-paper version of the puzzle, consisting just of the 12 double-sided cards that are sandwiched inside clear acrylic in the version above. This version doesn't come with a tray, just the cards wrapped up in a simple origami envelope.