[TestMethod]
public void Solve()
{
    var board = new char[,] {
        {'5','3','.','.','7','.','.','.','.'},
        {'6','.','.','1','9','5','.','.','.'},
        {'.','9','8','.','.','.','.','6','.'},
        {'8','.','.','.','6','.','.','.','3'},
        {'4','.','.','8','.','3','.','.','1'},
        {'7','.','.','.','2','.','.','.','6'},
        {'.','6','.','.','.','.','2','8','.'},
        {'.','.','.','4','1','9','.','.','5'},
        {'.','.','.','.','8','.','.','7','9'}
    };

    var expected = new char[,] {
        {'5','3','4','6','7','8','9','1','2'},
        {'6','7','2','1','9','5','3','4','8'},
        {'1','9','8','3','4','2','5','6','7'},
        {'8','5','9','7','6','1','4','2','3'},
        {'4','2','6','8','5','3','7','9','1'},
        {'7','1','3','9','2','4','8','5','6'},
        {'9','6','1','5','3','7','2','8','4'},
        {'2','8','7','4','1','9','6','3','5'},
        {'3','4','5','2','8','6','1','7','9'}
    };

    var sudoku = new Sudoku();
    sudoku.Solve(board);

    CollectionAssert.AreEqual(expected, board);
}

public class SolverOptions
{
    public int MaxRecursion { get; set; } = -1;
    public int MaxSolutions { get; set; } = -1;
    public bool IncludeCluesInSolution = false;

    public bool HasRecursionLevelExceeded(int recursionLevel)
    {
        return MaxRecursion > -1 && recursionLevel > MaxRecursion;
    }

    public bool HasSolutionsExceeded(IEnumerable<ISet<int>> solutions)
    {
        return MaxSolutions > -1 && solutions.Count() >= MaxSolutions;
    }
}

public interface ICSPSolver
{
    IReadOnlyCollection<ISet<int>> Solve(ExactCover problem, SolverOptions options);
}

public class ExactCover
{
    public ISet<int> Constraints { get; }
    public IDictionary<int, ISet<int>> Sets { get; }
    public ISet<int> Clues { get; }

    public ExactCover(ISet<int> constraints, IDictionary<int, ISet<int>> sets, ISet<int> clues)
    {
        Constraints = constraints;
        Sets = sets;
        Clues = clues;
    }

    public IReadOnlyCollection<ISet<int>> Solve(ICSPSolver solver, SolverOptions options)
    {
        return solver.Solve(this, options);
    }
}

class DLXNode
{
    internal DLXNode header, row;
    internal DLXNode up, down, left, right;
    internal int constraint, set, rowCount;

    internal DLXNode() => up = down = left = right = header = row = this;

    internal bool IsLast => right == this;

    internal void AddLast(DLXNode node) => row.left.Append(node);

    internal void AddLastDown(DLXNode node) => header.up.AppendDown(node);

    internal void Append(DLXNode node)
    {
        right.left = node;
        node.right = right;
        node.left = this;
        right = node;
    }

    internal void AppendDown(DLXNode node)
    {
        down.up = node;
        node.down = down;
        node.up = this;
        down = node;
        header.rowCount++;
    }

    internal IEnumerable<DLXNode> Iterate(Func<DLXNode, DLXNode> direction)
    {
        var node = this;
        do
        {
            yield return node;
            node = direction(node);

        } while (node != this);
    }

    public override string ToString()
    {
        var isHeader = header == this;
        var isRow = row == this;
        var isRoot = isHeader && isRow;

        return isRoot ? "R"
            : isHeader ? $"H{header.constraint}"
            : isRow ? $"R{row.set}"
            : $"C({header.constraint},{row.set})";
    }
}

public class DLX : ICSPSolver
{
    public IReadOnlyCollection<ISet<int>> Solve(ExactCover problem, SolverOptions options)
    {
        var root = Parse(problem);
        var solutions = new List<ISet<int>>();
        var currentSolution = new Stack<int>();
        var recursionLevel = 0;

        Explore(root, solutions, currentSolution, problem.Clues, recursionLevel, options);

        return solutions.AsReadOnly();
    }

    internal bool CheckForSolution(
        DLXNode root,
        IList<ISet<int>> solutions,
        Stack<int> currentSolution,
        ISet<int> clues,
        int recursionLevel,
        SolverOptions options)
    {
        if (root.IsLast
                       || options.HasRecursionLevelExceeded(recursionLevel)
                       || options.HasSolutionsExceeded(solutions))
        {
            if (root.IsLast)
            {
                var solution = new HashSet<int>(currentSolution);
                if (options.IncludeCluesInSolution)
                {
                    foreach (var clue in clues)
                    {
                        solution.Add(clue);
                    }
                }
                solutions.Add(solution);
            }

            return true;
        }

        return false;
    }

