The impossible 15-Puzzle

Game Play & Game Design
#1

Hello, I created a game about 15-Puzzle, is a map 4x4 with tiles. Everything is working perfectly, but I have a problem with “random generation” of each frame, because there is an impossible and unsolvable puzzle and I don’t understand exactly how this works, how can I position all tiles following the game logic to avoid the unsolvable puzzle, what is the algorithm to generate a random 15-puzzle solvable

http://www.cse.wustl.edu/~kjg/cs123/Labs/raster/15.gif

There are 3+ ways to get an unsolvable puzzle, but I’m not understanding the “standard” of impossibilities, Source:

#2

Instead of just placing the tiles randomly, why don’t you start with a solved puzzle and randomly mess it up for X iterations?

#3

Yep, either have a fast enough solver that can check candidates for solvability, or permute backwards from the solved puzzle.

#4

Yeah, I can try “reverse” mode to randomize the tiles, maybe I have some delay to generate some great random (500~1000 moves+).

I was thinking something like this: http://kociemba.org/fifteen/fifteensolver.html
The “Fifteen Puzzle Optimal Solver” can generate random puzzles very fast and all are solvable, I think is using some algorithm to easily fill the grid.

I will try to do the reverse to see how it looks.

#5

You could also use “reverse mode” to generate puzzles ahead of time, and then store a bunch of precomputed possible configurations. Then you can just choose one randomly, which will be very fast.

#6

I doubt reverse iteration is very slow, but if you want pregenerated puzzles you could even generate them in the background while the player sits in menus, etc. although if this is for mobile that may not be a good idea.

#7

The first link you posted with the permutations is probably the easiest test. In their first 15-puzzle example they describe the board position as:

(1 11 10 9 2 3 4 7 12 13 8 * 6 15)(5 14)

The first set of parentheses says that tile 1 is in the position that would have 11 in the solution. 11 is in the position that 10 would have. 10 is in position 9 etc.
The second set of parentheses says that tile 5 is in position 14 and tile 14 is in position 5.

You can count the size of these cycles by picking one tile to start with and just following the trail of permutations. Then picking an unvisited tile and repeating until no more tiles are left unvisited.

Count the number of cycles that have an even number of tiles in them. If this count is even, your arrangement is solvable.

#8

Don’t quote me, but I recall that for the classic 15 puzzle, exactly half of
all positions are impossible, and that a simple counting algorithm can be used
to determine which half any position is in.

#9

I don’t understand perfectly, but let’s try.

This is a random image:

(1- * 2 6 5 9 12 14 13 15- 3- 4-) (7 11) (8 10).
- is when I need to start with other number.

This is solvable because I have 15 cycles? ???

And the puzzle below is unsolvable because I have 16 cycles?

#10

Here’s how the counting goes:

  • The cycle starting at 1 is (1) because it is already in the correct location. Even cycle count is still: 0
  • The cycle starting at 2 is (2 6 5 9 12 14 13 *). Even cycle count is now: 1
  • The cycle starting at 3 is (3). Even cycle count is still: 1
  • The cycle starting at 4 is (4). Even cycle count is still: 1
  • The cycle starting at 7 is (7 11). Even cycle count is now: 2
  • The cycle starting at 8 is (8 10). Even cycle count is now: 3
  • The cycle starting at 15 is (15). Even cycle count is still: 3

There are no more tiles that aren’t in a cycle so we are done. The number of even cycles is 3, which is odd. So the arrangement is not solvable.

To get the long cycle, you look at the first tile which is 2. It’s position in the arrangement is the one that 6 should be in in the solution. So 6 is next in the cycle. Then we look at tile 6. It’s position in the arrangement is the one that 5 should be in in the solution. etc. When we get to the blank spot *, it is in the position that 2 should be in in the solution, but we’ve already processed 2 so the cycle has finished.

Hope that helps.

Edit: Your last example has cycles (1)(2)(3)(4)(5)(6)(7)(8 )(9)(10)(11)(12)(13)(14 15)(*). There is one even cycle. That’s an odd number, so not solvable either.

#11

I remember hearing a story about someone who switched 15 and 14 around and would give people $100 (maybe) if they could solve it. They didn’t have to give up a single penny. I can’t say for that first puzzle but I remember this case specifically.

