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

Archived Forums Questions & Answers
1

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.

2

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.

5

[I know the question is old, but Google still sends people here.]

My suggestion is to start with the solved puzzle, then write code to scramble it. Start at the empty location, randomly select a connected piece, slide that piece, repeat 20 or 30 times.

Since the end result was achieved using legal moves, you know that it is solvable if the player reverses those moves. However, randomness means less predictability on how hard it will be, and 30 scrambling moves may actually be solvable in only 3.

So there’s still a lot to think about in how you handle the scrambling, and you’d probably want a flag on each block so your scramble code doesn’t select the same tile to move twice in a row.

3

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

4

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)];
    }

}