• Products
  • Solutions
  • Made with Unity
  • Learning
  • Support & Services
  • Community
  • Asset Store
  • Get Unity

UNITY ACCOUNT

You need a Unity Account to shop in the Online and Asset Stores, participate in the Unity Community and manage your license portfolio. Login Create account
  • Blog
  • Forums
  • Answers
  • Evangelists
  • User Groups
  • Beta Program
  • Advisory Panel

Navigation

  • Home
  • Products
  • Solutions
  • Made with Unity
  • Learning
  • Support & Services
  • Community
    • Blog
    • Forums
    • Answers
    • Evangelists
    • User Groups
    • Beta Program
    • Advisory Panel

Unity account

You need a Unity Account to shop in the Online and Asset Stores, participate in the Unity Community and manage your license portfolio. Login Create account

Language

  • Chinese
  • Spanish
  • Japanese
  • Korean
  • Portuguese
  • Ask a question
  • Spaces
    • Default
    • Help Room
    • META
    • Moderators
    • Topics
    • Questions
    • Users
    • Badges
  • Home /
avatar image
0
Question by RyanZimmerman87 · Aug 26, 2013 at 12:27 AM · randomonguipuzzlesliding

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.

Comment
Add comment · Show 1
10 |3000 characters needed characters left characters exceeded
▼
  • Viewable by all users
  • Viewable by moderators
  • Viewable by moderators and the original poster
  • Advanced visibility
Viewable by all users
avatar image robertbu · Aug 26, 2013 at 12:53 AM 0
Share

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.

4 Replies

· Add your reply
  • Sort: 
avatar image
2

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.

Comment
Add comment · Show 2 · Share
10 |3000 characters needed characters left characters exceeded
▼
  • Viewable by all users
  • Viewable by moderators
  • Viewable by moderators and the original poster
  • Advanced visibility
Viewable by all users
avatar image 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! $$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.

avatar image 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. ;)

avatar image
1

Answer by No_Username_Found · Jan 07 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.

Comment
Add comment · Share
10 |3000 characters needed characters left characters exceeded
▼
  • Viewable by all users
  • Viewable by moderators
  • Viewable by moderators and the original poster
  • Advanced visibility
Viewable by all users
avatar image
0

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!

Comment
Add comment · Show 1 · Share
10 |3000 characters needed characters left characters exceeded
▼
  • Viewable by all users
  • Viewable by moderators
  • Viewable by moderators and the original poster
  • Advanced visibility
Viewable by all users
avatar image Caldas · Jul 30, 2017 at 05:50 PM 0
Share

What is the Brute force?

avatar image
0

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)];
     }
 
 }
Comment
Add comment · Share
10 |3000 characters needed characters left characters exceeded
▼
  • Viewable by all users
  • Viewable by moderators
  • Viewable by moderators and the original poster
  • Advanced visibility
Viewable by all users

Your answer

Hint: You can notify a user about this post by typing @username

Up to 2 attachments (including images) can be used with a maximum of 524.3 kB each and 1.0 MB total.

Welcome to Unity Answers

The best place to ask and answer questions about development with Unity.

To help users navigate the site we have posted a site navigation guide.

If you are a new user to Unity Answers, check out our FAQ for more information.

Make sure to check out our Knowledge Base for commonly asked Unity questions.

If you are a moderator, see our Moderator Guidelines page.

We are making improvements to UA, see the list of changes.



Follow this Question

Answers Answers and Comments

20 People are following this question.

avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image

Related Questions

Need help finding why my onGUI() sliding image puzzle has errors! 1 Answer

Randomized Light Sequence Puzzle Script 0 Answers

Sliding a sprite inside a grid 0 Answers

FPS Character keeps randomly sliding and rotating 2 Answers

Is there a way to add transition puzzle image in 2d sliding puzzle to another image once solved? 0 Answers

  • Anonymous
  • Sign in
  • Create
  • Ask a question
  • Spaces
  • Default
  • Help Room
  • META
  • Moderators
  • Explore
  • Topics
  • Questions
  • Users
  • Badges