/// <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; }
    }
}

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; }
    }

/// <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;
}