“Fifteenth Puzzle” Series: is it solvable

Previously we talked about the representations in F#.

In this part of the series I will explain how you can check if a given puzzle is solvable and how we can generate random puzzles that are solvable.

Of course you could try and let the computer solve the thing (a feat that is interesting in it’s own right) but if you only want a yes/no answer – as we do – there is a easier way which incorporates a often used nice technique in math: we look for a feature or number we can easily calculate for a given puzzle-state that will not change if we do a move.

Now how could that possible help? Well as we want to get to the solved state, where every tile is on it’s index (tile with number 1 on index 0, number 2 on 1, etc.) and because we can invert every move this feature must be the same on our given puzzle-state as it is on the solved puzzle if we can solve it.

Now what could that feature be? Well to be honest I will just go on and present this feature to you without saying how you could ever possible think of it (because I don’t know as I just read about it – after seeing it you might have some idea but as it’s often in math and puzzles – the solution is easy once you see it but finding it is the hard part).

So let’s get to it:

Finding our feature

First a little warning: for what comes you should always think of the empty-cell in the bottom-right position for reasons that will be clear below.

Let’s look at the tiles in the order I used in the first part I used there for the flat-representation (left-to-right, top-to-bottom). What we are going to need is this: Looking at a tile with number T search count all tiles after (in the left-to-right, top-to-bottom order) this one that have a number smaller than T. (In the solved puzzle this number will always be 0) – we will just call this number “Rank violations of T” or shorter RV( T ). Now take all of those numbers, sum then up and check if the number is even – we will call this just the “solvable feat of Puzzle P” ( Solvable( P )) as obviously this feature will be even for the solved and therefore for all solvable puzzles. Caution: We will not consider the empty cell at all for this (not think of it as having number 16 for now)!

So we could write for a Puzzle P:  Solvable( P ) = \sum_{T \in P} RV( T ) == 0 (mod 2) .

For example look at this:

PuzzleSample

After 10 there are 5, 1, 3, 8, 4, 9, 6, 2, 7 – all smaller so RV(10) = 9. Similar RV(13) = Nr \{ 5, 11, 1, 3, 12, 8, 4, 9, 6, 2, 7 \} = 11 and RV(5) = 4, … We finally get  Solvable(P) = 9 + 11 + 4 + 8 + 0 + 1 + 6 + 4 + 1 + 3 + 3 + 1 + 0 + 1 + 0 = 52 = 0 (mod 2) and so yes this will be solvable.

Before we write this into a F# algorithm let me explain why this will work.

Why is this invariant under the moves?

First if we start and end in a configuration where the empty cell is at the bottom-right we have to make an even count of moves both in the horizontal and vertical direction. Because for every step we move “up” we have to move “down” again (same with “left” – “right”) to end up in the same situation (This will be why we will move a puzzle first in this situation with the empty cell bottom-right in our code!). This is the first part of it: the number of moves in the vertical-direction are even!

Now if we make a move in the horizontal direction – either left or right – this number will not change our numbers as we don’t consider the empty-cell!

The case where we move in the vertical direction is a bit harder. What this does is: it moves a tile n := dim-1 places up or down in our ordering. So their will be as many tiles more that are now in front or behind or moving tile. Now let’s look at those tiles (naming them  t_{1} .. t_{n} ). For each one (t_i) we either have that the number on it is smaller or bigger than the number we moved. In the first case our moved tiles RV is one greater (if we moved it up) or one smaller (if we moved it down) for each one of those – in the second case it stays the same. But what’s with those t_i? Well in the first case their RV stays the same but in the second case their RV got one smaller (if we moved the tile before them) or one greater (if we moved the tile after them).

Look at the 9 here:

PuzzleSampleMoveBefore

we will move it up so we have to consider 3, 12 and 4:

PuzzleSampleMoveAfter

4 and 3 where smaller so their RV stays the same but 9’s got 2 bigger because of them. 12 is bigger so 9’s RV don’t change but 12’s RV got 1 smaller.

Let’s call the number of tiles smaller than over moved one k (so of course the number of tiles bigger than the moved one must be  dim-1-k) then if we move the tile up we get the net change (as we have just seen) to be

1*k+(-1)*(dim-1-k)=2*k-(dim-1)

and a similar formula if we move below:

 -1 * k + 1 * (dim-1-k) = -2*k + (dim-1)

