The goal of this project is to take an image of an unsolved puzzle that lies on a plain sheet of paper and to output the next step to the final solution. We will assume that the puzzle has its edges parallel to the image boundaries. The output will be in the form of an image with an x on the puzzle piece that should be moved into the empty space of the puzzle. The project consists of four different steps. The first three steps involve image processing of the puzzle-image. The final output of these three steps will be the numerical representation of the unsolved puzzle. In the fourth step we take this numerical representation and output the image of the original puzzle with an arrow pointing to the direction of the next step.

Input: Image of Puzzle on table:

Output: Image of Puzzle indicating next move:

Algorithm:

1. Find Puzzle in image (Victor) Assumes translation only (no rotation) Detects edges of puzzle against white table In the first step we are going to localize the puzzle in the image and output an image that represents the puzzle board. This will be done in the program called getPuzzle.c. We can approach this task in two different ways. One way is to try to determine the puzzle's position is using scale lines that go over the entire initial image. Assuming that the background is completely white (the puzzle is on a blank sheet of paper) we will try to find the first black pixel of the puzzle's border (presumably the border is black). If we use scan lines starting from the left, the first black pixel will coincide to the upper left corner of the puzzle. However, as the corners are curved, more than one pixel is needed to find the exact position of the upper left corner. An average of the x and y coordinates of these pixels will give a relative correct position of the puzzle's upper left corner. The same strategy applies to the other corners. We only need to find two corners to find the other four (the puzzle is a square!). However, this algorithm will fail when the puzzle's edges are not perfectly parallel to the image boundaries. The second (better) approach would be to assume that the puzzle board is somewhere in the center of the image. (This seems to be a reasonably enough assumption. If we are going to use this game in the Larry King's Show, the producers will focus their cameras on the puzzle board. Therefore, there should be no worries that the CX Department will not look good on CNN J) We will than use scan lines that start from somewhere in the middle of the image (in terms of x and y coordinates). The average on the black pixels' coordinates will give us the right x and y -coordinates of the corners without any possibility of failure.

2. Cut Tiles out of Image (Victor, Dan) Uses real-life ratios of puzzle. After localizing the puzzle in the image, we will begin the second step using puzzle.pgm (output image from the previous program) to output each tile separately. The only problem here is to distinguish between puzzle's border and the tiles' area. Given an image we know that any affine transformation of the image will keep the ratios between features dimensions constant. The ratio between the thickness of the border and the dimensions of the puzzle is .083. The output image of the getPuzzle.c program is square sized and has the dimensions of the entire puzzle. Using easy computations we can separate the border from the tiles area. Knowing the position of the tiles area, we will divide it in sixteen parts of equal size. Since each tile is also a square, we can output each tile separately. Some small "measure" errors may however occur because of rounding. , , , , . . .

3. Compute best fit of Tiles to Models using SSD (Laura) We use greedy matching algorithm: Compute SSD of all tile images with all tile models Choose overall best match as first match Choose next best match from remaining 15 models Choose next best match from remaining 14 models etc. The third step takes in the 32 images output from the second step. They are the correctly ordered 16 model tiles and the 16 unordered tiles representing the unsolved puzzle. The program ssd.c runs as follows. First, the main program loads all the tiles into an array called tile. Then it loads the model images into the models array. It calls computeLocation.c and passes these two arrays (model and tile) in. ComputeLocation.c then performs ssd on each tile by comparing it with all the model tiles that have not already been matched with a tile. The best match is computed between tile and model using ssd. The number of the tile will then be placed in the location array indicating where that tile is in the unsolved puzzle right now. For example, if the tile number 8 is at the spot at the top left hand spot in the puzzle, the location array contains a number 8 at location index 1. If the "10" is at the spot directly to the right, the location array will indicate a 10 at index 2 and so on. ssd.c outputs the numerical representation of the locations of the unsolved puzzle. = , = , = , = , . . .

4. Generate next move based on configuration (Dan) Hard-coded the solution for each tile About 1200 lines of code The fourth step consists mainly of implementing a solution to the 15-puzzle. The input is the configuration of the puzzle, and the output is the next move towards the solution. The strategy used is straightforward: Place the "1" piece. Place the "2" piece. Put the "3" piece in the 4th position. Solve the "4" and "3" piece simultaneously. Place the "5" piece and "6" piece. Put the "7" piece in the 8th position. Solve the "8" and "7" pieces simultaneously. Solve the rest in this order: 9, 13, 10, 14, 12, 13, 15. In order to speed up the programming process, we have decided to hard-code every step of the solution. This is about 1500 lines of code, but it is reliable, accounts for all special cases, and is very easy to implement.

Example: moving tile 1 into place:

Solving the 3 and 4 tiles:

Solving the last two rows, pair by pair:

Things that might be taken into account for future improvements are as follows:
1. Our program requires the lighting intensities to be almost identical in the model image and the unsolved puzzle image. An intensity mapping program might be added to remove this restriction.
2. A window based ssd program might further reduce errors in tile and model matching. This would account for slight misalignments of the tiles in the data image compared with the tiles in the model image.