- Home /
Easy way to generate 8 piece sliding puzzle so that it is always solveable?
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.
There's the brute force method. Start with the puzzle sorted, and then make a random number of moves to unsort the puzzle. The results will always be solvable.
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.
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! $$anonymous$$uch 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.
Ha, robertbu posted basically the same thing as I did at the same time, so it must be the way to go. ;)
Answer by No_Username_Found · Jan 07, 2021 at 03:02 PM
[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.
Answer by c4ctus · Jul 30, 2017 at 06:43 PM
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)];
}
}
Your answer
Follow this Question
Related Questions
Need help finding why my onGUI() sliding image puzzle has errors! 1 Answer
FPS Character keeps randomly sliding and rotating 2 Answers
Randomized Light Sequence Puzzle Script 0 Answers
Crossword game - How to start a word on a random location of players choice 0 Answers
Sliding a sprite inside a grid 0 Answers