# Das verflixte Hunde-Spiel by Mark Seemann

*A puzzle kata, and a possible solution.*

When I was a boy I had a nine-piece puzzle that I'd been gifted by the Swizz branch of my family. It's called *Das verflixte Hunde-Spiel*, which means something like *the confounded dog game* in English. And while a puzzle with nine pieces doesn't sound like much, it is, in fact, incredibly difficult.

It's just a specific incarnation of a kind of game that you've almost certainly encountered, too.

There are nine tiles, each with two dog heads and two dog ends. A dog may be coloured in one of four different patterns. The object of the game is to lay out the nine tiles in a 3x3 square so that all dog halves line up.

### Game details #

The game is from 1979. Two of the tiles are identical, and, according to the information on the back of the box, two possible solutions exist. Described from top clockwise, the tiles are the following:

- Brown head, grey head, umber tail, spotted tail
- Brown head, spotted head, brown tail, umber tail
- Brown head, spotted head, grey tail, umber tail
- Brown head, spotted head, grey tail, umber tail
- Brown head, umber head, spotted tail, grey tail
- Grey head, brown head, spotted tail, umber tail
- Grey head, spotted head, brown tail, umber tail
- Grey head, umber head, brown tail, spotted tail
- Grey head, umber head, grey tail, spotted tail

I've taken the liberty of using a shorthand for the patterns. The grey dogs are actually also spotted, but since there's only one grey pattern, the *grey* label is unambiguous. The dogs I've named *umber* are actually rather *burnt umber*, but that's too verbose for my tastes, so I just named them *umber*. Finally, the label *spotted* indicates dogs that are actually burnt umber with brown blotches.

Notice that there are two tiles with a brown head, a spotted head, a grey tail, and an umber tail.

The object of the game is to lay down the tiles in a 3x3 square so that all dogs fit. For further reference, I've numbered each position from one to nine like this:

What makes the game hard? There are nine cards, so if you start with the upper left corner, you have nine choices. If you just randomly put down the tiles, you now have eight left for the top middle position, and so on. Standard combinatorics indicate that there are at least 9! = 362,880 permutations.

That's not the whole story, however, since you can rotate each tile in four different ways. You can rotate the first tile four ways, the second tile four ways, etc. for a total of 4^{9} = 262,144 ways. Multiply these two numbers together, and you get 4^{9}9! = 95,126,814,720 combinations. No wonder this puzzle is hard if there's only two solutions.

When analysed this way, however, there are actually 16 solutions, but that still makes it incredibly unlikely to arrive at a solution by chance. I'll get back to why there are 16 solutions later. For now, you should have enough information to try your hand with this game, if you'd like.

I found that the game made for an interesting kata: Write a program that finds all possible solutions to the puzzle.

If you'd like to try your hand at this exercise, I suggest that you pause reading here.

In the rest of the article, I'll outline my first attempt. Spoiler alert: I'll also show one of the solutions.

### Types #

When you program in Haskell, it's natural to start by defining some types.

data Half = Head | Tail deriving (Show, Eq) data Pattern = Brown | Grey | Spotted | Umber deriving (Show, Eq) data Tile = Tile { top :: (Pattern, Half), right :: (Pattern, Half), bottom :: (Pattern, Half), left :: (Pattern, Half) } deriving (Show, Eq)

Each tile describes what you find on its `top`

, `right`

side, `bottom`

, and `left`

side.

We're also going to need a function to evaluate whether two halves match:

matches :: (Pattern, Half) -> (Pattern, Half) -> Bool matches (p1, h1) (p2, h2) = p1 == p2 && h1 /= h2

This function demands that the patterns match, but that the halves are opposites.

You can use the `Tile`

type and its constituents to define the nine tiles of the game:

tiles :: [Tile] tiles = [ Tile (Brown, Head) (Grey, Head) (Umber, Tail) (Spotted, Tail), Tile (Brown, Head) (Spotted, Head) (Brown, Tail) (Umber, Tail), Tile (Brown, Head) (Spotted, Head) (Grey, Tail) (Umber, Tail), Tile (Brown, Head) (Spotted, Head) (Grey, Tail) (Umber, Tail), Tile (Brown, Head) (Umber, Head) (Spotted, Tail) (Grey, Tail), Tile (Grey, Head) (Brown, Head) (Spotted, Tail) (Umber, Tail), Tile (Grey, Head) (Spotted, Head) (Brown, Tail) (Umber, Tail), Tile (Grey, Head) (Umber, Head) (Brown, Tail) (Spotted, Tail), Tile (Grey, Head) (Umber, Head) (Grey, Tail) (Spotted, Tail) ]

