1

Note: This question is not about this particular instance of this grid with these exact words, but about any combination of words.

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.

enter image description here

Florian Walther
  • 119
  • 3
  • 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. – Philip Kendall Dec 29 '22 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? – Doc Brown Dec 29 '22 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. – Florian Walther Dec 29 '22 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 '22 at 15:34
  • @Ewan I think it doesn't work because of similar letters – Florian Walther Dec 30 '22 at 16:20
  • You could maybe contact the maker of this game: https://wafflegame.net/. They have it set up where every puzzle is solvable in 10 moves. – Tyberius Dec 30 '22 at 20:56

3 Answers3

2

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.

candied_orange
  • 102,279
  • 24
  • 197
  • 315
  • 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. – Martin Maat Dec 31 '22 at 09: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 '22 at 13:17
  • eg ABCD -> BCDA has four characters out of place but requires three swaps – Ewan Dec 31 '22 at 13:19
  • @candied_orange meh – Martin Maat Dec 31 '22 at 15:18
  • @MartinMaat with enough identical letters there's no way for any position to require 10 swaps. – candied_orange Dec 31 '22 at 15:49
  • @Ewan you're right about BCDA. Note edit to "Choose only swaps that put 2 *in place* characters out of place" – candied_orange Dec 31 '22 at 15:49
1

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.

candied_orange
  • 102,279
  • 24
  • 197
  • 315
  • 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. – Florian Walther Dec 30 '22 at 09: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. – candied_orange Dec 30 '22 at 12:54
1

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.

Ewan
  • 70,664
  • 5
  • 76
  • 161
  • Why random? Why not use [permutation](https://stackoverflow.com/questions/8306654/finding-all-possible-permutations-of-a-given-string-in-python)? Just hack it so it wont move the spaces. – candied_orange Dec 30 '22 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 – candied_orange Dec 30 '22 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. – candied_orange Dec 30 '22 at 18:24
  • Thought I'd found a solution but [Counting number of swaps to make two strings equal in linear time](https://cs.stackexchange.com/questions/143527/counting-number-of-swaps-to-make-two-strings-equal-in-linear-time) counts *adjacent* swaps. Sigh. – candied_orange Dec 30 '22 at 18:48
  • I think this one might work: [Transform One String to Another using Minimum Number of Given Operation](https://www.geeksforgeeks.org/transform-one-string-to-another-using-minimum-number-of-given-operation/) – candied_orange Dec 30 '22 at 18:54
  • you only have to remember 10 states, the moves might be more of a problem – Ewan Dec 30 '22 at 22:42
  • 1
    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 '22 at 22:45
  • is it a "selection sort"? "The selection sort has the property of minimizing the number of swaps" – Ewan Dec 30 '22 at 22:53
  • I think I finally solved this. It's embarrassing how simple the math involved turned out to be. – candied_orange Dec 31 '22 at 08:32