Deliverable #1: Puzzle Generator

Jigsaw Puzzle Generator Source Code - zip

The first component needed to begin solving the jigsaw puzzle problem is the ability to parse a image and generate a board. The tool I developed is written in Python version 2.7.11. It uses the following libraries:

Pillow: An image processing library
TKinter (Optional): Used to open a file browser
Pickle (Optional): Python's object serialization library

If you are running Python in Windows (tested in Windows 7 and 10 only), you can use the package installer script I wrote; it is located here. If you want to manually install the libraries or on a non-Windows machine, you should use your platform's equivalent of pip install. Below is an example image of my cat Muffins:

By running the "puzzle.py" with default settings, the output will be as shown below:

A few things to notice:

Grid: The puzzle has been broken up into a set of 50px by 50px pieces. The piece width was automatically calculated based off the height and width of the image and the specified grid size.
Border: Between each puzzle piece is a border. This can be disabled by changing line #21 of the file "puzzle.py" from "export_with_border = True" to "export_with_border = False".

Using the existing code, you must manually specify the desired number of pieces in the x and y direction. There may be future improvement to remove this requirement, but at present, it remains. Given the specified grid size, the code calculates the appropriate piece width that gives the maximum image area. For example, below is the image with the grid size set to 2 pieces by 2 pieces. Note how the new board width changed from 500px by 300px to 300px by 300px with each piece now being 150px by 150px.

Two additional supported features are below. They can be added individually or in tandem.

Shuffling:

Before solving a jigsaw puzzle, the first step is to randomly shuffle the pieces. This is done using the standard Fisher-Yates shuffling algorithm. To enable rotation, line #285 in file "puzzle.py" ("# test_puzzle.shuffle_pieces()") should be uncommented. Below is the image with pieces shuffled only; notice for example, that the peppers are moved throughout the board.

Piece Rotation:

In much of the previous work done on the jigsaw puzzle problem, rotation of tiles was disallowed. In my application, I plan to make selectable whether rotation is enabled or disabled. To enable rotation, line #48 in file "puzzle_piece.py" ("rotation_enabled = False") should be changed to: rotation_enabled = True. Below is an image with rotation enabled (and shuffling disabled). Notice how the keys and utility knife remain in the bottom left corner but are rotated away from each other.