Easy way to generate 8 piece sliding puzzle so that it is always solveable?

Question

Ok so I recently added a mini-game to a much larger action RPG I'm working on.

The game is a sliding puzzle with 8 pieces. You can move pieces individually as long as they are moving into the empty slot.

So my tile lay out for the puzzle is like this:

1 2 3

4 5 6

7 8 9

Now going into this I thought this would be a super easy problem something I could complete easily within a few hours...

But the more I work on this the more annoying it becomes haha!

So I have it set up right now so all the pieces move correctly as expected. And I set up a randomization system so that all the pieces would begin in a random position.

BUT my randomization system also made it so that no piece could ever begin in it's starting position.

To my surprise I learned that if puzzle piece positions in this kind of puzzle are generated completely randomly then they are only solvable 50% of the time based off whether there is an even amount of permutations.

I believe having the pieces generate so that none of them can ever start in their final position causes the 50% chance to drop much lower perhaps even to 0% chance of being solvable? Not sure what the chance is but out of 5+ puzzles generated in this fashion none have been solvable so far...

Now I don't have the mathematical or programming background to easily figure out the algorithms for the puzzles to always generate in a way they are solvable. If my entire game was a puzzle I would take the time to try to figure it out, but given this is supposed to be a mini-game within my action RPG which will probably account for less than 5% of play time even if we use the puzzle in multiple levels, I really can't spend any more time goofing around with this.

It's getting to the point where I'm just going to take the finished position and move things around by myself to create predetermined starting positions that are solveable instead of attempting to generate them randomly...

I've already looked online for solutions but none of them look easily implementable with my math/program background in a reasonable time frame.

So my question is:

Does anyone have a code example how to randomly generate tiles in the configuration:

1 2 3

4 5 6

7 8 9

in a way that is always solveable? 7 is the empty piece in our current puzzle when the puzzle is complete.

Answer 1

Answer by Eric5h5 · Aug 26, 2013 at 12:57 AM

Starting from the final configuration, just have a routine that finds the possible pieces that could be moved to the hole position, and pick one at random to move there. Do this in a loop a few dozen times, and you end up with a scrambled puzzle that's guaranteed to be solvable since it's just "playing" the game, backward.

Add comment · Show 2 · Share

RyanZimmerman87 · Aug 26, 2013 at 02:30 AM 0

Share

Thanks guys, I think I'll give this a go in the next few days. That should probably be quite a bit easier than having the randomization follow the rules with some complex logic. Seems like reverse scrambling the solved position like you both suggested will be the best solution for me at this point.

I didn't realize this problem had so many variables to take into consideration to even have the puzzle be solvable! Much more complicated than I expected, but I'll mark this as solved after I give that a shot in near future. I have some other stuff I need to work on for next few days after spending so much time on this.

Eric5h5 · Aug 26, 2013 at 02:34 AM 0

Share

Ha, robertbu posted basically the same thing as I did at the same time, so it must be the way to go. ;)

Answer 2

Answer by RishBee · Jul 17, 2015 at 04:59 PM

The Brute force method might be the best approach in this case (and for my mini game too :) ) but if you want a truly random start position, this might be a good article to read!

Add comment · Show 1 · Share

Caldas · Jul 30, 2017 at 05:50 PM 0

Share

What is the Brute force?

Answer 3

It's too late? @RyanZimmerman87

 public class Puzzle
 {
     public int[] puzzle = {1, 2, 3,
                            4, 5, 6,
                            7, 8, -1};
 
     private int[,] connections = { { 1, 3, -1, -1 }, { 0, 2, 4, -1 }, { 1, 5, -1, -1 },
                                   { 0, 4, 6, -1 }, { 1, 3, 5, 7 }, { 2, 4, 8, -1 }, 
                                   { 3, 7, -1, -1 }, { 4, 6, 8, -1 }, { 5, 7, -1, -1 } };
 
     public void Generate(int iterations)
     {
         for(int a = 0; a < iterations; a++)
         {
             Next();
         }
     }
 
     public void Next()
     {
         for (int x = 0; x < puzzle.Length; x++)
         {
             if (puzzle[x] == -1)
             {
                 List<int> possibleConnections = new List<int>();
 
                 for (int m = 0; m < 4; m++)
                 {
                     if (connections[x, m] != -1)
                     {
                         possibleConnections.Add(connections[x, m]);
                     }
                 }
                 int target = RandomValueFromArray(possibleConnections.ToArray());
                 int targetValue = puzzle[target];
                 puzzle[target] = puzzle[x];
                 puzzle[x] = targetValue;
                 return;
             }
         }
     }
 
     public T RandomValueFromArray<T>(T[] array)
     {
         return array[Random.Range(0, array.Length)];
     }
 
 }

Easy way to generate 8 piece sliding puzzle so that it is always solveable?

3 Replies

Your answer

Welcome to Unity Answers

Follow this Question

Related Questions