Because I'm the neatnik that I am, I've sorted the tiles in lexicographic order, but the solution below doesn't rely on that.

### Brute force doesn't work #

Before I started, I cast around the internet to see if there was an appropriate algorithm for the problem. While I found a few answers on Stack Overflow, none of them gave me indication that any sophisticated algorithm was available. (Even so, there may be, and I just didn't find it.)

It seems clear, however, that you can implement some kind of recursive search-tree algorithm that cuts a branch off as soon as it realizes that it doesn't work. I'll get back to that later, so let's leave that for now.

Since I'd planned on writing the code in Haskell, I decided to first try something that might look like brute force. Because Haskell is lazily evaluated, you can sometimes get away with techniques that look wasteful when you're used to strict/eager evaluation. In this case, it turned out to not work, but it's often quicker to just make the attempt than trying to analyze the problem.

As already outlined, I first attempted a purely brute-force solution, betting that Haskell's lazy evaluation would be enough to skip over the unnecessary calculations:

allRotationsOf9 = replicateM 9 [0..3] allRotations :: [Tile] -> [[Tile]] allRotations ts = fmap (\rs -> (\(r, t) -> rotations t !! r) <$> zip rs ts) allRotationsOf9 allConfigurations :: [[Tile]] allConfigurations = permutations tiles >>= allRotations solutions = filter isSolution allConfigurations

My idea with the `allConfigurations`

value was that it's supposed to enumerate all 95 billion combinations. Whether it actually does that, I was never able to verify, because if I try to run that code, my poor laptop runs for a couple of hours before it eventually runs out of memory. In other words, the GHCi process crashes.

I haven't shown `isSolution`

or `rotations`

, because I consider the implementations irrelevant. This attempt doesn't work anyway.

Now that I look at it, it's quite clear why this isn't a good strategy. There's little to be gained from lazy evaluation when the final attempt just attempts to `filter`

a list. Even with lazy evaluation, the code still has to run through all 95 billion combinations.

Things might have been different if I just had to find one solution. With a little luck, it might be that the first solution appears after, say, a hundred million iterations, and lazy evaluation would then had meant that the remaining combinations would never run. Not so here, but hindsight is 20-20.

### Search tree #

Back to the search tree idea. It goes like this: Start from the top left position and pick a random tile and rotation. Now pick an arbitrary tile *that fits* and place it to the right of it, and so on. As far as I can tell, you can always place the first four cards, but from there, you can easily encounter a combination that allows no further tiles. Here's an example:

None of the remaining five tiles fit in the fifth position. This means that we don't have to do *any* permutations that involve these four tiles in that combination. While the algorithm has to search through all five remaining tiles and rotations to discover that none fit in position 5, once it knows that, it doesn't have to go through the remaining four positions. That's 4^{4}4! = 6,144 combinations that it can skip every time it discovers an impossible beginning. That doesn't sound like that much, but if we assume that this happens more often than not, it's still an improvement by orders of magnitude.

We may think of this algorithm as constructing a search tree, but immediately pruning all branches that aren't viable, as close to the root as possible.

### Matches #

Before we get to the algorithm proper we need a few simple helper functions. One kind of function is a predicate that determines if a particular tile can occupy a given position. Since we may place any tile in any rotation in the first position, we don't need to write a predicate for that, but if we wanted to generalize, `const True`

would do.

Whether or not we can place a given tile in the second position depends exclusively on the tile in the first position:

tile2Matches :: Tile -> Tile -> Bool tile2Matches t1 t2 = right t1 `matches` left t2

If the `right`

dog part of the first tile `matches`

the `left`

part of the second tile, the return value is `True`

; otherwise, it's `False`

. Note that I'm using infix notation for `matches`

. I could also have written the function as

tile2Matches :: Tile -> Tile -> Bool tile2Matches t1 t2 = matches (right t1) (left t2)

but it doesn't read as well.

In any case, the corresponding matching functions for the third and forth tile look similar:

tile3Matches :: Tile -> Tile -> Bool tile3Matches t2 t3 = right t2 `matches` left t3 tile4Matches :: Tile -> Tile -> Bool tile4Matches t1 t4 = bottom t1 `matches` top t4

Notice that `tile4Matches`

compares the fourth tile with the first tile rather than the third tile, because position 4 is directly beneath position 1, rather than to the right of position 3 (cf. the grid above). For that reason it also compares the `bottom`

of tile 1 to the `top`

of the fourth tile.

The matcher for the fifth tile is different:

tile5Matches :: Tile -> Tile -> Tile -> Bool tile5Matches t2 t4 t5 = bottom t2 `matches` top t5 && right t4 `matches` left t5

This is the first predicate that depends on two, rather than one, previous tiles. In position 5 we need to examine both the tile in position 2 and the one in position 4.

The same is true for position 6:

tile6Matches :: Tile -> Tile -> Tile -> Bool tile6Matches t3 t5 t6 = bottom t3 `matches` top t6 && right t5 `matches` left t6

but then the matcher for position 7 looks like the predicate for position 4:

tile7Matches :: Tile -> Tile -> Bool tile7Matches t4 t7 = bottom t4 `matches` top t7

This is, of course, because the tile in position 7 only has to consider the tile in position 4. Finally, not surprising, the two remaining predicates look like something we've already seen:

tile8Matches :: Tile -> Tile -> Tile -> Bool tile8Matches t5 t7 t8 = bottom t5 `matches` top t8 && right t7 `matches` left t8 tile9Matches :: Tile -> Tile -> Tile -> Bool tile9Matches t6 t8 t9 = bottom t6 `matches` top t9 && right t8 `matches` left t9

You may suggest that it'd be possible to reduce the number of predicates. After all, there's effectively only three different predicates: One that only looks at the tile to the left, one that only looks at the tile above, and one that looks both to the left and above.

Indeed, I could have boiled it down to just three functions:

matchesHorizontally :: Tile -> Tile -> Bool matchesHorizontally x y = right x `matches` left y matchesVertically :: Tile -> Tile -> Bool matchesVertically x y = bottom x `matches` top y matchesBoth :: Tile -> Tile -> Tile -> Bool matchesBoth x y z = matchesVertically x z && matchesHorizontally y z

but I now run the risk of calling the wrong predicate from my implementation of the algorithm. As you'll see, I'll call each predicate by name at each appropriate step, but if I had only these three functions, there's a risk that I might mistakenly use `matchesHorizontally`

when I should have used `matchesVertically`

, or vice versa. Reducing eight one-liners to three one-liners doesn't really seem to warrant the risk.

### Rotations #

In addition to examining whether a given tile fits in a given position, we also need to be able to rotate any tile:

rotateClockwise :: Tile -> Tile rotateClockwise (Tile t r b l) = Tile l t r b rotateCounterClockwise :: Tile -> Tile rotateCounterClockwise (Tile t r b l) = Tile r b l t upend :: Tile -> Tile upend (Tile t r b l) = Tile b l t r

What is really needed, it turns out, is to enumerate all four rotations of a tile:

rotations :: Tile -> [Tile] rotations t = [t, rotateClockwise t, upend t, rotateCounterClockwise t]

Since this, like everything else here, is a pure function, I experimented with defining a 'memoized tile' type that embedded all four rotations upon creation, so that the algorithm doesn't need to call the `rotations`

function millions of times, but I couldn't measure any discernable performance improvement from it. There's no reason to make things more complicated than they need to be, so I didn't keep that change. (Since I do, however, use Git tactically i did, of course, stash the experiment.)

### Permutations #

While I couldn't make things work by enumerating all 95 billion combinations, enumerating all 362,880 permutations of non-rotated tiles is well within the realm of the possible:

allPermutations :: [(Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)] allPermutations = (\[t1, t2, t3, t4, t5, t6, t7, t8, t9] -> (t1, t2, t3, t4, t5, t6, t7, t8, t9)) <$> permutations tiles

Doing this in GHCi on my old laptop takes 300 milliseconds, which is good enough compared to what comes next.

This list value uses permutations to enumerate all the permutations. You may already have noticed that it converts the result into a nine-tuple. The reason for that is that this enables the algorithm to pattern-match into specific positions without having to resort to the index operator, which is both partial and requires iteration of the list to reach the indexed element. Granted, the list is only nine elements long, and often the algorithm will only need to index to the fourth or fifth element. On the other hand, it's going to do it *a lot*. Perhaps it's a premature optimization, but if it is, it's at least one that makes the code more, rather than less, readable.

### Algorithm #

I found it easiest to begin at the 'bottom' of what is effectively a recursive algorithm, even though I didn't implement it that way. At the 'bottom', I imagine that I'm almost done: That I've found eight tiles that match, and now I only need to examine if I can rotate the final tile so that it matches:

solve9th :: (a, b, c, d, e, Tile, g, Tile, Tile) -> [(a, b, c, d, e, Tile, g, Tile, Tile)] solve9th (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do match <- filter (tile9Matches t6 t8) $ rotations t9 return (t1, t2, t3, t4, t5, t6, t7, t8, match)

Recalling that Haskell functions compose from right to left, the function starts by enumerating the four `rotations`

of the ninth and final tile `t9`

. It then filters those four rotations by the `tile9Matches`

predicate.

The `match`

value is a rotation of `t9`

that matches `t6`

and `t8`

. Whenever `solve9th`

finds such a match, it returns the entire nine-tuple, because the assumption is that the eight first tiles are already valid.

Notice that the function uses `do`

notation in the list monad, so it's quite possible that the first `filter`

expression produces no `match`

. In that case, the second line of code never runs, and instead, the function returns the empty list.

How do we find a tuple where the first eight elements are valid? Well, if we have seven valid tiles, we may consider the eighth and subsequently call `solve9th`

:

solve8th :: (a, b, c, d, Tile, Tile, Tile, Tile, Tile) -> [(a, b, c, d, Tile, Tile, Tile, Tile, Tile)] solve8th (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do match <- filter (tile8Matches t5 t7) $ rotations t8 solve9th (t1, t2, t3, t4, t5, t6, t7, match, t9)

This function looks a lot like `solve9th`

, but it instead enumerates the four `rotations`

of the eighth tile `t8`

and filters with the `tile8Matches`

predicate. Due to the `do`

notation, it'll only call `solve9th`

if it finds a `match`

.

Once more, this function assumes that the first seven tiles are already in a legal constellation. How do we find seven valid tiles? The same way we find eight: By assuming that we have six valid tiles, and then finding the seventh, and so on:

solve7th :: (a, b, c, Tile, Tile, Tile, Tile, Tile, Tile) -> [(a, b, c, Tile, Tile, Tile, Tile, Tile, Tile)] solve7th (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do match <- filter (tile7Matches t4) $ rotations t7 solve8th (t1, t2, t3, t4, t5, t6, match, t8, t9) solve6th :: (a, b, Tile, Tile, Tile, Tile, Tile, Tile, Tile) -> [(a, b, Tile, Tile, Tile, Tile, Tile, Tile, Tile)] solve6th (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do match <- filter (tile6Matches t3 t5) $ rotations t6 solve7th (t1, t2, t3, t4, t5, match, t7, t8, t9) solve5th :: (a, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile) -> [(a, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)] solve5th (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do match <- filter (tile5Matches t2 t4) $ rotations t5 solve6th (t1, t2, t3, t4, match, t6, t7, t8, t9) solve4th :: (Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile) -> [(Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)] solve4th (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do match <- filter (tile4Matches t1) $ rotations t4 solve5th (t1, t2, t3, match, t5, t6, t7, t8, t9) solve3rd :: (Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile) -> [(Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)] solve3rd (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do match <- filter (tile3Matches t2) $ rotations t3 solve4th (t1, t2, match, t4, t5, t6, t7, t8, t9) solve2nd :: (Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile) -> [(Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)] solve2nd (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do match <- filter (tile2Matches t1) $ rotations t2 solve3rd (t1, match, t3, t4, t5, t6, t7, t8, t9)

You'll observe that `solve7th`

down to `solve2nd`

are very similar. The only things that really vary are the predicates, and the positions of the tile being examined, as well as its neighbours. Clearly I can generalize this code, but I'm not sure it's worth it. I wrote a few of these in the order I've presented them here, because it helped me think the problem through, and to be honest, once I had two or three of them, GitHub Copilot picked up on the pattern and wrote the remaining functions for me.

Granted, typing isn't a programming bottleneck, so we should rather ask if this kind of duplication looks like a maintenance problem. Given that this is a one-time exercise, I'll just leave it be and move on.

Particularly, if you're struggling to understand how this implements the 'truncated search tree', keep in mind that e..g `solve5th`

is likely to produce no valid `match`

, in which case it'll never call `solve6th`

. The same may happen in `solve6th`

, etc.

The 'top' function is a bit different because it doesn't need to `filter`

anything:

solve1st :: (Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile) -> [(Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)] solve1st (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do match <- rotations t1 solve2nd (match, t2, t3, t4, t5, t6, t7, t8, t9)

In the first position, any tile in any rotation is legal, so `solve1st`

only enumerates all four `rotations`

of `t1`

and calls `solve2nd`

for each.

The final step is to compose `allPermutations`

with `solve1st`

:

solutions :: [(Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)] solutions = allPermutations >>= solve1st

Running this in GHCi on my 4½-year old laptop produces all 16 solutions in approximately 22 seconds.

### Evaluation #

Is that good performance? Well, it turns out that it's possible to substantially improve on the situation. As I've mentioned a couple of times, so far I've been running the program from GHCi, the Haskell REPL. Most of the 22 seconds are spent interpreting or compiling the code.

If I compile the code with some optimizations turned on, the executable runs in approximately 300 ms. That seems quite decent, if I may say so.

I can think of a few tweaks to the code that might conceivably improve things even more, but when I test, there's no discernable difference. Thus, I'll keep the code as shown here.

Here's one of the solutions:

The information on the box claims that there's two solutions. Why does the code shown here produce 16 solutions?

There's a good explanation for that. Recall that two of the tiles are identical. In the above solution picture, it's tile 1 and 3, although they're rotated 90° in relation to each other. This implies that you could take tile 1, rotate it counter-clockwise and put it in position 3, while simultaneously taking tile 3, rotating it clockwise, and putting it in position 1. Visually, you can't tell the difference, so they don't count as two distinct solutions. The algorithm, however, doesn't make that distinction, so it enumerates what is effectively the same solution twice.

Not surprising, it turns out that all 16 solutions are doublets in that way. We can confirm that by evaluating `length $ nub solutions`

, which returns `8`

.

Eight solutions are, however, still four times more than two. Can you figure out what's going on?

The algorithm also enumerates four rotations of each solution. Once we take this into account, there's only two visually distinct solutions left. One of them is shown above. I also have a picture of the other one, but I'm not going to totally spoil things for you.

### Conclusion #

When I was eight, I might have had the time and the patience to actually lay the puzzle. Despite the incredibly bad odds, I vaguely remember finally solving it. There must be some more holistic processing going on in the brain, if even a kid can solve the puzzle, because it seems inconceivable that it should be done as described here.

Today, I don't care for that kind of puzzle in analog form, but I did, on the other hand, find it an interesting programming exercise.

The code could be smaller, but I like it as it is. While a bit on the verbose side, I think that it communicates well what's going on.

I was pleasantly surprised that I managed to get execution time down to 300 ms. I'd honestly not expected that when I started.

## Comments

Thanks for a nice blog post! I found the challange interesting, so I have written my own version of the code that both tries to be faster and also remove the redundant solutions, so it only generates two solutions in total. The code is available here. It executes in roughly 8 milliseconds both in ghci and compiled (and takes a second to compile and run using runghc) on my laptop.

In order to improve the performance, I start with a blank grid and one-by-one add tiles until it is no longer possible to do so, and then bactrack, kind of like how you would do it by hand. As a tiny bonus, that I haven't actually measured if it makes any practical difference, I also selected the order of filling in the grid so that they can constrain each other as much as possible, by filling 2-by-2 squares as early as possible. I have however calculated the number of boards explored in each of the two variations. With a spiral order, 6852 boards are explored, while with a linear order, 9332 boards are explored.

In order to eliminate rotational symmetry, I start by filling the center square and fixing its rotation, rather than trying all rotations for it, since we could view any initial rotation of the center square as equivalent to rotating the whole board. In order to eliminate the identical solutions from the two identical tiles, I changed the encoding to use a number next to the tile to say how many copies are left of it, so when we choose a tile, there is only a single way to choose each tile, even if there are multiple copies of it. Both of these would also in theory make the code slightly faster if the time wasn't already dominated by general IO and other unrelated things.

I also added various pretty printing and tracing utilites to the code, so you can see exactly how it executes and which partial solutions it explores.

Thank you for writing. I did try filling the two-by-two square first, as you suggest, but in isolation it makes no discernable difference.

I haven't tried your two other optimizations. The one to eliminate rotations should, I guess, reduce the search space to a fourth of mine, unless I'm mistaken. That would reduce my 300 ms to approximately 75 ms.

I can't easily guess how much time the other optimization shaves off, but it could be the one that makes the bigger difference.