Archive

Archive for August, 2010

A sudoku solver in C#

How would the sudoku solver from the previous posted look like if implemented in C# you might wonder? Would the code be clumsy and verbose? I tried it out and I would say the old work horse does a pretty good job. Using goodies like linq, lambda expressions, generics and extension methods it is possible to keep the code compact and clear.

As with F# I needed a few helper functions when working with 2d-arrays. I packaged the utilities as extension methods which enables a natural syntax. The class is called Array2D and the methods are EnumerateBy, Enumerate, Transform, Transformi, Init, Show, GetRow, GetColumn and SubArray. The code is about 90 lines so I will not post it here like I did with the corresponding F# code. Also the code is straight forward and not that interesting.

Instead, let’s move forward. The rest of the code is packaged into two classes; Solution and Solver. The solver is quite thin; in fact the entire source code fits well in here:

class Solver

{

    public static Solution Solve(Solution roSolution)

    {

        var solution = new Solution(roSolution);

        solution.Reduce();

        if (solution.IsInvalid)

            return null;

        else if (solution.IsUnique)

            return solution;

        else

            return solution.Expand().Select(x => Solve(x)).SkipWhile(x => x == null).FirstOrDefault();

    }

}

 

We recognize the backtrack search from the F# implementation. First call the iterative step (this time called Solution.Reduce, previously called iterativeSolve) and depending on the outcome;

  • either return null, if the solution is invalid,
  • or return the result if the solution is unique
  • or else continue searching by expanding the least ambiguous cell

The rest of the code is contained within the solution class. Like in F# the game plan is stored as a 9×9 array where each cell contains a sets of integers, representing the possible values.

class Solution

{

    private HashSet<int>[,] values;

 

    // …

}

 

The Solution.Reduce method applies Solution.SolveCell for each cell in the game plan until nothing changes.

public void Reduce()

{

    bool modified;

    do

    {

        var newValues = values.Transformi((v, r, c) => v.Count > 1 ? SolveCell(r, c) : v);

        if (modified = !AreEqual(newValues, values))

            values = newValues;

    } while (modified);

}

 

Not much to add here except that I wanted to try out the new StructuralComparisons.StructuralEqualityComparer in .net 4 for comparing two 2d-arrays of sets but I failed. At a glance it seemed to be exactly what I wanted but it did no do the “right thing” so I wrote a helper method instead. Hmm, I need to look more into that some day.

Anyway, I am a little proud of the Solution.SolveCell so I just dump it here:

private HashSet<int> SolveCell(int r, int c)

{

    var row = SelectRow(r);

    var column = SelectColumn(c);

    var block = SelectBlock(r, c);

    var solution = values[r, c].Where(v => !row.Contains(v))

                                .Where(v => !column.Contains(v))

                                .Where(v => !block.Contains(v));

    return new HashSet<int>(solution);

}

 

Just as compact as the F# equivalent. Linq is really a useful thing when trying to write compact but yet readable code. Ofcourse Solution.Expand (called unfold in the F# code) also benefits from linq:

public List<Solution> Expand()

{

    // Find least ambiguous cell

    var lac = values.EnumerateBy((s, r, c) => new { Count = s.Count, Row = r, Column = c })

                    .Where(x => x.Count > 1)

                    .OrderBy(x => x.Count)

                    .First();

 

    // Expand

    var result = new List<Solution>();

    foreach (int v in values[lac.Row, lac.Column])

    {

        var solution = new Solution(this);

        solution.values[lac.Row, lac.Column] = Singleton(v);

        result.Add(solution);

    }

    return result;

}

 

As I said in the beginning I think C# does a pretty good job (even though I have to admit I spent more time on the C# code so the comparsion might not be entirely fair). The code is compact and clear and not far behind F#. One thing I was really missing, though, was the brilliant 2d-array slicing syntax. Let’s just repeat it here once more:

module Array2D

    let getRow (arr : ‘a[,]) r = arr.[r..r,*] 

    let getColumn (arr : ‘a[,]) c = arr.[*,c..c]

    let getGroup (arr : ‘a[,]) gc gr size=

        let r = gr * size

        let c = gc * size

        arr.[r..r+size-1,c..c+size-1]

 

It is just a detail but such a lovely detail indeed.

Oups, I almost forgot; you can download the entire source here. This time, however, without any fancy (oh, well…) wpf user interface.

Categories: Uncategorized

Carmenta Engine 5, First contact

The release of CE 5 is getting closer and just recently Carmenta Engine 5 RC 1 was announced. A lot of things have been reworked and improved – to say the least. As a first experiment I sat down and wrote a very basic “hello world” kind of application. Using the brand new WPF map control the user interface can be defined as simple as:

