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() {
			List<MyPiece> pieceList = new LinkedList<MyPiece>();
			for (MyPiece piece : picture.pieces) {
				pieceList.add(piece);
			}
			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.
							// Add edge2's piece
							// to solution.
							// Check which edges of edge2
							// are exposed, and add
							// those to exposed_edges.
						}
					}
					// Do the same thing,
					// swapping inner & outer.
				}
			}
		}
	}
Advertisements

1 Comment (+add yours?)

  1. Diksha
    Jul 01, 2012 @ 17:20:00

    Nice post. But data structure with explanation in words would be more helpful.

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: