Home

Overview

The N-Puzzle represents a square puzzle consisting of squares which start out in a random order and can be moved around to be arranged into a solution.

The classic example is the 15-puzzle which consists of a board of 4x4 squares identified by numbers, with one square missing (empty). Users must arrange the squares in order by sliding squares. The puzzle goes back over 135 years and has been a fundamental example for modeling algorithms and analysis over the last century.

https://en.wikipedia.org/wiki/15_puzzle

Challenge

In this specific challenge, the squares represent parts of an image and must be arranged to complete an image. For an added twist, the squares can also be rotated.

• Squares have an identifier and set of edges.
• Edges are defined in orientation order [N,E,S,W].
• A square matches the squares adjacent to it when the edges of both squares match.
• When there is no adjacent square (outside border), the edge is considered a match (wildcard).
• A puzzle is solved when all squares match all adjacent squares (no conflicts).
• For solutions, Square A will always be position [ 0, 0 ] with Edge 1 in the N orientation

e.g. Square A with edges [1,2,3,4]

---------------
|      1      | 
|             | 
|  4   A   2  | 
|             | 
|      3      | 
---------------

Different puzzles will require varying actions to complete. As puzzles become unlocked, you will need to use the actions allowed for that puzzle to determine a solution. There can be multiple solutions and using different actions may result in a shorter solution.

The goal of each puzzle is to come up with a list of actions which will transition the puzzle from the START state to the FINAL state.

You may find that you can easily solve some puzzles by hand at first, but as you progress through the tiers, you will find the benefit of an application performing the analysis.

Example

Let's walk through an example of a 4-Puzzle with the allowed actions of MOVE, SWAP, and ROTATE.

Given a starting state of

-----------------------------
|      4      |      3      |
|             |             |
|  3   A   1  |  10  C   8  |
|             |             |
|      2      |      9      |
-----------------------------
|      5      |      7      |
|             |             |
|  2   B   6  |  8   D   11 |
|             |             |
|      7      |      12     |
-----------------------------

We are looking for how to transition to a solution state of

-----------------------------
|      1      |      5      |
|             |             |
|  4   A   2  |  2   B   6  |
|             |             |
|      3      |      7      |
-----------------------------
|      3      |      7      |
|             |             |
|  10  C   8  |  8   D   11 |
|             |             |
|      9      |      12     |
-----------------------------

We can achieve the transition with an action list of:

• ROTATE(A,3)
• MOVE(C, DOWN)
• MOVE(C, LEFT)
• MOVE(B, UP)

or

• ROTATE(A,3)
• SWAP(C, B)

Refer to the API for specific actions and their parameters.