<Window x:Class="CE5TestApp.MainWindow"

       xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation&quot;

       xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml&quot;

       xmlns:local="clr-namespace:CE5TestApp"

       xmlns:cectrl="clr-namespace:Carmenta.Engine.Controls;assembly=CEControls.Dotnet"

       Title="MainWindow" Height="350" Width="525">  

    <Grid>

        <cectrl:MapControl View="{local:ViewFactory ConfigurationFile=testmap.px, ViewName=View0}"/>

    </Grid>

</Window>

 

The map control has a view property which is the only thing that must be set. The WPF sample in the documentation suggests, hooking up the Window.Loaded event and then setting the property from code. I am, however, more of a declarative programmer kind of guy so I wrote a MarkupExtension called ViewFactory that loads a configuration from file and retrieves the specified view. Here is the implemenation:

[MarkupExtensionReturnType(typeof(View))]

public class ViewFactory : MarkupExtension

{

    public string ConfigurationFile { get; set; }

 

    public string ViewName { get; set; }

 

    public override object ProvideValue(IServiceProvider serviceProvider)

    {

        if (!Runtime.IsInitialized)

            Runtime.Initialize();

 

        View result = null;

        if (ConfigurationFile != null && File.Exists(ConfigurationFile) && ViewName != null)

        {

            var config = new Configuration(ConfigurationFile);

            result = (View)config.GetPublicObject(ViewName);

        }

 

        return result;

    }

}

 

Nice. The only cloud on the sky was that I got this error message at first.

runtimeproblem 

It was easily fixed though, by adding the following snippet to the app.config:

<startup useLegacyV2RuntimeActivationPolicy="true">

  <supportedRuntime version="v4.0"/>

</startup>

 

The last thing I did was to add support for zooming and panning. Like before, this kind of map interaction, is handled by tools. The tool interface has been totally redesigned though; abstracting away low-level details. More over, instead of providing a flora of different tools a multi-tool called StandardTool is provided. I think this makes good sense. Well, lets get down to business and modify the application to use the standard tool. First we need to add a new namespace declaration to the xaml:

xmlns:ce="clr-namespace:Carmenta.Engine;assembly=CECore.Dotnet"

 

and then we simply set the tool property:

<cectrl:MapControl View="{local:ViewFactory ConfigurationFile=testmap.px, ViewName=View0}">

    <cectrl:MapControl.Tool>

        <ce:StandardTool/>

    </cectrl:MapControl.Tool>

</cectrl:MapControl>

 

All done. I am looking forward to try out more of CE5. It is clear that this is a major upgrade and that programming maps have become easier and more fun.

Categories: Uncategorized

A sudoku solver in F#

I have never really enjoyed solving sudokus by hand. The reason for this, I think, is that it is so mechanical. It’s all about applying an algorithm, which is something that computers are very good at and humans, well humans should write programs instead… 🙂

Yesterday, I was challanged by the Project Euler, to create – thats right – a sudoku solver. Normally, I do not write about my solutions since the fun of the Project Euler is to find your own solutions and the solutions are, well not that useful really, once they are found out. Sudokus, however, are well known outside the domain of the Project Euler. Thus, here we are.

The solver stores the game state in a two dimensional array. Each array element contains a set of integers representing the possible values for that cell.

type Solution = Set<int>[,]

The two dimensional array turned out to be a good choice due to the elegant support for slicing. I ended up extending the Array2D module as shown below:

module Array2D

    // ref: http://cs.hubfs.net/forums/thread/14066.aspx

    let getRow (arr : ‘a[,]) r = arr.[r..r,*] 

    let getColumn (arr : ‘a[,]) c = arr.[*,c..c]

    let getGroup (arr : ‘a[,]) gc gr size=

        let r = gr * size

        let c = gc * size

        arr.[r..r+size-1,c..c+size-1]

    let enumerateBy (f : int -> int -> ‘a -> ‘b) (arr : ‘a[,]) =

        seq {

            let rc = Array2D.length1 arr

            let cc = Array2D.length2 arr

            for r in 0..rc-1 do

                for c in 0..cc-1 do

                    yield f r c arr.[r,c]

        }

    let enumerate (arr : ‘a[,]) =

        enumerateBy (fun r c v -> v) arr

    let enumeratei (arr : ‘a[,]) =

        enumerateBy (fun r c v -> v,(r,c)) arr

 

The algorithm then consists of two separate parts. One part is the iterative that can solve the simplest class of sudokus and by such I mean sudokus that do not require guessing.

let solveCell a c r =

    let filterByRow s = Set.difference s (selectRow a r)

    let filterByColumn s = Set.difference s (selectColumn a c)

    let filterByGroup s = Set.difference s (selectGroup a (c/3) (r/3))

    a.[r,c] |>   

    filterByRow |>

    filterByColumn |>

    filterByGroup

 

