Puzzle time - strange dominoes
-
This is not a puzzle of the kind that requires some deep insights. It is really a puzzle.
Imagine domino tiles that have sequences of the letters A and B on both sides.
For instance, you are given an unlimited amount these three tiles (Upper half letters - Lower half letters):
- B - BAB
- BA - AA
- ABB - BB
Can you find a sequence of tiles such that the letter sequence of the upper halfs is the same as the letter sequence of the lower tiles?
For these three tiles, a solution would be the sequence 1,3,2,3:
The upper halfs yield the string B-ABB-BA-ABB, or BABBBAABB.
The lower halfs yield the string BAB-BB-AA-BB, or BABBBAABB.Your task is to find a sequence with these properties for these types of tiles (you have an unlimited amount of each):
- AAB - A
- AB - ABB
- AB - BAB
- BA - AAB
Warning: It isn't easy to find a solution, but I can guarantee that a solution exists.
-
As I wrote, there is no insight I know of that could help you. Whether you need a computer depends on how much you like to do puzzles. That said, it is not easy to get a computer to help you with this.
The deep insight that makes this problem interesting is in understanding how hard these kinds of puzzles are.
-
Why is this problem interesting? It is interesting because, in a very precise technical sense, it is impossible to solve. There is no "algorithm" a human or any machine could follow that can tell whether there's a solution for a set of tiles or not. While that may be possible for a particular set of tiles, it is impossible to have an algorithm that works for every et of tiles.
The intuitive reason for that sad property is that one can encode arbitrary "computation" into the tiles in such a way that adding tiles corresponds to execution steps of a computer. For instance, one could, theoretically at least, translate the whole Windows operating system into a set of tiles for this game such that the game has a solution if and only if the Windows code contains a bug that results in a blue screen. Similarly, one could translate all of mathematics into a set of tiles such that there is a solution to the game if and only if mathematics is consistent.
In the literature, this game is known as the "Post correspondence problem", and it is standard material in most undergraduate introductions to the theory of computation.
-
Sure you could automate it for this set of tiles. It would be trial and error is all. But had I bothered automating the manual procedure I was using (for up to about 20 tiles) I would have found this.
I knew the starting tile had to be 2 and the ending had to be three.
Basically the placement of the next tile was often determined by the longer of the two concatenated ‘words’ (in this case the bottom) however whenever you needed to add an ‘AB’ to the top there were two options. You just had to keep following both until one hit a dead end.
Like I said, I got to about 20 by hand and put it down. I intended to pick it back up but never did.
When I picked it back up o was going to work backwards from tile 3 and see where that got me.
-
Sure you could automate it for this set of tiles. It would be trial and error is all. But had I bothered automating the manual procedure I was using (for up to about 20 tiles) I would have found this.
I knew the starting tile had to be 2 and the ending had to be three.
Basically the placement of the next tile was often determined by the longer of the two concatenated ‘words’ (in this case the bottom) however whenever you needed to add an ‘AB’ to the top there were two options. You just had to keep following both until one hit a dead end.
Like I said, I got to about 20 by hand and put it down. I intended to pick it back up but never did.
When I picked it back up o was going to work backwards from tile 3 and see where that got me.
@jon-nyc said in Puzzle time - strange dominoes:
Sure you could automate it for this set of tiles. It would be trial and error is all. But had I bothered automating the manual procedure I was using (for up to about 20 tiles) I would have found this.
You could certainly automate searching for it. But you wouldn't know when to stop the search. You can't limit the search depth. You can't "decide" the problem: There is no algorithm which will tell you for every set of tiles whether there is a solution.