    internal DLXNode GetHeaderWithMinimumRowCount(DLXNode root)
    {
        DLXNode next = null;

        foreach (var header in root.Iterate(n => n.right).Skip(1))
        {
            if (next == null || header.rowCount < next.rowCount)
            {
                next = header;
            }
        }

        return next;
    }

    internal void Explore(
        DLXNode root,
        IList<ISet<int>> solutions,
        Stack<int> currentSolution,
        ISet<int> clues,
        int recursionLevel,
        SolverOptions options)
    {
        if (CheckForSolution(
            root, solutions, currentSolution, clues, recursionLevel, options))
        {
            return;
        }

        var header = GetHeaderWithMinimumRowCount(root);

        if (header.rowCount <= 0)
        {
            return;
        }

        Cover(header);

        foreach (var row in header.Iterate(n => n.down).Skip(1))
        {
            currentSolution.Push(row.row.set);
            foreach (var rightNode in row.Iterate(n => n.right).Skip(1))
            {
                Cover(rightNode);
            }
            Explore(root, solutions, currentSolution, clues, recursionLevel + 1, options);
            foreach (var leftNode in row.Iterate(n => n.left).Skip(1))
            {
                Uncover(leftNode);
            }
            currentSolution.Pop();
        }

        Uncover(header);
    }

    internal void Cover(DLXNode node)
    {
        if (node.row == node) return;

        var header = node.header;
        header.right.left = header.left;
        header.left.right = header.right;

        foreach (var row in header.Iterate(n => n.down).Skip(1))
        {
            foreach (var rightNode in row.Iterate(n => n.right).Skip(1))
            {
                rightNode.up.down = rightNode.down;
                rightNode.down.up = rightNode.up;
                rightNode.header.rowCount--;
            }
        }
    }

    internal void Uncover(DLXNode node)
    {
        if (node.row == node) return;

        var header = node.header;

        foreach (var row in header.Iterate(n => n.up).Skip(1))
        {
            foreach (var leftNode in row.Iterate(n => n.left).Skip(1))
            {
                leftNode.up.down = leftNode;
                leftNode.down.up = leftNode;
                leftNode.header.rowCount++;
            }
        }

        header.right.left = header;
        header.left.right = header;
    }

    internal DLXNode Parse(ExactCover problem)
    {
        var root = new DLXNode();
        var headerLookup = new Dictionary<int, DLXNode>();
        var rowLookup = new Dictionary<int, DLXNode>();
        var givens = new HashSet<int>(problem.Clues
            .SelectMany(x => problem.Sets[x]).Distinct());

        foreach (var constraint in problem.Constraints.Where(x => !givens.Contains(x)))
        {
            var header = new DLXNode { constraint = constraint, row = root };
            headerLookup.Add(constraint, header);
            root.AddLast(header);
        }

        foreach (var set in problem.Sets.Where(x => !x.Value.Any(y => givens.Contains(y))))
        {
            var row = new DLXNode { set = set.Key, header = root };
            rowLookup.Add(set.Key, row);
            root.AddLastDown(row);

            foreach (var element in set.Value)
            {
                if (headerLookup.TryGetValue(element, out var header))
                {
                    var cell = new DLXNode { row = row, header = header };
                    row.AddLast(cell);
                    header.AddLastDown(cell);
                }
            }
        }

        return root;
    }
}