let iterateSolve (arr : Solution) =

    let updateSingleCell (a : Solution) c r =

        let prev = a.[r,c]

        a.[r,c] <- solveCell a c r

        prev <> a.[r,c]

    let updateAllCells (arr : Solution) =

        Array2D.enumeratei arr |>

        Seq.filter (fun (s,_) -> s.Count > 1) |>

        Seq.fold (fun st (_,(r,c)) -> let changed = updateSingleCell arr c r in st || changed) false 

    let arr’ = Array2D.copy arr

    while updateAllCells arr’ do ()

    arr’

 

SelectRow, SelectColumn and SelectGroup are thin wrappers around Array2D.getRow, Array2D.getColumn and Array2D.getGroup. The second part of the algorithm handles the guessing by implementing back tracking. Here we go:

let rec backTrackSearch (f : ‘a -> ‘a list) (initial : ‘a) =

    match f initial with

    | [] -> None

    | [solution] -> Some solution

    | solutions ->

        solutions |>

        Seq.map (backTrackSearch f) |>

        Seq.tryPick (fun x -> x)

 

let solve (s : Solution) =

    let unfold (arr : Solution) : Solution list =

        let cells = Array2D.enumerateBy (fun r c (s : Set<int>) -> s.Count,(r,c)) arr

        if Seq.tryFind (fun (count,_) -> count = 0) cells |> Option.isSome then

            []

        elif Seq.forall (fun (count,_) -> count = 1) cells then

            [arr]

        else

            [ let (_,(r,c)) = cells |> Seq.filter (fun (count,_) -> count > 1) |> Seq.minBy fst

              for candidate in arr.[r,c] do 

                 let arr’ = Array2D.copy arr

                 arr’.[r,c] <- Set.singleton candidate

                 yield arr’ ]

    backTrackSearch (iterateSolve>>unfold) s

 

That is actually all there is to it. I was surprised by how little code that was actually needed for a efficient sudoku solver. To make it more useful I also added a very simple WPF based user interface.

sodukusolver 

The entire source code can be downloaded here.

Categories: Uncategorized

Monads

I have been playing with monads (a.k.a. computation expressions or workflows in F#) a bit lately. From wikipedia we can learn, among other things, that:

“In functional programming, a monad is a kind of abstract data type constructor used to represent computations (instead of data in the domain model). Monads allow the programmer to chain actions together to build a pipeline, in which each action is decorated with additional processing rules provided by the monad. ”

Monads is indeed nothing new and Haskell programmers have been using them for years but I have not really taken the time to dig into the theory before. I should also add that this blog entry does not claim to be unique (or even creative) and all the material provided here are also available at many places. A couple of good links that I have been reading are:

I lift my hat of and say “thank you” to the great programmers behind.

Anyway, the simplest monad of them all is the the maybe monad. The maybe monad is useful when chaining function calls that may fail or return nothing. Take a deep breath, here is one possible F# definition:

type MaybeMonad() =

    member b.Return(x) = Some x

    member b.Bind(m, f) =

        match m with

        | None -> None

        | Some x -> f x

 

let maybe = MaybeMonad()

 

A sample usage may look like:

let failIfBig n = if n > 1000 then None else (Some n)

 

let safesum inp1 inp2 =

    maybe { let! n1 = failIfBig inp1

            let! n2 = failIfBig inp2

            let sum = n1 + n2

            return sum }

 

printf "%A\n" (safesum 10 20)

printf "%A\n" (safesum 10000 20)

 

The safesum function uses a special “workflow” syntax which is translated by the compiler to (something like):

let safesum’ inp1 inp2 =

    maybe.Bind(failIfBig inp1, fun n1 ->

        maybe.Bind(failIfBig inp2, fun n2 ->

            let sum = n1 + n2

            maybe.Return(sum)))

 

My next step was to grok the state monad. The state monad is useful for hiding a state parameter that is “threaded” through a computation. Take another deep breath – here comes a possible state monad definition (again using F# ofcourse):

type StateMonad() =

    member this.Return(a) = fun s -> a,s

    member this.Bind(m, f) = fun s0 ->

                                let a,s = m s0

                                let m’ = f a

                                m’ s

 

let state = StateMonad()

 

Along with the monad, it is common to provide the following helpers:

let getState = fun s -> s,s

let setState s = fun _ -> (),s

let execute m s0 = m s0 |> fst

 

A sample usage may look like this:

type BinTree<‘a> = Leaf of ‘a | Node of BinTree<‘a>*BinTree<‘a>

 

let rec labelTree t =

    state {

        match t with

        | Leaf x ->

            let! s = getState

            do! setState (s+1)

            return Leaf (x,s)

        | Node (l,r) ->

            let! l’ = labelTree l

            let! r’ = labelTree r

            return Node (l’,r’)

    }

 

 

let sampleTree =

    Node(

        Node(Leaf "a", Leaf "b"),

        Leaf "c")

 

execute (labelTree sampleTree) 0 |> printf "%A\n"

 

Using the state monad is, as shown above, not that hard. Understanding the magic behind requires more thought.

Categories: Uncategorized