“Fifteenth Puzzle” Series: core with F#

In this part of the series I will show you how I modeled the puzzle into data-representations and how I implemented this in F#.

The representation is straight forward. I want to stay flexible so I don’t fix the dimension of the board. That has the disadvantage that I have remember or calculate the dimension but this is no big deal as currying and OOP are both here for our convenience.

To identify the places on the board I either use an index (flat-representation) in the usual left-to-right and top-to-bottom enumeration – or I use a tuple with the first item being the row-number and the second counting the columns (I will create a type-abbreviation Coordinate for this). Look at the following sketch for some visual clues as how to correlated both:


A tile on the puzzle is identified just by it’s number – 1 to dim^2-1 – and the empty tile by the number dim^2. We will use Tile as a type-abbreviation for this.

Finally I will add two more abbreviations to identify the puzzle-content either in flat-view (Tiles) or in “2D”-representation (PuzzleState – this will be an array of arrays. The outer ones being the rows and each row consisting of the tiles in it, so that you can index such a state with .[row].[column])

So let’s start a new VS2010 solution calling it Puzzle. Next we add a F#-Silverlight library named Puzzle.Core to it and choose Silverlight 4 when asked for the target version. I remove the script, rename the source file into just core.fs and begin the file with a nice namespace and our representations:

namespace Puzzle.Core

open System

type Coordinate  = int*int
type Tile        = int
type Tiles       = Tile array
type PuzzleState = (Tile array) array

We are going to need some function to calculate the dimension for the coordinate-representation. That’s straight forward (just the length of the row-array) but let’s warp this in a function anyway – it’s shorter and we will be able to read it Zwinkerndes Smiley

    let dim (state : PuzzleState) = Array.length state

Let’s go on and think just a moment on how to translate between indizes and coordinates. Looking again at the sketch above you might see that we have the following mapping between them:

index = dim * row + column

This is the immediate consequence of the way we are enumerating the cells (remember: left-to-right and top-to-bottom).

Now this of course is just the infamous division with reminder (as column will be non-negative and smaller than the dimension) and it’s easy to get the conversion functions:

let index2coord (dim : int) (ind : int) : Coordinate
     = ( ind / dim, ind % dim )

let coord2index (dim : int) 1)r,c) : Coordinate) : int
      = r*dim + c

Next we will need functions to get the current tile-numbers of a game state and to check for the empty ...continue

As you can see this uses a couple of helper functions I will show you next. But you might wonder why I don’t put those inside this one as sub-functions? Well I could but it’s getting a mess really quickly (you just cannot read this) – and on this blog it’s even worse.

Here you go:

    /// given a coordinate gets all surrounding coordinates
    /// this will be used to find the empty cell's coordinates
    /// if the user clicks on a tile
    let getSurrounding (dim : int) 2)r,c) : Coordinate) : Coordinate list =
        /// checks if a coordinate is inside the puzzle
        let isCoordInField (dim : int) ((r,c) : ...continue

That’s it for today – next we will have a look at how to check if you can solve a given state and of course if it’s already solved Smiley mit geöffnetem Mund

References   [ + ]

1. r,c) : Coordinate) : int = r*dim + c

Next we will need functions to get the current tile-numbers of a game state and to check for the empty tile as it will play a major role:

    /// get the tile-number of a PuzzleState by a coordinate
    let getTile (state : PuzzleState) ((row,col) : Coordinate) : Tile
        = state.[ row ].[ col ]

    /// the empty tile will have the square of dim
    let emptyTile (dim : int) : Tile
        = dim*dim

    /// checks if the tile at the given coordinate is empty
    /// by comparing the number with the number of the empty tile
    let isCoordEmpty (state : PuzzleState) ((r,c) : Coordinate) : bool
        = getTile state (r,c) = emptyTile (dim state)

    /// finds the coordinate of the empty tile using isCoordEmpty
    /// fails if there is not exaclty one position with an empty tile
    let emptyCoord (state : PuzzleState) : Coordinate
        = let dim = dim state
          let coords
              = [ for r in [0..dim-1] do
                  for c in [0..dim-1] do
                  yield (r,c)
                ] |> List.filter (isCoordEmpty state)
          match coords with
          | [x] -> x
          | _   -> failwith "multiple or no empty tiles found"

Now we want to be able to move tiles around. But of course only if can indeed move them. Which is the case when they are directly next to the empty cell. We will use a pure function that translates a puzzle-state into another (moving the tile or not if it was not beside the empty cell):

    let moveTileAt (state : PuzzleState) ((r,c) : Coordinate) : PuzzleState =
        match emptyTileFrom state (r,c) with
        | None         -> state
        | Some (r',c') -> switchTiles state ((r,c),(r',c'
2. r,c) : Coordinate) : Coordinate list = /// checks if a coordinate is inside the puzzle let isCoordInField (dim : int) ((r,c) : Coordinate) : bool = r >= 0 && c >= 0 && r < dim && c < dim [ (r-1,c); (r+1,c); (r,c-1);(r,c+1) ] |> List.filter (isCoordInField dim) /// uses getSurrounding to find the coordinates /// of the empty cell if it's in the surroundings /// of the given coordinate - if not the function /// will return None - indicating that the let emptyTileFrom (state : PuzzleState) ((r,c) : Coordinate) : Coordinate option = let dim = dim state getSurrounding dim (r,c) |> List.tryFind (fun coord -> coord = emptyCoord state) /// switches two tiles by their coordinates let switchTiles (state : PuzzleState) ((r,c) : Coordinate, (r',c') : Coordinate) : PuzzleState = let dim = dim state let switch = function | (x,y) when x = r && y = c -> (r',c') | (x,y) when x = r' && y = c' -> (r,c) | _ as c -> c Array.init dim (fun x -> Array.init dim (fun y -> (x,y) |> switch |> getTile state