/*****************************************************************************
**
**    Soo.cs
**
*****************************************************************************/
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;
 
class Soo
    {
    public enum Difficulty
        {
        UNKNOWN = 0,
        EASY,
        NORMAL,
        HARD,
        FIENDISH,
        DIABOLICAL,
        IMPOSSIBLE
        };
 
    private const int MAX_CHAIN = Grid.Size;
    private const int MAX_FISH = (Grid.Size / 2) + 1;
    private const int MAX_SUBSET = Grid.Size - Grid.BoxSize;
    /*    -----------------------------------------------------------------------
        VARIABLES
        -----------------------------------------------------------------------    */
#region "VARIABLES"
    protected Difficulty    _difficulty;
    protected Grid             _grid;
    protected List<Hint>     _hints;
    protected bool?         _possible;
    protected bool?         _solved;
    protected string         _strDetails;
 
    protected House[]        _housesBox = new House[ Grid.Size ];
    protected House[]        _housesColumn = new House[ Grid.Size ];
    protected House[]        _housesRow = new House[ Grid.Size ];
#endregion
/*    -----------------------------------------------------------------------
    CONSTRUCTOR
    -----------------------------------------------------------------------    */
#region "Constructor"
    public
    Soo()
        {
        _grid = new Grid();
        _hints = new List<Hint>();
 
        for (int idx = 0; idx < Grid.Size; ++idx)
            {
            _housesBox[ idx ] = new House( this, idx, Grid.House.Box );
            _housesColumn[ idx ] = new House( this, idx, Grid.House.Column );
            _housesRow[ idx ] = new House( this, idx, Grid.House.Row );
            }
 
        Reset();
        }    /* end of Soo::Soo() */
#endregion
/*    -----------------------------------------------------------------------
    PUBLIC METHODS
    -----------------------------------------------------------------------    */
 
    public String
    DisplaySolution()
        {
        StringBuilder        sb = new StringBuilder( _hints.Count * 64 );
 
        foreach (Hint hint in _hints)
            {
            switch (hint.type)
                {
                case Hint.HintType.SET_VALUE:
                    sb.AppendFormat( "{0} => {1}\t\t{2}\n",
                                        Grid.SqName( hint.index ), 
                                        hint.iValue, 
                                        hint.strWhy );
                    break;
 
                case Hint.HintType.ELIMINATE_CANDIDATE:
                    sb.AppendFormat( "{0} => not {1}\t\t{2}\n",
                                        Grid.SqName( hint.index ), 
                                        hint.iValue, 
                                        hint.strWhy );
                    break;
                }
            }
 
        if (Solved)
            sb.Append( _grid.Display() );
        else
            {
            sb.Append( _grid.DisplayMarks() );
            sb.Append("\n");
            sb.Append( _grid.DisplayShortForm('.') );
            }
 
        sb.AppendFormat("\nDifficulty: {0}\n", _difficulty.ToString() );
 
        return sb.ToString();
        }    /* end of Soo::DisplaySolution() */
    ///
    ///    <summary>
    ///    Eliminates a candidate for a given square
    ///    </summary>
    ///    <returns>TRUE if candidate eliminated, FALSE otherwise</returns>
    ///    <param name="index">Index of square</param>
    ///    <param name="iValue">Value to be eliminated</param>
    ///
    public bool
    EliminateCandidate( int index, int iValue )
        {
        if (_grid[ index ].ClearCandidate( iValue ))
            {
            Hint hint;
#if TRACE_SOLVE
            Console.WriteLine( _grid.DisplayMarks() );
            Console.WriteLine( "{0} => not {1}\t\t{2}",
                                Grid.SqName( index ), iValue, _strDetails );
#endif
            hint.type = Hint.HintType.ELIMINATE_CANDIDATE;
            hint.index = index;
            hint.iValue = iValue;
            hint.strWhy = _strDetails;
 
            _hints.Add( hint );
 
            return true;
            }
 
        return false;
        }    /* end of Soo::EliminateCandidate() */
    ///
    ///    <summary>
    ///    Parses a string and attempts to build a valid grid from it
    ///    </summary>
    ///    <returns>TRUE if parsed successfully, FALSE otherwise</returns>
    ///    <param name="strRaw">Raw string to parse</param>
    ///
    public bool
    Parse( string strRaw )
        {
        Reset();
        if (_grid.Parse(strRaw, out _strDetails) &&
            isSolvable())
            {
            //
            //    Make sure the solution is unique
            //
            if (_grid.EmptyCount == 0)
                return true;    // already solved?
 
            DancingLinks dlx = new DancingLinks( );
 
            if (dlx.Solve( _grid, false ) == 1)
                return true;
 
            _strDetails = (dlx.Solutions == 0) ?
                            "Does not have a solution." :
                            "Does not have a unique solution.";
            }
 
        return false;
        }    /* end of Soo::Parse() */
    ///
    ///    <summary>
    ///    Resets the game to it's initial (blank) state
    ///    </summary>
    ///
    public void
    Reset()
        {
        _difficulty = Difficulty.UNKNOWN;
        _possible = null;
        _solved = null;
        _strDetails = "";
        _hints.Clear();
        _grid.Reset();
        }    /* end of Soo::Reset() */
    ///
    ///    <summary>
    ///    Assigns a value to a square
    ///    </summary>
    ///    <param name="index">Index of square</param>
    ///    <param name="iValue">Value to be assigned</param>
    ///
    public void
    SetSquare( int index, int iValue )
        {
        if (_grid.Set( index, iValue ))
            {
            Hint hint;
#if TRACE_SOLVE
            Console.WriteLine( _grid.DisplayMarks() );
            Console.WriteLine( "{0} => {1}\t\t{2}",
                                Grid.SqName( index ), iValue, _strDetails );
#endif
            hint.type = Hint.HintType.SET_VALUE;
            hint.index = index;
            hint.iValue = iValue;
            hint.strWhy = _strDetails;
 
            _hints.Add( hint );
            //
            //    Grid has changed, so the solvable/solved state is now unknown.
            //
            _possible = null;
            _solved = null;
            }
        }    /* end of Soo::SetSquare() */
    ///
    ///    <summary>
    ///    Attempts to solve the puzzle
    ///    </summary>
    /// <returns>TRUE if solved, FALSE otherwise</returns>
    ///
    public bool
    Solve()
        {
        _hints.Clear();
 
        try
            {
            while (!isSolved() && SolveStep())
                { /* EMPTY LOOP */ }
            }
        catch (IllegalValueException ex)
            {
            _difficulty = Difficulty.IMPOSSIBLE;
            _possible = false;
            _strDetails = String.Format( "The value '{0}' at square {1} is illegal.",
                                        ex.iValue, Grid.SqName( ex.index ) );
            throw new ApplicationException(_strDetails);
            }
        catch (UnsolvableSquareException ex)
            {
            _difficulty = Difficulty.IMPOSSIBLE;
            _possible = false;
            _strDetails = String.Format( "Square {0} has no possible value.",
                                        Grid.SqName( ex.index ) );
            throw new ApplicationException(_strDetails);
            }
 
        return Solved;
        }    /* end of Soo::Solve() */
    ///
    ///    <summary>
    ///    Solves the puzzle
    ///    </summary>
    ///    <returns>TRUE if solved, FALSE otherwise</returns>
    ///
    public bool
    SolveStep()
        {
        int iHouse;
 
        if (findNakedSingles())
            {
            if (_difficulty < Difficulty.EASY)
                _difficulty = Difficulty.EASY;
            return true;
            }
 
        for (iHouse = 0; iHouse < Grid.Size; ++iHouse)
            if (_housesBox[ iHouse ].FindHiddenSingles() ||
                _housesColumn[ iHouse ].FindHiddenSingles() ||
                _housesRow[ iHouse ].FindHiddenSingles())
                {
                if (_difficulty < Difficulty.EASY)
                    _difficulty = Difficulty.EASY;
                return true;
                }
 
        for (iHouse = 0; iHouse < Grid.Size; ++iHouse)
            if (_housesBox[ iHouse ].FindNakedPairs() ||
                _housesColumn[ iHouse ].FindNakedPairs() ||
                _housesRow[ iHouse ].FindNakedPairs() ||
                _housesBox[ iHouse ].FindBoxLineReductions() ||
                _housesColumn[ iHouse ].FindBoxLineReductions() ||
                _housesRow[ iHouse ].FindBoxLineReductions())
                {
                if (_difficulty < Difficulty.NORMAL)
                    _difficulty = Difficulty.NORMAL;
                return true;
                }
 
        for (iHouse = 0; iHouse < Grid.Size; ++iHouse)
            if (_housesBox[ iHouse ].FindSubsets( MAX_SUBSET ) ||
                _housesColumn[ iHouse ].FindSubsets( MAX_SUBSET ) ||
                _housesRow[ iHouse ].FindSubsets( MAX_SUBSET ))
                {
                if (_difficulty < Difficulty.HARD)
                    _difficulty = Difficulty.HARD;
                return true;
                }
 
        if (findFish() ||
            findWings() ||
            findColors() ||
            findChains() ||
            findRectangles())
            {
            if (_difficulty < Difficulty.FIENDISH)
                _difficulty = Difficulty.FIENDISH;
            return true;
            }
 
        if (_difficulty < Difficulty.DIABOLICAL)
            _difficulty = Difficulty.DIABOLICAL;
 
        return false;
        }    /* end of Soo::SolveStep() */
/*    -----------------------------------------------------------------------
    PRIVATE METHODS
    -----------------------------------------------------------------------    */
#region    "PRIVATE METHODS"
    ///
    /// <summary>
    /// Eliminate candidates based on "XY-Chains" strategy
    /// </summary>
    /// <returns>TRUE if one or more candidates eliminated, FALSE otherwise</returns>
    ///  
    private bool
    findChains()
        {
        Square    sq;
        int     iPeer,
                iSecond;
        uint    uLink;
        int[]    iList = new int[ MAX_CHAIN ];
 
        for (int iFirst = 0; iFirst < Grid.Squares; ++iFirst)
            {
            sq = _grid[ iFirst ];
            if (sq.CandidateCount != 2)
                continue;
 
            for (iPeer = 0; iPeer < Grid.Peers; ++iPeer)
                {
                iSecond = Grid.NthPeer( iFirst, iPeer );
                if (_grid[ iSecond ].IsEmpty &&
                    _grid[ iSecond ].CandidateCount == 2)
                    {
                    uLink = _grid.SharedCandidates( iFirst, iSecond );
                    if (uLink != 0 &&
                        BitSet.CountBits(uLink) == 1)
                        {
                        iList[ 0 ] = iFirst;
                        iList[ 1 ] = iSecond;
                        if (goChaining( uLink, 2, iList ))
                            return true;
                        }
                    }
                }
            }
 
        return false;
        }
    ///
    /// <summary>
    /// Eliminate candidates based on "Simple Coloring" strategy
    /// </summary>
    /// <returns>TRUE if one or more candidates eliminated, FALSE otherwise</returns>
    ///  
    private bool
    findColors()
        {
        int     index,
                iHere,
                iPeer,
                iValue;
        bool     bFound = false;
        int[]     iColors = new int[ Grid.Squares ];
 
        for (iValue = Grid.ValueMin; iValue <= Grid.ValueMax; ++iValue)
            {
            if (_grid.CountValues( iValue ) >= (Grid.Size - 1))
                continue;
 
            for (index = 0; index < Grid.Squares; ++index)
                {
                if (!_grid[ index ].Candidates.Test( iValue ))
                    continue;
 
                for (int idx = 0; idx < Grid.Squares; ++idx)
                    iColors[idx] = 0;
 
                iColors[index] = 1;
                if (goColoring(iValue, 1, index, iColors))
                    {
                    int         iSeen,
                                iTarget;
 
                    for (iHere = 0; iHere < Grid.Squares; ++iHere)
                        {
                        if ((iSeen = iColors[iHere]) == 0)
                            {
                            if (_grid[ iHere ].IsEmpty &&
                                _grid[ iHere ].Candidates.Test( iValue ))
                                {
                                for (iPeer = 0; iPeer < Grid.Peers; ++iPeer)
                                    {
                                    iTarget = Grid.NthPeer( iHere, iPeer );
                                    if (iColors[ iTarget ] != 0 &&
                                        iColors[ iTarget ] != iSeen)
                                        {
                                        if (iSeen == 0)
                                            iSeen = iColors[ iTarget ];
                                        else
                                            {
                                            _strDetails = "SIMPLE COLORING";
                                            if (EliminateCandidate(iHere, iValue))
                                                bFound = true;
                                            }
                                        }
                                    }
 
                                if (bFound)
                                    return true;
                                }
                            }
                        else
                            {
                            //
                            //    Look for two squares of the same color that share the
                            //    same box, row, or column.  If we find this, then all of
                            //    the squares of the OTHER color can be set to the current
                            //    value.
                            //
                            for (Grid.House house = Grid.House.Box; house <= Grid.House.Row; ++house)
                                {
                                iTarget = iHere;
                                while ((iTarget = Grid.NextSq(iTarget, house)) != iHere)
                                    if (iColors[iTarget] == iSeen)
                                        {
                                        for (int iTrue = 0; iTrue < Grid.Squares; ++iTrue)
                                            if (iColors[iTrue] != 0 && iColors[iTrue] != iSeen)
                                                {
                                                _strDetails = "SIMPLE COLORING (EXCLUSION)";
                                                SetSquare(iTrue, iValue);
                                                bFound = true;
                                                }
 
                                        if (bFound)
                                            return true;
                                        }
                                }
                            }
                        }
                    }
                }
            }
 
        return bFound;
        }    /* end of findColors() */
    ///
    /// <summary>
    /// Eliminate candidates based on "Swordfish" or "Jellyfish" strategies
    /// </summary>
    /// <returns>TRUE if one or more candidates eliminated, FALSE otherwise</returns>
    /// <remarks>
    /// SWORDFISH: three columns with only two candidates for a given digit. 
    /// If these fall on exactly three common rows, and each of those rows has 
    /// at least two candidate cells, then all three rows can be cleared of 
    /// that digit - except in the defining cells. This is the original, 
    /// "restrictive" definition. It has since been realised that a more 
    /// relaxed definition is possible, in that the three columns can each 
    /// have two or three candidates for the given digit -- as long as they 
    /// fall on the three common rows.
    /// </remarks>
    ///  
    private bool
    findFish()
        {
        int iCount,
                iLine;
        uint uSquare;
        int[] iLines = new int[ MAX_FISH ];
        uint[] uSquares = new uint[ MAX_FISH ];
 
        for (int iMaxDepth = 2; iMaxDepth < MAX_FISH; ++iMaxDepth)
            for (int iValue = Grid.ValueMin; iValue <= Grid.ValueMax; ++iValue)
                {
                for (iLine = 0; iLine < (Grid.Size - iMaxDepth); ++iLine)
                    {
                    iCount = _housesRow[ iLine ].GetCandidateSquares( iValue, out uSquare );
                    if (iCount >= 2 && iCount <= iMaxDepth)
                        {
                        iLines[ 0 ] = iLine;
                        uSquares[ 0 ] = uSquare;
                        if (goFishing( iValue, 1, iMaxDepth, iLines, uSquare, uSquares, ref _housesRow ))
                            return true;
                        }
 
                    iCount = _housesColumn[ iLine ].GetCandidateSquares( iValue, out uSquare );
                    if (iCount >= 2 && iCount <= (Grid.Size - iMaxDepth))
                        {
                        iLines[ 0 ] = iLine;
                        uSquares[ 0 ] = uSquare;
                        if (goFishing( iValue, 1, iMaxDepth, iLines, uSquare, uSquares, ref _housesColumn ))
                            return true;
                        }
                    }
                }
 
        return false;
        }    /* end of Soo::findFish() */
    ///
    ///    <summary>
    ///    Finds all NAKED SINGLE squares
    ///    </summary>
    ///    <returns>TRUE if one or more found, FALSE otherwise</returns>
    ///    <remarks>
    ///    NAKED SINGLE is when a square has only one possible candidate.
    ///    </remarks>
    ///
    private bool
    findNakedSingles()
        {
        Square    sq;
        int        iValue;
        bool    bFound = false;
 
        for (int index = 0; index < Grid.Squares; ++index)
            {
            sq = _grid[ index ];
            if (sq.CandidateCount == 1)
                {
                iValue = sq.Candidates.FirstBit;
                Debug.Assert( Grid.IsValidValue( iValue ) );
 
                _strDetails = "NAKED SINGLE";
                SetSquare( index, iValue );
                bFound = true;
                //
                //    Reset the counter to the lowest peer of this square
                //
                if (_grid.EmptyCount > 0)
                    index = Math.Min(index, Grid.NthPeer(index, 0) - 1);
                else
                    break;
                }
            }
 
        return bFound;
        }    /* end of Soo::findNakedSingles() */
    ///
    ///    <summary>
    ///    Finds the first UNIQUE RECTANGLE 
    ///    </summary>
    ///    <returns>TRUE if one or more found, FALSE otherwise</returns>
    ///    <remarks>
    ///    </remarks>
    ///
    private bool
    findRectangles()
        {
        int        iBase,
                iCorner1,
                iCorner2,
                iTarget,
                iValue;
        uint    uDeadlyBits;
        bool    bFound = false;
        BitSet    setBoxes = new BitSet();
 
        for (iBase = 0; iBase < Grid.Squares; ++iBase)
            {
            if (_grid[ iBase ].CandidateCount != 2)
                continue;
 
            uDeadlyBits = _grid[ iBase ].Candidates.Bits;
            //
            //    iBase is now the "base corner" that we'll work off of:  try to
            //    find a square in the same row with the same pair, and then a
            //    second square in the same column with the same pair.
            //
            iCorner1 = iBase;
            while ((iCorner1 = Grid.NextSq(iCorner1, Grid.House.Column)) != iBase)
                if (_grid[iCorner1].Candidates.Bits == uDeadlyBits)
                    break;
 
            if (iCorner1 == iBase)
                continue;    // didn't find a first candidate
 
            iCorner2 = iBase;
            while ((iCorner2 = Grid.NextSq(iCorner2, Grid.House.Row)) != iBase)
                if (_grid[iCorner2].Candidates.Bits == uDeadlyBits)
                    break;
 
            if (iCorner2 == iBase)
                continue;    // didn't find a second candidate
 
            iTarget = (Grid.GetRow(iCorner1) * Grid.Size) + Grid.GetColumn(iCorner2);
            Debug.Assert( Grid.IsValidIndex(iTarget) );
 
            if ((_grid[iTarget].Candidates.Bits & uDeadlyBits) != uDeadlyBits)
                continue;    // fourth corner doesn't contain the "deadly bits"
            //
            //    The key to a "unique rectangle" is that it must occupy
            //    exactly TWO boxes, TWO columns, and TWO rows.  Because we
            //    searched by row and column, we know that there are already
            //    2 columns and rows, but we have to make sure that there are
            //    only two boxes.
            //
            setBoxes.ClearAll();
            setBoxes.Set( Grid.GetBox(iBase) );
            setBoxes.Set( Grid.GetBox(iCorner1) );
            setBoxes.Set( Grid.GetBox(iCorner2) );
            setBoxes.Set( Grid.GetBox(iTarget) );
 
            if (setBoxes.Count == 2)
                {
                //
                //    Found a unique rectangle, so we can remove the "deadly
                //    bits" from the final corner.
                //
                _strDetails = String.Format("UNIQUE RECTANGLE: {0} - {1} - {2} - {3}",
                                            Grid.SqName(iBase), Grid.SqName(iCorner1), 
                                            Grid.SqName(iCorner2), Grid.SqName(iTarget));
 
                for (iValue = BitSet.FindFirst(uDeadlyBits);
                     iValue > 0;
                     iValue = BitSet.FindNext(uDeadlyBits, iValue + 1))
                    {
                    if (EliminateCandidate(iTarget, iValue))
                        bFound = true;
                    }
 
                if (bFound)
                    return true;
                }
            }
 
        return bFound;
        }    /* end of Soo::findRectangles() */
    ///
    /// <summary>
    /// Eliminate candidates based on "Y-Wing" strategy
    /// </summary>
    /// <returns>TRUE if one or more candidates eliminated, FALSE otherwise</returns>
    ///  
    private bool
    findWings()
        {
        int idx,
                iCount,
                iPeer,
                iPeerHi,
                iPeerLo,
                iWingHi,
                iWingLo;
        uint uBitsHi,
                uBitsLo,
                uBitsPivot;
        bool bFound = false;
 
        for (int iPivotSq = 0; iPivotSq < (Grid.Squares - 2); ++iPivotSq)
            {
            iCount = _grid[ iPivotSq ].CandidateCount;
            if (!(iCount == 2 || iCount == 3))
                continue;
            //
            //    Search for another square with only 2 candidates that intersects 
            //    the pivot square and shares one common value. This square is the
            //    "Wing #1" square.
            //
            for (iPeerLo = 0; iPeerLo < Grid.Peers; ++iPeerLo)
                {
                iWingLo = Grid.NthPeer( iPivotSq, iPeerLo );
                if (_grid[ iWingLo ].CandidateCount != 2)
                    continue;
 
                uBitsPivot = _grid[ iPivotSq ].Candidates.Bits;
                uBitsLo = _grid[ iWingLo ].Candidates.Bits;
                if (BitSet.CountBits( uBitsPivot & uBitsLo ) != (iCount - 1))
                    continue;
 
                if (iCount == 3)
                    {
                    //
                    //    XYZ-WING: three cells that contain only 3 different numbers 
                    //    between them, but which fall outside the confines of one 
                    //    row/column/box, with one of the cells (the 'hinge') being 
                    //    able to see the other two; those other two having only one 
                    //    number in common; and the hinge having all three numbers as 
                    //    candidates. 
                    //
                    for (iPeerHi = 0; iPeerHi < Grid.Peers; ++iPeerHi)
                        {
                        iWingHi = Grid.NthPeer( iPivotSq, iPeerHi );
                        if (Grid.Intersects( iWingLo, iWingHi ) ||
                            _grid[ iWingHi ].CandidateCount != 2)
                            {
                            continue;
                            }
 
                        uBitsHi = _grid[ iWingHi ].Candidates.Bits;
                        if ((uBitsLo & uBitsPivot) == (uBitsHi & uBitsPivot) ||
                            BitSet.CountBits( uBitsPivot & uBitsHi ) != 2 ||
                            BitSet.CountBits( uBitsPivot | uBitsLo | uBitsHi ) != 3)
                            {
                            continue;
                            }
                        //
                        //    Found a possible XYZ-WING
                        //
                        Debug.Assert( BitSet.CountBits( uBitsLo & uBitsHi ) == 1 );
 
                        int iValue = BitSet.FindFirst( uBitsLo & uBitsHi );
 
                        for (iPeer = 0; iPeer < Grid.Peers; ++iPeer)
                            {
                            idx = Grid.NthPeer( iWingLo, iPeer );
                            if (Grid.Intersects( idx, iPivotSq ) &&
                                Grid.Intersects( idx, iWingHi ) &&
                                _grid[ idx ].Candidates.Test( iValue ))
                                {
                                _strDetails = String.Format( "XYZ-WING (Hinge {0} Wings {1} - {2})",
                                                                Grid.SqName( iPivotSq ),
                                                                Grid.SqName( iWingLo ),
                                                                Grid.SqName( iWingHi ) );
                                if (EliminateCandidate( idx, iValue ))
                                    bFound = true;
                                }
                            }
 
                        if (bFound)
                            return true;
                        }
                    }
                else
                    {
                    //
                    //    Now find a third square that intersects pivot square,
                    //    but NOT Wing #1) and shares one (and only one) candidate
                    //    with both "Wing #1" and the pivot.  This is the "Wing #2"
                    //    square.
                    //
                    for (iPeerHi = 0; iPeerHi < Grid.Peers; ++iPeerHi)
                        {
                        iWingHi = Grid.NthPeer( iPivotSq, iPeerHi );
                        if (iWingHi == iWingLo ||
                            Grid.Intersects( iWingLo, iWingHi ) ||
                            _grid[ iWingHi ].CandidateCount != 2)
                            {
                            continue;
                            }
 
                        uBitsHi = _grid[ iWingHi ].Candidates.Bits;
                        if ((uBitsLo & uBitsPivot) == (uBitsHi & uBitsPivot) ||
                            BitSet.CountBits( uBitsPivot & uBitsHi ) != 1 ||
                            BitSet.CountBits( uBitsPivot | uBitsLo | uBitsHi ) != 3)
                            {
                            continue;
                            }
                        //
                        // At this point, the mark shared by both wings can be 
                        // eliminated from all squares that intersect with BOTH
                        // wings, except for the pivot square.
                        //
                        int iValue = BitSet.FindFirst( uBitsLo & uBitsHi );
 
                        Debug.Assert( Grid.IsValidValue( iValue ),
                                     "Soo::findYWing() => no common mark!" );
 
                        for (iPeer = 0; iPeer < Grid.Peers; ++iPeer)
                            {
                            if ((idx = Grid.NthPeer( iWingLo, iPeer )) != iPivotSq &&
                                Grid.Intersects( idx, iWingHi ) &&
                                _grid[ idx ].Candidates.Test( iValue ))
                                {
                                _strDetails = String.Format( "Y-WING (Pivot {0} Wings {1} - {2})",
                                                                Grid.SqName( iPivotSq ),
                                                                Grid.SqName( iWingLo ),
                                                                Grid.SqName( iWingHi ) );
                                if (EliminateCandidate( idx, iValue ))
                                    bFound = true;
                                }
                            }
                        if (bFound)
                            return true;
                        }
                    //
                    //    XY-WING -- find a Wing #2 that intersects and shares a
                    //    common candidate with the Pivot wing, but does NOT
                    //    intersect Wing #1.
                    //
                    for (iPeerHi = 0; iPeerHi < Grid.Peers; ++iPeerHi)
                        {
                        iWingHi = Grid.NthPeer( iPivotSq, iPeerHi );
                        if (iWingHi == iWingLo ||
                            Grid.Intersects( iWingLo, iWingHi ) ||
                            _grid[ iWingHi ].CandidateCount != 2)
                            {
                            continue;
                            }
 
                        uBitsHi = _grid[ iWingHi ].Candidates.Bits;
                        if ((uBitsLo & uBitsPivot) == (uBitsHi & uBitsPivot) ||
                            BitSet.CountBits( uBitsPivot & uBitsHi ) != 1 ||
                            BitSet.CountBits( uBitsPivot | uBitsLo | uBitsHi ) != 3)
                            {
                            continue;
                            }
                        //
                        // At this point, the mark shared by both wings--but NOT 
                        //    in the pivot square--can be eliminated from any squares 
                        //    that intersect BOTH wings.
                        //
                        int iValue = BitSet.FindFirst( (uBitsLo | uBitsHi) & ~uBitsPivot );
 
                        Debug.Assert( Grid.IsValidValue( iValue ),
                                     "Soo::findYWing() => no common mark!" );
 
                        for (iPeer = 0; iPeer < Grid.Peers; ++iPeer)
                            {
                            if ((idx = Grid.NthPeer( iWingLo, iPeer )) != iPivotSq &&
                                Grid.Intersects( idx, iWingHi ) &&
                                _grid[ idx ].Candidates.Test( iValue ))
                                {
                                _strDetails = String.Format( "XY-WING (Pivot {0} Wings {1} - {2})",
                                                                Grid.SqName( iPivotSq ),
                                                                Grid.SqName( iWingLo ),
                                                                Grid.SqName( iWingHi ) );
                                if (EliminateCandidate( idx, iValue ))
                                    bFound = true;
                                }
                            }
 
                        if (bFound)
                            return true;
                        }
                    }
                }
            }
 
        return bFound;
        } /* end of Soo::findWings() */
    ///
    ///    <summary>
    ///    Recursive routine to find chained values
    ///    </summary>
    ///    <returns>TRUE if chain found, FALSE otherwise</returns>
    ///    <param name="uLink">Value linked from previous pair</param>
    ///    <param name="iLength">Length of chain built so far</param>
    ///    <param name="iList">Array of chained squares</param>
    ///
    private bool
    goChaining( uint uLink, int iLength, int[] iList )
        {
        Square    sq;
        int        idx,
                iPeer,
                iPrev;
        uint    uNextLink;
        bool    bFound = false;
 
        if (iLength >= MAX_CHAIN)
            return false;
 
        Debug.Assert( iLength > 1 );
        Debug.Assert( BitSet.CountBits( uLink ) == 1 );
 
        iPrev = iList[ iLength - 1 ];
        uNextLink = _grid[ iPrev ].Candidates.Bits & ~uLink;
 
        for (iPeer = 0; iPeer < Grid.Peers; iPeer++)
            {
            sq = _grid[ Grid.NthPeer( iPrev, iPeer ) ];
            if (sq.CandidateCount != 2 ||
                (sq.Candidates.Bits & uNextLink) == 0 ||
                Utility.ArrayContains( sq.Index, iList, iLength ))
                {
                continue;
                }
 
            iList[ iLength++ ] = sq.Index;
            if (goChaining( uNextLink, iLength, iList ))
                return true;
            //
            //    Didn't find a longer chain, so test what we have to see if 
            //    it's valid.  It must be an odd length and the end-points must 
            //    share a common value that wasn't used in the chain.  If so, 
            //    then that common value can be excluded from all squares 
            //    visible to BOTH endpoints.
            //    
            if (iLength > 2 && (iLength & 0x0001) == 1)
                {
                int        iSq,
                        iTarget,
                        iValue;
                uint    uHeadLink,
                        uTarget;
 
                uHeadLink = _grid.SharedCandidates( iList[ 0 ], iList[ 1 ] );
                uTarget = _grid[ iList[ 0 ] ].Candidates.Bits & ~uHeadLink;
                iValue = BitSet.FindFirst( uTarget );
 
                if (Grid.IsValidValue( iValue ) &&
                    sq.Candidates.Test(iValue) &&
                    !_grid[ iPrev ].Candidates.Test(iValue))
                    {
                    StringBuilder sb = new StringBuilder();
 
                    for (iTarget = 0; iTarget < Grid.Peers; ++iTarget)
                        {
                        iSq = Grid.NthPeer( sq.Index, iTarget );
                        if (_grid[ iSq ].Candidates.Test( iValue ) &&
                            Grid.Intersects( iSq, iList[ 0 ] ))
                            {
                            if (sb.Length == 0)
                                {
                                sb.Append( "CHAIN: " );
                                for (idx = 0; idx < iLength; ++idx)
                                    {
                                    if (idx > 0)
                                        sb.Append( "-" );
 
                                    sb.AppendFormat( "{0}", Grid.SqName( iList[ idx ] ) );
                                    }
 
                                }
 
                            _strDetails = sb.ToString();
/*
                            Console.WriteLine( "\n\n{0}\n{1}\nValue: {2}", 
                                                _grid.DisplayMarks(), sb.ToString(), iValue );
         &