## 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.