## Implement a jigsaw puzzle

Implement a jigsaw puzzle. Design the data structures and explain an algorithm to solve the puzzle.

My initial thoughts:
Each piece contains pointer to its four edges. We iterate through pairs of pieces to check whether they match along any edge.

My initial codes:

```	public class MyPiece {
int ID;
MyPiece up;
MyPiece down;
MyPiece left;
MyPiece right;

int[][] pixels;

public MyPiece(int iD, MyPiece up, MyPiece down, MyPiece left,
MyPiece right, int[][] pixels) {
super();
ID = iD;
this.up = up;
this.down = down;
this.left = left;
this.right = right;
this.pixels = pixels;
}

public void display() {
// TODO display this piece
}

@Override
public Object clone() {
return new MyPiece(ID, up, down, left, right, pixels);
}
}

public class MyPicture {
Set<MyPiece> pieces;

}

public class MyJigsawPuzzle {
MyPicture picture;
int ROW;
int COL;
MyPiece[][] puzzle;

public void initialize() {
// TODO initialize the picture
}

public void startGame() {
for (MyPiece piece : picture.pieces) {
}
Collections.shuffle(pieceList);
puzzle = new MyPiece[ROW][COL];
for (int i = 0; i < ROW; ++i) {
for (int j = 0; j < COL; ++j) {
puzzle[i][j] = pieceList.get(pieceList.size() - 1);
pieceList.remove(puzzle[i][j]);
}

}

for (int i = 0; i < ROW; ++i) {
for (int j = 0; j < COL; ++j) {
puzzle[i][j].display();
}
}
}

public boolean isComplete() {
for (int i = 0; i < ROW; ++i) {
for (int j = 0; j < COL; ++j) {
MyPiece piece = puzzle[i][j];
MyPiece up = i >= 1 ? puzzle[i - 1][j] : null;
MyPiece down = i < ROW - 1 ? puzzle[i + 1][j] : null;
MyPiece left = j >= 1 ? puzzle[i][j - 1] : null;
MyPiece right = j < COL - 1 ? puzzle[i][j + 1] : null;
if (piece.up != up || piece.down != down
|| piece.left != left || piece.right != right)
return false;
}
}
return true;
}

public void solve() {
for (int i = 0; i < ROW; ++i) {
for (int j = 0; j < COL; ++j) {
MyPiece A = puzzle[i][j];
for (int m = 0; m < ROW; ++m) {
for (int n = 0; j < COL; ++n) {
MyPiece B = puzzle[m][n];
if (A.up == B)
swap(i - 1, j, m, n);
else if (A.down == B)
swap(i + 1, j, m, n);
else if (A.left == B)
swap(i, j - 1, m, n);
else if (A.right == B)
swap(i, j + 1, m, n);
}
}
}
}
}

public void swap(int i, int j, int m, int n) {
MyPiece temp = puzzle[i][j];
puzzle[i][j] = puzzle[m][n];
puzzle[m][n] = temp;
}
}

Solution:
class Edge {
enum Type {
inner, outer, flat
}

Piece parent;
Type type;

boolean fitsWith(Edge type) {
}; // Inners & outer fit together.
}

class Piece {
Edge left, right, top, bottom;

// 90, 180, etc
Orientation solvedOrientation = 90;
}

class Puzzle {
// Remaining pieces left to put away.
Piece[][] pieces;
Piece[][] solution;
Edge[] inners, outers, flats;

// We're going to solve this by working our way
// in-wards, starting with the corners.
// This is a list of the inside edges.
Edge[] exposed_edges;

void sort() {

// Iterate through all edges,
// adding each to inners, outers, etc,
// as appropriate.
// Look for the cornersâ€”add those to solution.
// Add each non-flat edge of the corner
// to exposed_edges.

}

void solve() {
for (Edge edge1 : exposed_edges) {
// Look for a match to edge1
if (edge1.type == Edge.Type.inner) {
for (Edge edge2 : outers) {
if (edge1.fitsWith(edge2)) {
// We found a match!
// Remove edge1 from
// exposed_edges.
// to solution.
// Check which edges of edge2
// those to exposed_edges.
}
}
// Do the same thing,
// swapping inner & outer.
}
}
}
}

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5b2de8d1054be', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5b2de8d1054ef',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5b2de8d1054f1',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});