Converting Sudoku Solver from Excel to C#

Introduction

I was interested by your article, January 1, on converting a Sudoku program from VB.Net and WinForms to C# and WPF http://www.codeproject.com/Articles/855699/Complete-Sudoku-Game-in-Csharp-WPF-Silverlight as I made a somewhat similar, but perhaps more extreme, conversion a couple of years ago. Before I started I had no experience with C# or WPF – I had not even heard of them and my experience with object oriented programming extended no further than creating simple controls in Visual Basic for Excel. I hope that my experiences will persuade others that learning C# is not as daunting as it at first appears. In fact, like going for a long run, the hardest part is actually deciding to start.

Background

When I first learnt about Sudoku I thought it would be an interesting challenge to automate a solution on the computer. Since my only recent programming was using Visual Basic to write Excel macros I decided to use Excel as the front end and write all the code in VB. This worked very well but then I got too ambitious for these tools. I’d seen other Sudoku problems with different geometries, like Samurai, and I wanted to be able to handle these. This was not too difficult but I decided I needed a solver that would handle any Sudoku problem whatever the size or geometry or type of characters.

My VB code held all variables in global arrays and it became a nightmare to re-dimension these for different problems and even then it was not general enough. I needed a more powerful programming language and somehow I needed to move away from Excel as the front end as this required manually redrawing each new geometry. I decided to switch to C# for no better reason than my computer literate son in law recommended this to me as I discussed the problem with him on a ski lift in Tignes. This was a momentous event so I remember it well but I subsequently learnt that he did all his programming in C and had never actually used C# (he was going to be my mentor!). I used WPF instead of WinForms simply because I didn’t know I had a choice. Both decisions were ultimately extremely fortuitous and I continue to be impressed by the power and flexibility of this combination of tools.

Before Excel and VB I used to code in Fortran IV (mainly scientific computing in Nuclear Engineering back in the 1970s) so my prejudice was to create large shared arrays – something I found very difficult, maybe even impossible, in C#. It was only after many frustrated attempts at creating variably dimensioned global arrays that I started to understand the concept of classes and life became simpler.

Use Of Classes

I have a class called "Cell" which stores the detail of each little box in the problem, detail such as what possibilities are still available and what larger structures "Shapes" this Cell is a part of. I have a class called "Shape" which is roughly the same as the Rows, Columns and Boxes that I see in several other Sudoku programs, although somewhat more general. My definition of a Shape is any collection of one or more, not necessarily contiguous, Cells. A Sudoku Shape always has the same number of Cells equal to the number of unknowns in the problem and also has the rule that the solution in each of these Cells must be different. Different types of Shapes are used for Killer problems.

The coding for the Cell class and Shape class is included below.

/// <summary>
/// Records all detail associated with a single Cell
/// including reference to all Shapes containing this Cell
/// </summary>
public class Cell
{
    /*
     * Records all detail associated with a single Cell
     *  including reference to all Shapes containing this Cell
     * Calls are:
     *      Add(Tag)                            Creates a new, unsolved, Cell with identifier Tag
     *      AddShape(ShapeNum)                  Add the ID number of a Shape containing this Cell
     *      RemoveShape(ShapeNum)               Reverses AddShape
     *      ForceSolve(n)                       Records the Cell as "Solved" with possibility n
     *      ForceUnSolve()                      Forces the Cell to an unsolved state, sets all possibilities = true
     *      NumSolvedCells            static    get Total number of Cells which have been Solved, includes fixed Cells
     *      ResetNumSolvedCells       static    Reset the counter of Solved Cells to zero
     *      Tag                                 get Identifier of this Cell, RnCm
     *      Solved                              Returns true if Cell is solved, else returns false<
     *      NumPossibilities                    gets Number of possibilities remaining for this Shape,  = 1 if Solved
     *      Solution                            gets the Solution index, i.e. number 0 through NChars - 1
     *      NumShapes                           gets Number of Shapes containing this Cell
     *      [] ShapeNums                        gets array of id#s of all Shapes containing this Cell
     *      SolOrder                            gets/sets Order in which each Cell is Solved, zero through NumSolvedCells - 1
     *      [] Possibilities                    gets a boolean array of remaining possibilities
     *      Cell[i]                             gets/sets possibility []
     */
    private static int numSolvedCells;
    string tag;
    bool solved;
    int solution;
    int solOrder;
    int nShape = 0;
    int maxShape;
    bool[] possibilities;
    int[] shapeNums;

    /// <summary>Creates a new, unsolved, Cell with identifier Tag</summary>
    /// <param name="Tag">string, the identifier for the Cell</param>
    public void Add(string Tag)
    {
        this.tag = Tag;
        possibilities = new bool[Characters.NumChars];
        maxShape = 5;   //Initial value, will expand if necessary, see AddShape
        shapeNums = new int[maxShape];
        for (int nS = 0; nS < maxShape; nS++)
        {
            shapeNums[nS] = -1;
        }
        ForceUnSolve();
    }

    /// <summary>Add the ID number of a Shape containing this Cell</summary>
    /// <param name="ShNum">The number of the Shape to be added</param>
    public void AddShape(int ShNum)
    {
        if (!shapeNums.Contains(ShNum))
        {
            expandIfFull();
            shapeNums[nShape++] = ShNum;  //nShape counts # of Shapes for this Cell
        }
    }

    /// <summary>Reverses AddShape</summary>
    /// <remarks>The array, shapeNums, is reordered to bring active elements forward</remarks>
    /// <param name="ShNum">Number of the Shape to be removed</param>
    /// <returns>true if the Shape was removed, false if the Shape was not found</returns>
    public bool RemoveShape(int ShNum)
    {
        bool found = false;
        if (shapeNums.Contains(ShNum))
        {
            found = true;
            for (int i = 0; i < nShape; i++)
            {
                if (shapeNums[i] == ShNum)
                {
                    if (i + 1 < nShape)
                    {
                        //
                        // Move ShNum one place to the right in the array
                        int temp = shapeNums[i + 1];
                        shapeNums[i + 1] = shapeNums[i];
                        shapeNums[i] = temp;
                    }
                    //
                    // ShNum now at end of array, replace by -1
                    else shapeNums[i] = -1;
                }
            }
            nShape--;       //nShape counts # of Shapes for this Cell
        }
        return found;
    }

    /// <summary>Records the Cell as "Solved" with possibility n</summary>
    /// <remarks>Sets possibilities[i] = (i == n)</remarks>
    /// <param name="n">Number to record (index of possibilities array)</param>
    /// <returns>Number of possibilities eliminated</returns>
    public int ForceSolve(int n)
    {
        int possEliminated;
        if ((n < 0) | (n >= Characters.NumChars))
        {
            InOutUtilities iO = new InOutUtilities();
            iO.Display_And_Pause(
                " Invalid n in ForceSolve, n= ",
                n.ToString(), " Cell = ", this.tag.ToString());
            return 0;
        }
        if (this.solved) return 0;
        possEliminated = recalculateNumPossibilities() - 1;
        this.solved = true;
        this.solOrder = numSolvedCells++;
        this.solution = n;
        for (int nCh = 0; nCh < Characters.NumChars; nCh++)
        {
            possibilities[nCh] = (nCh == n);
        }
        return possEliminated;
    }
    /// <summary>Forces the Cell to an unsolved state, sets all possibilities = true</summary>
    public void ForceUnSolve()
    {
        this.solved = false;
        this.solOrder = 0;
        this.solution = -1;
        for (int nCh = 0; nCh < Characters.NumChars; nCh++)
        {
            this.possibilities[nCh] = true;
        }
    }

    /// <summary>Total number of Cells which have been Solved, includes fixed Cells</summary>
    public static int NumSolvedCells
    {
        get { return numSolvedCells; }
    }

    /// <summary>Reset the counter of Solved Cells to zero</summary>
    public static void ResetNumSolvedCells()
    {
        numSolvedCells = 0;
    }

    /// <summary>Identifier of this Cell, RnCm</summary>
    public string Tag
    {
        get { return this.tag; }
    }

    /// <summary>Returns true if Cell is solved, else returns false</summary>
    public bool Solved
    {
        get { return this.solved; }
    }

    /// <summary>Number of possibilities remaining for this Shape,  = 1 if Solved</summary>
    public int NumPossibilities
    {
        get
        {
            return recalculateNumPossibilities();
        }
    }

    private int recalculateNumPossibilities()
    {
        int n = 0;
        for (int nCh = 0; nCh < Characters.NumChars; nCh++)
        {
            if (possibilities[nCh])
            {
                n++;
                this.solution = nCh;
            }
            if (n > 1) solution = -1;
        }
        return n;
    }

    /// <summary>Returns the Solution index, i.e. number 0 through NChars - 1</summary>
    /// <remarks>Use Characters.Chars[c.Solution] for display, Characters.Values[c.Solution] for value</remarks>
    /// <returns>Solution index, number 0 through NChars - 1</returns>
    public int Solution
    {
        get { return this.solution; }
    }

    /// <summary>Number of Shapes containing this Cell</summary>
    public int NumShapes
    {
        get { return this.nShape; }
    }

    /// <summary>Id number of all Shapes containing this Cell</summary>
    public int[] ShapeNums
    {
        get { return this.shapeNums; }
    }

    /// <summary>Order in which each Cell is Solved, zero through NumSolvedCells - 1</summary>
    public int SolOrder
    {
        get { return this.solOrder; }
    }

    /// <summary>Array giving all possible solution for this Cell</summary>
    public bool[] Possibilities
    {
        get { return this.possibilities; }
    }

    /// <summary>Get or Set a possibility for this Cell</summary>
    public bool this[int Index]
    {
        get { return this.possibilities[Index]; }
        set
        {
            this.possibilities[Index] = value;
        }
    }

    private void expandIfFull()
    {
        if (nShape == maxShape)
        {
            maxShape += 5;
            int[] newShapeNums = new int[maxShape];
            this.shapeNums.CopyTo(newShapeNums, 0);
            this.shapeNums = newShapeNums;
            for (int nS = nShape; nS < maxShape; nS++)
            {
                shapeNums[nS] = -1;
            }
        }
    }
}

/// <summary>Stores all information associated with a single Shape</summary>
public class Shape
{
    private static int maxShapeNo = -1;
    private static int numActiveShapes = 0;
    private int num;
    private ShapeType type;
    private string label;
    private int sum;
    private int size;
    private string[] cellTags;
    private string identifier;
    private int[,] partitions;
    private int nPartition = 0;
    private int nActivePartition;
    private bool noRepeatSolns;

    /// <summary>Add a new Shape</summary>
    /// <param name="Type">Type of Shape, chose from enum ShapeType</param>
    /// <param name="Label">Label of Shape - not validated</param>
    /// <param name="Sum">Sum of Cell values</param>
    /// <param name="CellTags">Array of all Cell Tags, No of Cell Tags sets Size</param>
    /// <returns>Number of Shape, used as unique identifier</returns>
    public int Add(ShapeType Type, string Label, int Sum, string[] CellTags)
    {
        this.num = ++maxShapeNo;
        numActiveShapes++;
        this.type = Type;
        this.label = Label;
        this.sum = Sum;
        this.size = CellTags.Count();
        this.cellTags = new string[size];
        CellTags.CopyTo(cellTags, 0);
        this.identifier = Shared.CreateShapeIdentifier(type, label, sum, cellTags);
        switch (this.type)
        {
            case ShapeType.Sudoku:
            case ShapeType.Killer:
                noRepeatSolns = true;
                break;
            case ShapeType.Super:
            case ShapeType.Created:
                noRepeatSolns = false;
                break;
        }
        return num;
    }

    /// <summary>Resets the number of Shapes to zero</summary>
    public static void ResetShapeCount()
    {
        numActiveShapes = 0;
        maxShapeNo = -1;
    }

    /// <summary>Returns the number of the last Shape added</summary>
    public static int MaxShapeNo
    {
        get { return maxShapeNo; }
    }

    /// <summary>Returns the identification number of a given Shape</summary>
    public int Num
    {
        get { return this.num; }
    }

    /// <summary>Returns the Type of a given Shape</summary>
    public ShapeType Type
    {
        get { return this.type; }
    }

    /// <summary>Returns the Label of a given Shape</summary>
    public string Label
    {
        get { return this.label; }
    }

    /// <summary>Returns the Sum of a given Shape</summary>
    public int Sum
    {
        get { return this.sum; }
    }

    /// <summary>Returns the Size (# Cells) of a given Shape</summary>
    public int Size
    {
        get { return this.size; }
    }

    /// <summary>Returns the Identifier (Type, Sum, Cell Tags) of a given Shape</summary>
    public string Identifier
    {
        get { return this.identifier; }
    }

    /// <summary>Returns an Array of all Cell Tags for a given Shape</summary>
    public string[] CellTags
    {
        get { return this.cellTags; }
    }

    /// <summary>Indicates if a value may be repeated in a given Shape</summary>
    /// <remarks>
    /// Always set true (No repeats) for Sudoku and Killer Shapes
    /// Always set false (Repeats allowed) for Super Shapes
    /// Set true for Created Shape iff wholely contained within a Sudoku or Killer Shape
    /// </remarks>
    public bool NoRepeatSolns
    {
        get { return this.noRepeatSolns; }
        set { this.noRepeatSolns = value; }
    }
}

Generality Of The Code

Armed with these two classes the coding becomes very straightforward. For example, if we solve a Cell we do not have to eliminate that solution from each Row, Column and Box that contains the Cell but simply from every Shape that contains the Cell.

Having created the above classes the next step was to store them in sorted lists. This avoided the need to dimension arrays and made it simple to keep the code general. This means that exactly the same code is used to solve a samurai problem, Figure 1, as a regular 9X9 Sudoku problem, or as a 9X9X problem where numbers cannot repeat on the diagonals, Figure 2, or even as a 3 dimensional Tredoku problem, Figure 3. A little extra code was required to draw Figure 3 but no extra code was needed to draw and solve the identical problem shown as a 2 dimensional mapping in Figure 4,

Note that in the 9X9X and Tredoku problems the Shapes do not all contain contiguous Cells. In fact the word contiguous has no meaning since the diagrams, above, are simply a way of mapping the problem into something we would recognise. It’s critical to the philosophy of the program that Cells are simply classes that can contain a number of possible solutions and Shapes are simply classes that reference collections of Cells. A further generalisation allows the number of unknowns to be an input parameter, this defines the sizes of the Sudoku Shapes (in normal parlance the sizes of the Rows, Columns and Boxes). Then the unknowns can be mapped to "any" symbol. I have restricted this to mean any symbol that can be represented as a single Unicode character, simply to be able to display mark-up during the solution without needing separators, Figure 5.

The struct for the character information is shown below. This is one of the very few arrays that are used in the program.

Struct Characters
   /// <summary>Information on Character set used to display the problem and solution</summary>
    public struct Characters
    {
        /// <summary>Returns number of Characters in the Problem</summary>
        public static int NumChars { get { return Chars.Count(); } }
        /// <summary>Gets or Sets the Character set as a string[]</summary>
        public static string[] Chars { get; set; }
        /// <summary>Values associated with the Characters</summary>
        public static int[] Values { get; set; }
    }

Algorithms

With these concepts it was relatively easy to write code that implements most of the well-known algorithms, Table 1, for solving very general Sudoku problems. It does not use the "X-Wing" algorithm because this seems to require knowledge of the geometry of the problem.

I give an example of the code for Naked and Hidden Pairs etc, below. This gives an example of how simple the code can be if we are not encumbered with concepts of Rows, Columns and Boxes. In fact I have 2 versions of this code, the special version, shown here, is fast but requires that at least one Cell contains an exact match. The general version allows for combinations such as (1,2), (2,3), (1,3) but is slow so is only used if all else fails.

/// <summary>Check for sets of n Cells in this Shape containing exactly n possibilities
/// <para >Special method - requires one Cell in the subset contains exactly n possibilities,
/// i.e. one Cell has n possibilities and n-1 Cells have subsets</para></summary>
/// <param name="n">Looking for n Cells in Shape s which between them have n possibilities</param>
/// <param name="s">Shape to apply this logic to</param>
/// <returns>Number of possibilities eliminated</returns>
private int nPossInNCellsInShapeSSpecial(int n, Shape s)
{
    int possibilitiesEliminated = 0;
    string[] cellTags = getListOfSuitableCells(n, s);
    if (cellTags != null)
    {
        //
        // Find a Cell with exactly n possibilities
        foreach (string tag in cellTags)
        {
            Cell c = (Cell)Collections.Cells[tag];
            if (c.NumPossibilities == n)
            {
                //
                // Find all Cells with a subset of these possibilities
                List<string> selectedCells = new List<string>();
                selectedCells.Add(tag);
                foreach (string otherTag in cellTags)
                {
                    if (otherTag != tag)
                    {
                        Cell otherC = (Cell)Collections.Cells[otherTag];
                        bool subset = true;
                        for (int ch = 0; ch < Characters.NumChars; ch++)
                        {
                            if (otherC[ch] && !c[ch])
                            {
                                subset = false;
                                break;
                            }
                        }
                        if (subset)
                        {
                            selectedCells.Add(otherTag);
                        }
                    }
                }
                if (selectedCells.Count == n)
                {
                    possibilitiesEliminated += removePossibilitesFromRemainingCells(n, s, selectedCells);
                }
            }
        }
    }
    return possibilitiesEliminated;
}

User Interface

A significant part of the programming was to develop the user interface. But most of the issues were due to my ignorance and inexperience rather than to the inherent difficulty of the task.

Choosing WPF for the user interface was originally a mistake. I wasn’t even aware that there was another possibility – Windows Forms. Every time I got stuck and needed to search for help my search would find a WinForms solution (there seems to be far more help available for WinForms than for WPF) which I would unwittingly try to implement and then wonder why it didn’t work. Eventually I twigged and now always include "wpf" in my search string. But this was not obvious at the time and may be a source of confusion to other learners. It would be helpful if there were clearer documentation about differences and why both exist and reasons for choosing each. I read somewhere that WPF is Microsoft’s preferred direction but all the help documentation seems to indicate otherwise. The actual solution grid shown in the above diagrams could not be generated in XAML since it needed to be dynamic but it is relatively easy to create an array of TextBoxes and then delete any that are not wanted. Writing the code to generate the Shape boundaries was a lot of fun, especially for Killer problems where I wanted to identify the Killer Shapes and also put the sum in the top left Cell, see Figure 6.

All the rest of the user interface, including all controls was written using XAML, and this turned out to be very easy. I like the way that, if I want to change controls around and maybe place one inside another I can simply cut and paste the XAML code.

Creating Sudoku Problems

I wanted to add the capability to create Sudoku problems and for this I am very grateful to an article published here entitled "Sudoku using Microsoft Solver Foundation" http://www.codeproject.com/Articles/419389/Sudoku-using-MS-Solver-Foundation

I use MS Solver Foundation to populate the solution grid then successively hide Cells until left with the smallest number which still gave a unique solution. This makes it easy to create new problems for any geometry.

Limitations

This was all written for PC. I have not attempted to write it for phone since I have no Silverlight knowledge. I also did not try to make this an interactive game program where the user is presented with a problem that he attempts to solve directly on the PC. Both the phone and the interactive game are currently beyond a learner’s capability so I decided to stick with a Sudoku solver and problem creator.

Conclusion And Summary

Overall this has been a great experience which has lifted my coding capability from unstructured code in Fortran IV to a semblance of competence in a modern object oriented language. I have only included a few code examples since these illustrate the power of using a language like C# and the full code is rather long and mainly involved in the user interface. I’m sure that an experienced programmer could write this much better than I can.

The points I want to stress are the general definition of Shape, which eliminates the need for separate code for Row, Column and Box, plus the use of classes for Cell and Shape which hide a lot of the complexity and enable the code to be made very general.