#12

One thing I should have mentioned: I was assuming the blank space would be at the bottom right. Everything above is still correct, but the rule “even number of even cycles -> solvable” holds when the blank space is at an even position (e.g. bottom right is position 16, in your other example the blank space is at position 2).

When the blank space is in an odd position, the rule is “odd number of even cycles -> solvable”.

If I find time today I’ll put it in code…

Edit: here you go:

	
	/**
	 * 
	 * @param state A 16-length array of tiles for each position. Tile "0" is the gap.
	 * @return Whether this state can reach [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0] by sliding tiles.
	 */
	public static boolean isSolvable(int[] state){
		//prepare the mapping from each tile to its position
		int[] positions = new int[16];
		for(int i = 0; i < state.length; i++){
			positions[state[i]] = i;
		}
		
		//check whether this is an even or odd state
		boolean isEvenState = positions[0] % 2 == 0;
		
		//count the even cycles
		int evenCount = 0;
		boolean[] visited = new boolean[16];
		for(int i = 0; i < positions.length; i++){
			if(visited[i]) 
				continue; 
			//a new cycle starts at i. Count its length..
			int cycleLength = 0;
			int nextTile = i;
			while(!visited[nextTile]){
				cycleLength++;
				visited[nextTile] = true;
				nextTile = positions[nextTile];
			}
			
			if(cycleLength % 2 == 0)
				evenCount++;
		}
		
		return isEvenState == (evenCount % 2 == 0);
	}

Examples:
Is the goal state solvable?

System.out.println(isSolvable(new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0}));

“true”

Is one move from the goal state solvable (having moved tile 15)?

System.out.println(isSolvable(new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13,14,0,15}));

“true”

If you swap tiles 14 and 15 is it solvable?

System.out.println(isSolvable(new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13,15,14,0}));

“false”

Is your other example solvable?

System.out.println(isSolvable(new int[]{1,0,3,4,6,2,11,10,5,8,7,9,14,12,15,13};));

“false”

Those are the only tests I’ve done, but the code seems to be bug free.

#13

Hello, I implemented your code to runs with my code, sometimes works sometimes does not work.

1 - I create an Array of Integer (0-15), shuffle the Array, and send to your method (isSolvable(new int[]{a(0),a(1)…}).
2 - isSolvable() returns true or false, if false, shuffle again and send to your method until returns true.
3 - If true, I fill the grid with all positions based on the sequence sent to the method that returns true.

Sometimes works, sometimes does not work (sorry for the big image,the left side is the start position, the right side is when I tried to solve the puzzle manually).

http://s28.postimg.org/ba6c7ttz1/img.png

#14

My apologies, there was a bug after all. Using “0” to represent the gap makes the indexing a bit confusing and the even/odd state check was wrong.

   /**
	 * 
	 * @param state A 16-length array of tiles for each position. Tile "0" is the gap.
	 * @return Whether this state can reach [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0] by sliding tiles.
	 */
	public static boolean isSolvable(int[] state){
		//prepare the mapping from each tile to its position
		int[] positions = new int[16];
		for(int i = 0; i < state.length; i++){
			positions[state[i]] = (i+1)%16;
		}
		
		//check whether this is an even or odd state
		int row = (positions[0]-1)/4;
		int col = (positions[0]-1)-row*4;
		boolean isEvenState = positions[0] == 0 || row % 2 == col %2;
		
		//count the even cycles
		int evenCount = 0;
		boolean[] visited = new boolean[16];
		for(int i = 0; i < positions.length; i++){
			if(visited[i]) 
				continue; 
			//a new cycle starts at i. Count its length..
			int cycleLength = 0;
			int nextTile = i;
			while(!visited[nextTile]){
				cycleLength++;
				visited[nextTile] = true;
				nextTile = positions[nextTile];
			}
			if(cycleLength % 2 == 0)
				evenCount++;
		}
		return isEvenState == (evenCount % 2 == 0);
	}

If you have code that makes a whole lot of random swaps from the goal that would be a good way to test the correctness.

#15

Now is working! great job!

I tried 30x+ and I solved all, I’ll try code some algorithm to solve automatically based on default moviments in some parts, then I can test more fast, but I think everything is working now.

Thanks for the patience, the explanation and the code. :wink: