Home > Uncategorized > A sudoku solver in C#

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.

Advertisements
Categories: Uncategorized
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: