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

Click to Play


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

_ Wink
Offline 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!
Offline 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!
Legends of Yore - The Casual Retro Roguelike
Offline 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.

_ Wink
Offline 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!
Offline 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.
Offline 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.
Offline 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.
Offline 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?  Huh

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

_ Wink
Offline 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!
Legends of Yore - The Casual Retro Roguelike
Offline 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.

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


_ Wink
Offline 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.
Offline 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.  Wink

_ Wink
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
A NON-ideal modular configuration for Eclipse with JavaFX
by philfrei
2019-12-19 19:35:12

Java Gaming Resources
by philfrei
2019-05-14 16:15:13

Deployment and Packaging
by philfrei
2019-05-08 15:15:36

Deployment and Packaging
by philfrei
2019-05-08 15:13:34

Deployment and Packaging
by philfrei
2019-02-17 20:25:53

Deployment and Packaging
by mudlee
2018-08-22 18:09:50

Java Gaming Resources
by gouessej
2018-08-22 08:19:41

Deployment and Packaging
by gouessej
2018-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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!