and you see that both numbers “evenness” only depends on whether dim-1 is even or odd!

That’s it – that’s our price. We make a even number of moves and every time we move it our sum only changes by a ever or odd number but it’s always even or always odd. Therefore in total it will have to be a even change and so solvable( P ) stays the same.

Wow – I hope you could understand all this (reading my not so perfect English) – make sure to let me know if you have problems or see any!

Implementing this in F#

First let’s see how we can decide if the puzzle is solved already. Well if we flatten the puzzle first we just have to compare it to the range 1,2,…16:

    let flattenPuzzle (state : PuzzleState) : Tiles
        = state |> Array.concat

    let isSolved (state : PuzzleState) : bool
        = let dim = dim state
          let flat = flattenPuzzle state
          [| 1..dim*dim |] = flat

Now to decide if a puzzle-state is solvable we need a helper to move the empty tile in the bottom-right position (as mentioned above) – for this we just move the empty cell first to the right and then to the bottom:

    let moveToStdConf (state : PuzzleState) : PuzzleState =
        let dim = dim state
        let (r,c)    = emptyCoord state
        let state'   = 1
                       |> List.map (fun c -> (r,c))
                       |> List.fold moveTileAt state
        let state''  = [r+1..dim-1]
                       |> List.map (fun r -> (r, dim-1))
                       |> List.fold moveTileAt state'
        state''

Then of course we have to compute the number of total RV’s as we have seen. This function will do so (for a flattened representation) just the way I explained it in a nice recursive way:

    let getRankViolations (tiles : Tile array) : int
        = let rec countSmaller v fs =
            match fs with
            | [] -> 0
            | x::fs' when x < v -> 1+countSmaller v fs'
            | _::fs' -> countSmaller v fs'
          let foldFun v (sum, fs) =
            let sum' = sum + countSmaller v fs
            let fs' = v::fs
            (sum', fs')
          Array.foldBack foldFun tiles (0, [])
          |> fst

And now it’s a piece of cake to determine if a puzzle-state is solvable – first move the empty cell to the bottom-right position, flatten this, compute the number of RV’s and then check if this is even:

    let isEven (n : int) : bool
        = n % 2 = 0

    let isFlatConfigSolvable : Tiles -> bool
        = getRankViolations >> isEven

    let isSolveable (state : PuzzleState) : bool =
        moveToStdConf state
        |> flattenPuzzle
        |> isFlatConfigSolvable

That’s it.

Creating random and solvable puzzles

The idea is simple – if you look at our reasoning you will see that you can switch a puzzle from solvable to not-solvable just by switching a pair of consecutive tiles – let’s say the first ones. Our algorithm will simply create a random configuration of tiles, check if this is solvable and if not switch a direct pair of tiles.

But first a helper that makes a puzzle-state from a flattened representation:

    let initTiles (tiles : Tiles) : PuzzleState
        = let maxDim = tiles |> (int << Math.Sqrt << double << Array.length)
          let maps = tiles   |> Array.mapi( fun i v -> (index2coord maxDim i),v) |> Map.ofArray
          Array.init maxDim (fun r -> Array.init maxDim (fun c -> maps.[r,c]))

This one just get’s the dimension from the length of the array (as the puzzle is quadratic it’s just the square root) and just initializes the state using the transform-mappings we introduced in the last article.

The rest is just switching a couple (let’s say dim*dim) of random pairs making sure not to change the empty cell (by just adding it just after the random shuffling) – I think the code tells more than a thousand words Zwinkerndes Smiley :

    let initRandom (dim : int) : PuzzleState
        = let rnd         = new Random(int DateTime.Now.Ticks)
          let rndIndex () = rnd.Next(0, dim*dim - 1)
          let rndPair ()  = (rndIndex(), rndIndex())
          let values      = [| 1..dim*dim - 1 |]
          let switch (vs : int[]) (i, j) =
              let t = vs.[i]
              vs.[i] <- vs.[j]
              vs.[j] <- t
          [1..dim*dim]    |> List.iter (fun _ -> rndPair() |>  switch values)
          let complete    = Array.append values [| dim*dim |]
          if complete |> isFlatConfigSolvable |> not then switch complete (0,1)
          complete |> initTiles

Ok let’s wrap up this lengthy post for now. Next time we will wrap this all up.