[TestMethod]
        public void ManySolutions()
        {
            var problem = new ExactCover(
                new HashSet<int> { 1, 2, 3 },
                new Dictionary<int, ISet<int>> {
                      { 0, new HashSet<int> { 1 } }
                    , { 1, new HashSet<int> { 2 } }
                    , { 2, new HashSet<int> { 3 } }
                    , { 3, new HashSet<int> { 2, 3 } }
                    , { 4, new HashSet<int> { 1, 2 } }
                },
                new HashSet<int>());

            var solutions = problem.Solve(
                new DLX(),
                new SolverOptions());

            var printed = Print(problem, solutions);

            AssertAreEqual(@"
Constraints: {1, 2, 3}
Set 0: {1}
Set 1: {2}
Set 2: {3}
Set 3: {2, 3}
Set 4: {1, 2}
Solutions: 3
Solution #1: {1}, {2}, {3}
Solution #2: {1}, {2, 3}
Solution #3: {3}, {1, 2}", printed);
        }

        [TestMethod]
        public void ManySolutionsWithClues()
        {
            var problem = new ExactCover(
                new HashSet<int> { 1, 2, 3 },
                new Dictionary<int, ISet<int>> {
                      { 0, new HashSet<int> { 1 } }
                    , { 1, new HashSet<int> { 2 } }
                    , { 2, new HashSet<int> { 3 } }
                    , { 3, new HashSet<int> { 2, 3 } }
                    , { 4, new HashSet<int> { 1, 2 } }
                },
                new HashSet<int> { 2 });

            var solutions = problem.Solve(
                new DLX(),
                new SolverOptions() { IncludeCluesInSolution = true });

            var printed = Print(problem, solutions);

            AssertAreEqual(@"
Constraints: {1, 2, 3}
Set 0: {1}
Set 1: {2}
Set 2: {3} [Clue]
Set 3: {2, 3}
Set 4: {1, 2}
Solutions: 2
Solution #1: {1}, {2}, {3}
Solution #2: {3}, {1, 2}", printed);
        }

 string Print(ExactCover problem, IReadOnlyCollection<ISet<int>> solutions)
        {
            var b = new StringBuilder();
            var i = 0;
            b.AppendLine($"Constraints: {Print(problem.Constraints)}");
            foreach (var set in problem.Sets)
            {
                var isClue = problem.Clues.Contains(set.Key);
                if (isClue)
                {
                    b.AppendLine($"Set {set.Key}: {Print(set.Value)} [Clue]");
                }
                else
                {
                    b.AppendLine($"Set {set.Key}: {Print(set.Value)}");
                }
            }
            b.AppendLine($"Solutions: {solutions.Count}");
            foreach (var solution in solutions)
            {
                b.AppendLine($"Solution #{++i}: {string.Join(", ", solution.OrderBy(_ => _).Select(s => Print(problem.Sets[s])))}");
            }
            return b.ToString();
        }

        string Print<T>(IEnumerable<T> set) => !set.Any() ? "Empty" : $"{{{string.Join(", ", set.OrderBy(_ => _))}}}";

        static string Normalize(string input) => Regex.Replace(input, @"s+", string.Empty);

        static void AssertAreEqual(string excepted, string actual) => Assert.AreEqual(Normalize(excepted), Normalize(actual));

public class Sudoku
{
    public void Solve(char[,] board)
    {
        var problem = Reduce(board);

        // The challenge allows us to assert a single solution is available
        var solution = problem.Solve(
            new DLX(), new SolverOptions { MaxSolutions = 1 }).Single();

        Augment(board, solution);
    }

    internal void Augment(char[,] board, ISet<int> solution)
    {
        var n2 = board.Length;
        var n = (int)Math.Sqrt(n2);

        foreach (var match in solution)
        {
            var row = match / (n * n);
            var column = match / n % n;
            var number = match % n;
            var symbol = Encode(number);

            board[row, column] = symbol;
        }
    }

    internal ExactCover Reduce(char[,] board)
    {
        var n2 = board.Length;
        var n = (int)Math.Sqrt(n2);
        var m = (int)Math.Sqrt(n);

        // The constraints for any regular Sudoku puzzle are:
        //  - For each row, a number can appear only once.
        //  - For each column, a number can appear only once.
        //  - For each region(small square), a number can appear only once.
        //  - Each cell can only have one number.

        // For 9x9 Sudoku, the binary matrix will have 4 x 9² columns.

        var constraints = new HashSet<int>(Enumerable.Range(0, 4 * n * n));

        // The sets for any regular Sudoku puzzle are all permutations of:
        //  - Each row, each column, each number

        // For 9x9 Sudoku, the binary matrix will have 9³ rows.

        var sets = new Dictionary<int, ISet<int>>();
        var clues = new HashSet<int>();

        foreach (var row in Enumerable.Range(0, n))
        {
            foreach (var column in Enumerable.Range(0, n))
            {
                var region = m * (row / m) + column / m;

                foreach (var number in Enumerable.Range(0, n))
                {
                    sets.Add((row * n + column) * n + number, new HashSet<int>
                    {
                        // number in row
                        row * n + number,
                        // number in column
                        (n + column) * n + number,
                        // number in region
                        (2 * n + region) * n + number,
                        // cell has number
                        (3 * n + row) * n + column
                    });
                }

                if (TryDecode(board[row, column], out var given))
                {
                    clues.Add((row * n + column) * n + given);
                }
            }
        }

        var problem = new ExactCover(constraints, sets, clues);

        return problem;
    }

    internal char Encode(int number) => (char)('1' + number);

    internal bool TryDecode(char symbol, out int number)
    {
        if (symbol == '.')
        {
            number = -1;
            return false;
        }

        number = symbol - '1';
        return true;
    }
}