LeetCode #37: Sudoku as Exact Cover Problem solved using Dancing Links

Question

Introduction

I provide a regular 9x9 Sudoku solver, reducing the puzzle to an Exact Cover Problem. The algorithm used is Knuth's Algorithm X as implemented using Dancing Links (DLX). As I found no such solving technique on Code Review written in C#, I took up the challenge to have a go at it.

^{The problem definitions and used algorithms are behind links because it takes a lot of reading to understand these concepts.}

---

Challenge Description

This is a LeetCode challenge: #37 - Sudoku Solver.

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

• Each of the digits 1-9 must occur exactly once in each row.
• Each of the digits 1-9 must occur exactly once in each column.
• Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
• Empty cells are indicated by the character '.'.

---

Goal

I'll first show the unit test that solves a board, before presenting a bottom-up presentation to come to this solution. Next steps include exact cover -> dancing links -> sudoku solver.

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

---

Exact Cover

An Exact Cover Problem is a specific type of Constaint Satisfaction Problem where all constraints have to be met, and no constraint can be met more than once. Each set is a collection of candidate constraints. Finding a solution requires to find combinations of sets that meet all the constraints.

I need some configurable options, since consumers may decide how many solutions should be probed for. For instance, if you need a unique solution, search for 2 solutions and if the solver found only one, you know it's the unique solution.

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

Any solver implementation must implement the interface. Given a problem and some options, one or more solutions are probed for. Each solution is a set containing the id's of the initial sets used to meet the requirements.

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

The problem's state is stored.

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

---

Dancing Links

Dancing links implements a fast algorithm for solving an exact cover problem. It works on a circular bi-directional doubly linked list, which also happens to be a sparse matrix.

To accomplish such Toroidal Matrix structure, we require a node.

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

And the implementation of the DLX solver.

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

These unit tests should give you an idea how the algorithm can be used for trivial problems.

        [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));

---

Sudoku Solver

As a final step, we reduce a Sudoku board to a DLX matrix, solve it and map the data back to the Sudoku board. The format chosen corresponds to the challenge.

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

---

Questions

• Usability: can this code be reused for different variants of the puzzle?
• Usability: can this code be reused for different problems such as the n queen problem?
• Performance: can this algorithm be improved for performance
• General coding guidelines

Answer 1

SolverOptions

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

Instead of using undocumented magic values, why not use uint??

I'm not sure what MaxRecursion gains you. IMO it would be more useful to have a progress report and a way to cancel the search.

---

    public bool IncludeCluesInSolution = false;

What's a "clue" in a general exact cover problem? I think this is at the wrong level of abstraction.

---

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

Ugh. This either forces you to evaluate the solution set multiple times (if it's lazy) or it forces you to use a non-lazy IEnumerable, which means caching the full solution set in memory. IMO it would be far preferable for the searcher to return a lazy enumeration and simply keep count of the solutions returned and compare the count to MaxSolutions. Alternatively, and this is what I did with my Java implementation many years ago, the search could take a callback which accepts the solution and returns a bool indicating whether to continue searching.

---

ICSPSolver

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

I'm not convinced by the name. There are constraint satisfaction problems which can't be reduced to exact cover.

See my comments above on preferring to return a lazy IEnumerable, which would mean changing the return type here.

---

ExactCover

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

Why int? Knuth writes in a context in which everything is described in a fairly minimalist imperative language from the 1970s, but this code is in a modern polymorphic language. I would be strongly inclined to make the universe a type parameter, and then if the caller wants to number the elements of the universe and work with ints for speed of comparisons then let them, but don't make it obligatory.

For my taste the properties should all have read-only types. It is unfortunate that .Net doesn't have an IReadOnlySet<T>: I consider that it's worth writing one, and a read-only wrapper for ISet<T>.

I am baffled as to what the three properties represent. As far as I'm concerned the absolutely necessary component of an exact cover problem is an IEnumerable<IEnumerable<TUniverse>> representing the subsets; and the other, optional, component is an IEnumerable<TUniverse> to detect the case where the union of the subsets is missing one or more elements.

---

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

There's always a case to be made for copying your inputs to prevent the caller mutating them.

---

DLXNode

class DLXNode
{
    internal DLXNode header, row;
    internal DLXNode up, down, left, right;

See previous comments on using a modern language. I don't believe that it's necessary to manually implement the linked lists of Knuth's description, and by delegating that kind of thing to the library you can save yourself a lot of pain debugging.

---

DLX

public class DLX : ICSPSolver
{
    public IReadOnlyCollection<ISet<int>> Solve(ExactCover problem, SolverOptions options)
    {
        var root = Parse(problem);

I'm intrigued by the name. To me, Parse means transforming a string into the thing it represents. What does it mean to you?

---

    internal bool CheckForSolution(
    internal DLXNode GetHeaderWithMinimumRowCount(DLXNode root)
    internal void Explore(
    internal void Cover(DLXNode node)
    internal void Uncover(DLXNode node)
    internal DLXNode Parse(ExactCover problem)

These could, and therefore should, all be static.

---

                var solution = new HashSet<int>(currentSolution);
                if (options.IncludeCluesInSolution)
                {
                    foreach (var clue in clues)
                    {
                        solution.Add(clue);
                    }
                }

solution.UnionWith(clues) would be more elegant.

---

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

Among the obviously useful things lacking from Linq is a function public static TSource MinBy<TSource, TValue>(this IEnumerable<TSource> elts, Func<TSource, TValue> valuation) where TValue : IComparable<TValue>. I heartily recommend that you factor this function out of GetHeaderWithMinimumRowCount and add it to your utility library.

---

        foreach (var constraint in problem.Constraints.Where(x => !givens.Contains(x)))

problem.Constraints.Except(givens).