# How can I mix this grid to guarantee it being solvable in X minimum steps?

I am programming a puzzle game where you have to arrange a grid of words correctly. The image below shows a final grid. The grid is represented by a two-dimensional string array and could look like this (the empty spaces are represented by `undefined` elements):

``````const crosswordGrid = [
["a", "u", "d", "i", "t",],
["t", undefined, "e", undefined, "e",],
["t", "r", "i", "c", "e",],
["i", undefined, "g", undefined, "t",],
["c", "o", "n", "c", "h",],
];
``````

How could I mix the characters in this grid in a way that it's guaranteed solvable in X minimum steps (for example, 10)?

Note: By "step" I mean a swap of any two arbitrary characters/tiles anywhere on the entire grid. The shape of the grid stays the same and the `undefined` elements stay in place.

Clearly, I can't just swap 10 random tiles because the same letters in different places will require fewer necessary swaps to get back to the correct solution. I tried swapping tiles as a chain, but that also didn't work.

• One option is to make 10 random moves, then brute force to see if you can solve in less than 10 moves. If you can, make another random move. Repeat until the fastest solution is 10 moves. Dec 29, 2022 at 21:41
• Your question is unclear, you did not define what a "step" is. Do you mean a swap of two neighboured cells? A swap of two arbitrary cells? Reversing a chain of cells? Dec 29, 2022 at 22:20
• @DocBrown Thank you, I added a sentence for clarification. A step is indeed the swap of any two characters on the grid. Dec 29, 2022 at 23:03
• surely the 10 random swaps works if you just check that you aren't moving a character to a correct position in the finished grid?
– Ewan
Dec 30, 2022 at 15:34
• @Ewan I think it doesn't work because of similar letters Dec 30, 2022 at 16:20

How could I mix the characters in this grid in a way that it's guaranteed solvable in X minimum steps (for example, 10)?

Model the grid as a string of 21 characters and the solution position is:

``````auditteetriceigtconch
``````

Choose only swaps that put 2 in place characters out of place (as opposed to swaps that put 1 or 0 out of place). Then a position that requires 10 steps/swaps to solve will leave 20 characters out of place.

For example compare this position (1st line) to the solution (2nd line). Solving will require at least 10 swaps:

``````uaideettrtciietgoccnh
auditteetriceigtconch
``````

Notice that only the last letter is in the correct position. 20 are out of place. No fewer than 10 swaps can solve this because a swap can correct at most two letters out of place. 20 / 2 = 10.

• There is an issue with this approach. You did not present an algorithm, just a requirement. The tempting algorithm would be to try the first two, check if they are a double displacement and proceed. If they are the same letters, try 1 and 3, et cetera. But this would fail if at the end you have a series of identical letters. You will be out of good moves before 10. Dec 31, 2022 at 9:31
• yes I think this is a simplified version of my answer. However. is it not possible that a 20 out of place string might take more than 10 swaps?
– Ewan
Dec 31, 2022 at 13:17
• eg ABCD -> BCDA has four characters out of place but requires three swaps
– Ewan
Dec 31, 2022 at 13:19
• @candied_orange meh Dec 31, 2022 at 15:18
• @MartinMaat with enough identical letters there's no way for any position to require 10 swaps. Dec 31, 2022 at 15:49

You need a function that solves the puzzle and tells you how many steps it takes. Such a function will get slower the more steps it takes. You can speed it up with a hash n cache strategy. Every puzzle position can be serialized as a single string (hint, try using spaces). Every string can be hashed. Once you know the number of steps needed to solve the puzzle cache it by dumping the hash and the step count into a hash table. Now you never have to calculate the steps for the same position twice. If you've seen a position before you've already got the step count. The critical thing here is to store the hash NOT the string. This trick spends space to gain time. So don't waste space.

Optimizing even further, let the solving function use the hashes. If it finds a position it has seen before it can just stop hunting and add the calculated step count to the stored step count.

To satisfy the minimal step requirement a breadth first search must be made to find all hashes in a step count before moving to the next one. That is, find all hashes reachable with one step before finding ones reachable with two steps. This will avoid cycling since it ensures a hash will be first discovered with the fewest steps.

With that the function simplifies into not much more than a legal move generator.

• Thank you. I don't understand what any of that means. I was hoping that the puzzle can be mixed in a way that simply needs the same number of steps to get "unmixed" again. A certain way of swapping characters. Dec 30, 2022 at 9:34
• @FlorianWalther using two steps you could swap the corners diagonally. AH & TC. Pass that new position into the solving function and it'll return 2. Since 2 is how many moves you made you know there is no shortcut to solving it from here. However, look at the TEE in the second row. Swap TE to make the second row ETE then swap TE to make EET. It took 2 steps to get here but the solving function will return 1 because 1 ET swap is enough to get back to TEE. Dec 30, 2022 at 12:54

OK here's my solution.

• you start from the end with the target grid. this is state 0

• you swap a random pair, this creates a new state

• you compare with all previous states

• if one or more of the moved tiles match a previous state, ie you have moved E around and its ended up on a square which, in a previous state had an E in it, reject the new state and try a different random swap

• else, add this state to the list and loop

• all possible swaps tried? reject two steps and continue from there.

Note that you need to keep track of all the attempted moves for the case where its difficult or impossible to create a 10 move puzzle.

So our test cases

1. start TEE, swap 2 and 3, TEE - 0 moves required to solve

both moved squares have the same letter in state 1 and state 0, reject

1. start TEE, swap 1 and 2, swap 2 and 3, EET - 1 move to solve

move 1 is OK, move 2 fails because square 2 has an E in both state 0 and state 2

1. start TEE, swap 2 and 3 n times

fails immediately on move 1

## Optimising?

Well you can see that if you have less than ten letters it will be impossible to make a ten move puzzle. so reject immediately

If you move a letter than hasn't been previously moved, its more likely not to be rejected.

Check for duplicate letters before moving.

## How to prove this solution?

After each move 2 letters will be in incorrect squares. because we compare to state 0. requiring at least 1 move to fix.

This is true of all the states and moves. every move creates 2 incorrect squares compared with any other state. each state has to be independently resolved.

• Why random? Why not use permutation? Just hack it so it wont move the spaces. Dec 30, 2022 at 17:34
• Hah, I just realized you can simply ignore the spaces. You only need them when presenting. Puzzle state is always a 21 character string. Leave out the spaces and permute it normally. The solution string is: auditteetriceigtconch Dec 30, 2022 at 17:45
• Also just realized "comparing with all previous states" might be an issue. We're talking about 946 Petabytes of 64 bit hashs. Might cause a cache miss. This was a lot smaller state space when I thought it was a sliding puzzle game. Dec 30, 2022 at 18:24
• Thought I'd found a solution but Counting number of swaps to make two strings equal in linear time counts adjacent swaps. Sigh. Dec 30, 2022 at 18:48
• yeah i think this must be an interview question or something, if you think about it as a single dimension array you are effectively sorting it, so if you know all the various sorts and O complexities there is probably a comparable one.
– Ewan
Dec 30, 2022 at 22:45