This time in our quest to solve the most annoying puzzles from adventure games we will travel to 221B Baker Street in Victorian London, as Sherlock Holmes unearths a locked box from a grave in The Testament of Sherlock Holmes

The lock mechanism consists of a sort of sliding puzzle, but this time the tiles move in pairs. Rather than explaining it, it’s easier to just see it in action.

Our first approach will be to use our breadth-first search implementation, so we’ll need the same functions we coded for the sliding tiles puzzle. Again, we need both a initial and a solution state:

(def start [[0 0 0 0 0 0 0 0 0]
            [2 6 3 7 5 4 4 8 0]
            [0 0 0 0 0 0 0 0 0]])

(def end   [[0 0 0 0 0 0 0 0 0]
            [7 8 2 3 5 4 6 4 0]
            [0 0 0 0 0 0 0 0 0]])

And a way to check if we are in a solution state:

#{end}

We also need a possible-next-states function. Again, I’ll be using some helper functions that you can look up in the full repo, but the core is pretty much similar to the one for the sliding puzzle:

(defn possible-next-steps [puzzle]
  (for [move '([-1 0] [1 0] [0 1] [0 -1])
        pair (pairs puzzle)
        :let [from (pair-cells pair)
              to (pair-cells (new-pair pair move))]
        :when (valid-move? puzzle from to)]
    (move-cells puzzle from to)))

Great, now we can use our breath first searcher to do the heavy lifting:

(bfser/solve start #{end} possible-next-steps)

We must be patient because this takes a long time. In fact, it takes such a long time that I got tired of waiting before it came to a solution. Maybe Sherlock won’t be able to open the box just yet, but he shouldn’t despair, next time we’ll be looking at a more efficient way of approaching the problem.