Java-Gaming.org Hi !
 Featured games (91) games approved by the League of Dukes Games in Showcase (806) Games in Android Showcase (239) games submitted by our members Games in WIP (868) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
 Home Help Search Login Register
Pages: [1]
 ignore  |  Print
 The impossible 15-Puzzle  (Read 53957 times) 0 Members and 1 Guest are viewing this topic.
craftm

JGO Coder

Medals: 15
Projects: 1

_Keep Trying

 « Posted 2015-02-10 18:15:03 »

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

There are 3+ ways to get an unsolvable puzzle, but I'm not understanding the "standard" of impossibilities, Source:
- http://www.math.ubc.ca/~cass/courses/m308-02b/projects/grant/fifteen.html
- http://mathworld.wolfram.com/15Puzzle.html
- http://en.wikipedia.org/wiki/15_puzzle
- http://kociemba.org/fifteen/fifteensolver.html

_
KevinWorkman

« JGO Plugged Duke »

Medals: 288
Projects: 12
Exp: 12 years

HappyCoding.io - Coding Tutorials!

 « Reply #1 - Posted 2015-02-10 18:18:17 »

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

HappyCoding.io - Coding Tutorials!
Happy Coding forum - Come say hello!
BurntPizza

« JGO Bitwise Duke »

Medals: 486
Exp: 7 years

 « Reply #2 - Posted 2015-02-10 18:20:35 »

Yep, either have a fast enough solver that can check candidates for solvability, or permute backwards from the solved puzzle.
 Games published by our own members! Check 'em out!
craftm

JGO Coder

Medals: 15
Projects: 1

_Keep Trying

 « Reply #3 - Posted 2015-02-10 18:33:59 »

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.

_
KevinWorkman

« JGO Plugged Duke »

Medals: 288
Projects: 12
Exp: 12 years

HappyCoding.io - Coding Tutorials!

 « Reply #4 - Posted 2015-02-10 18:36:45 »

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.

HappyCoding.io - Coding Tutorials!
Happy Coding forum - Come say hello!
BurntPizza

« JGO Bitwise Duke »

Medals: 486
Exp: 7 years

 « Reply #5 - Posted 2015-02-10 18:42:39 »

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.
Jono
 « Reply #6 - Posted 2015-02-10 20:40:50 »

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 `(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.
ddyer
 « Reply #7 - Posted 2015-02-11 07:35:21 »

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.
craftm

JGO Coder

Medals: 15
Projects: 1

_Keep Trying

 « Reply #8 - Posted 2015-02-11 13:02:46 »

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 `(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.
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?

_
Jono
 « Reply #9 - Posted 2015-02-11 14:23:08 »

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.
 Games published by our own members! Check 'em out!
Longarmx
 « Reply #10 - Posted 2015-02-12 03:19:33 »

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

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.

Jono
 « Reply #11 - Posted 2015-02-12 08:52:34 »

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:
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37 `      /**    *     * @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?
 1 `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)?
 1 `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?
 1 `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?
 1 `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.
craftm

JGO Coder

Medals: 15
Projects: 1

_Keep Trying

 « Reply #12 - Posted 2015-02-12 18:09:39 »

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:

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).

_
Jono
 « Reply #13 - Posted 2015-02-12 21:52:02 »

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.

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36 `   /**    *     * @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.
craftm

JGO Coder

Medals: 15
Projects: 1

_Keep Trying

 « Reply #14 - Posted 2015-02-12 23:16:28 »

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.
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.
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.

_
Pages: [1]
 ignore  |  Print

 Riven (587 views) 2019-09-04 15:33:17 hadezbladez (5533 views) 2018-11-16 13:46:03 hadezbladez (2410 views) 2018-11-16 13:41:33 hadezbladez (5794 views) 2018-11-16 13:35:35 hadezbladez (1233 views) 2018-11-16 13:32:03 EgonOlsen (4669 views) 2018-06-10 19:43:48 EgonOlsen (5688 views) 2018-06-10 19:43:44 EgonOlsen (3205 views) 2018-06-10 19:43:20 DesertCoockie (4104 views) 2018-05-13 18:23:11 nelsongames (5125 views) 2018-04-24 18:15:36
 princec 9x KaiHH 7x Ali-RS 6x gouessej 5x VaTTeRGeR 5x elect 4x mudlee 3x Rain8 2x philfrei 2x SteveSmith 2x saocrinn 1x Akazan 1x bullen 1x SHC 1x ral0r2 1x
 A NON-ideal modular configuration for Eclipse with JavaFXby philfrei2019-12-19 19:35:12Java Gaming Resourcesby philfrei2019-05-14 16:15:13Deployment and Packagingby philfrei2019-05-08 15:15:36Deployment and Packagingby philfrei2019-05-08 15:13:34Deployment and Packagingby philfrei2019-02-17 20:25:53Deployment and Packagingby mudlee2018-08-22 18:09:50Java Gaming Resourcesby gouessej2018-08-22 08:19:41Deployment and Packagingby gouessej2018-08-22 08:04:08
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org