I do jigsaw puzzles in streaks. I’ll go for years without doing one. After all, there is something fundamentally wasteful about spending countless hours on putting something together that is destined to be disassembled and put back into the box. Then again, I’ll find myself on vacation welcomed by several days of soaking rain, and I’ll start one. If you’re like me, it’s impossible to start a puzzle without finishing it. Doing so would be admitting defeat, and one cannot allow oneself to be defeated by something that lives in a box in the closet. I also refuse, unlike some members of my immediate family, to cheat by using the picture on the box cover to help solve the puzzle. At least I don’t do that while anyone is looking. Occasionally, some sadist will give me a puzzle as a gift, usually one that has some impossible picture, or one that has impossible shapes, or one that is a single color, etc. This month, thanks to the suggestion of Peter Lewis, it’s my turn to torture you with a jigsaw puzzle Challenge. And I’m not giving you a box cover to work with, just in case you’re inclined to cheat.

Your puzzle has no color information to help you in assembling it — you’ll have to rely entirely on the shapes of the pieces to determine where each piece belongs. When assembled, the puzzle has a rectangular shape. The puzzle is presented to you as a bitmap of 16-bit pixels. Each piece consists of contiguous pixels with a unique nonzero pixel value. The pieces are rotated by a multiple of one-quarter turn, and are scattered throughout a rectangle, with no overlap between pieces. Pixels not containing part of a puzzle piece have the value 0. To eliminate any ambiguity in the orientation of the reassembled puzzle, the top left corner piece will be located in its final position at location (0,0) of the puzzle rectangle. Your job is to reassemble a series of these puzzles as efficiently as you can.

The file challenge.in contains a single line with the number of test cases your program needs to process. The input for each test case is provided in file jigsawNN.in, where NN ranges from 1 to the number of test cases. Each input file contains (2+puzzleHeight*puzzleWidth) 16-bit values, corresponding to this JigsawPuzzle structure:

Your code needs to read each input file, reassemble the puzzle by rotating and translating individual pieces, and output a JigsawPuzzle structure containing the solved puzzle to the file jigsawNN.out. With no space between the reassembled puzzle pieces, the reassembled puzzle will have a smaller width and height than the input bitmap.

Your program should produce a challenge.log file, with one line per test case containing the integer number of microseconds used by your application to solve that test case, including the time to read the input, find the solution, and produce the output file. The method used to measure execution time may vary based on the development environment you use for your solution, but you should measure time with microsecond precision if possible.

You can improve your chances of winning by incorporating optional features into your solution. For this jigsaw puzzle problem, you might want to optionally display your solution’s progress in solving the puzzle. The timing of your solution should exclude any optional display features.

Scoring will be based on minimizing execution time, on a subjective evaluation of additional features, and on the clarity of your code, including the commentary that describes your solution, use of consistent naming conventions, and the readability of your code. Your base score will be 1 penalty point for each microsecond of execution time. Penalty points will be decreased by up to 25% based on any optional features you might incorporate into your solution, and by another 25% based on a subjective evaluation of the clarity of your code.

This will be a native PowerPC Challenge, using the development environment of your choice, provided I have or can obtain a copy - email progchallenge@mactech.com to check before you start. You can develop for Mac OS 9 or Mac OS X. Your solution should be a complete Macintosh application, and your submission should provide everything needed to build your application, as well as documentation of the features you have implemented, to ensure that I don’t overlook anything.

Here are some Questions and Answers about this Challenge.

Test data for this Challenge is available.

You can get a head start on the Challenge by reading the Programmer's Challenge mailing list. It will be posted to the list on or before the 12th of the preceding month. To join, send an email to listserv@listmail.xplain.com with the subject "subscribe challenge-A". You can also join the discussion list by sending a message with the subject "subscribe challenge-D".