Image 15-Puzzle mechanics

Image 15 Puzzle theory

Remember those Image Puzzle (otherwise known as 15-puzzle, 16-puzzle, or variants thereof), where you have to slide around sections of an image to get it into order?

If you're as old as me, perhaps you had some of those little plastic handheld ones?

Image / 15-Puzzle example in Javascript & Canvas

Personally, I was terrible at them and used to pop the pieces out and cheat, but whilst I'm not great help at solving them, I can at least show you how to write them. First of all, let's look at how they work...

15-Puzzle mechanics

We start with an image with a known width and height, and a known number of tiles we want to section the image in to (gridW, gridH):

[Tile Object]:
	[image position]	= [x, y];
	[canvas position]	= [x, y];

[Image Tiles] = Array();
[Free Position] = [(gridW - 1), (gridH - 1)];

for y = 0 to (gridH - 1):
	for x = 0 to (gridW - 1):
		if x==(gridW - 1) and y==(gridH - 1) then skip;
		t = new [Tile Object];
		t.[image position] = [x, y];
		t.[canvas position] = [x, y];
		[Image Tiles].add( t );
	end x loop
end y loop

This gives us a grid where each image segment is on the same position on the canvas (or game screen) as it is on the source image, with a tile at the bottom right of the image not included. This is how the puzzle will look when it's solved, but wouldn't make for an interesting game, so lets look at how we'll shuffle this grid.

Shuffling the 15-puzzle

With our [Image Tiles], and the "hole" or free position at [gridW - 1, gridH - 1]. Shuffling is quite simple:

for i = 0 to (some number, let's say 100):
	[dir] = (Select random direction; up, down, left, or right);
	if [Free Position] modified by [dir] is in map bounds:
		swap [Free Position] and [Image Tiles] entry at ([Free Position] modified by [dir])'s [canvas position]
	end if
end i loop

In other words, for each loop iteration we choose a cardinal direction, and if the tile in this direction relative to the [Free Position] is inside the grid bounds; if so, we swap the [Free Position] coordinates and the [Tile Object]'s [canvas position] property in this direction.

This works as though you had taken the solved puzzle and shifted pieces around the board at random to shuffle it.

Page loaded in 0.086 second(s).