4
\$\begingroup\$

This is a generic implementation of Knuth's "Algorithm X" using dancing links. The whole code with a "mandatory" sudoku solver can be found at gitlab.

Regarding the scope of the review, I am an experienced programmer and I think I "should" know what I am doing, therefore you should not consider any issue to be too small to mention. If you are a less experienced programmer and don't understand something in the code, that means the code is not good enough and you should consider bring it up.

The Code

In order to separate the constraint generation from the algorithm itself, the implementation uses a ColumnMapper. The column mapper provides the constraints that each value has. For example, in a sudoku solver the value would be "placing number 1 at column 3 in row 5" and the mapper returns the columns for constraints imposed by the sudoku column, row and box restrictions.

package fi.iki.asb.wheel.algorithm.dlx;

/**
 * Interface for mapping a value that represents a row in the
 * DLX matrix to indexes of columns where the value has constraints.
 */
@FunctionalInterface
public interface ColumnMapper<T> {

    /**
     * Get indexes of columns where the given value has constraints.
     * After all rows have been added to the DLX matrix, the column
     * indexes must form a single continuous series where all
     * columns have at least one constraint.
     *
     * @return Unique set of integers, sorted in ascending order.
     */
    int[] from(T rowValue);

}

The algorithm itself provides two public methods: addRow(...) for adding rows to the matrix and search(...) for searching for the solution. The search method requires a consumer that is used to deliver results to the caller and provides an option for an "emergecy brake" that can be used to stop the algorithm before it has completed the execution.

Please note that the abstract data types used are not part of the review. You should consider them to work as a data structure bearing it's name should. I may post a separate review for those later.

package fi.iki.asb.wheel.algorithm.dlx;

import fi.iki.asb.wheel.adt.IndexedCollection;
import fi.iki.asb.wheel.adt.Set;
import fi.iki.asb.wheel.adt.impl.ArrayBackedList;
import fi.iki.asb.wheel.adt.impl.HashSet;
import java.util.function.BooleanSupplier;
import java.util.function.Consumer;
import fi.iki.asb.wheel.adt.RandomAccessCollection;

/**
 * Generic implementation of Knuth's Algorithm X using dancing links.
 *
 * <p>This class is <i>not</i> thread safe.</p>
 *
 * @param <T> The type associated to constraints.
 */
public class DLX<T> {

    /**
     * A constraint node in the matrix.
     */
    private class Node {
        final Column column;
        final T value;
        Node up, down, left, right;

        Node(Column column, T value) {
            this.column = column;
            this.value = value;
            up = down = left = right = this;
        }
    }

    /**
     * Column header in the matrix.
     */
    private class Column extends Node {

        /**
         * Number of nodes in this column.
         */
        int size = 0;

        public Column() {
            super(null, null);
        }
    }

    // =================================================================== //

    private final ColumnMapper<T> columnMapper;

    private final Column head;

    private final ArrayBackedList<Column> columns;

    public DLX(ColumnMapper<T> columnMapper) {
        this.columnMapper = columnMapper;
        this.columns = new ArrayBackedList<>();
        
        head = new Column();
    }

    // =================================================================== //
    // Matrix initialization code.

    /**
     * Add a row with the given value.
     */
    public void addRow(T value) {
        // Needed to link nodes horizontally.
        Node previousNode = null;

        // Get relevant columns from the mapper.
        final int[] columns = columnMapper.from(value);
        for (int columnIndex: columns) {
            final Column column = getOrCreateColumn(columnIndex);
            final Node newNode = new Node(column, value);

            // Add new node to the column.
            newNode.down = column;
            newNode.up = column.up;
            column.up.down = newNode;
            column.up = newNode;
            column.size++;

            // Add new node to the row.
            if (previousNode != null) {
                newNode.right = previousNode;
                newNode.left = previousNode.left;
                previousNode.left.right = newNode;
                previousNode.left = newNode;
            }
            previousNode = newNode;
        }
    }

    /**
     * Create a new column with the given index. If the matrix does not yet
     * contain all columns preceding <code>columnIndex</code>, the missing
     * columns will be created.
     *
     * @param columnIndex Zero indexed column index.
     */
    private Column getOrCreateColumn(int columnIndex) {
        while (columns.size() <= columnIndex) {
            final Column newColumn = new Column();
            newColumn.left = head.left;
            newColumn.right = head;
            head.left.right = newColumn;
            head.left = newColumn;
            columns.add(newColumn);
        }

        return columns.get(columnIndex);
    }

    // =================================================================== //
    // The DLX solution.

    /**
     * Search for exact cover solution with no emergency brake.
     */
    public void search(
            RandomAccessCollection<T> initialSolution,
            Consumer<RandomAccessCollection<T>> solutionConsumer) {
        search(initialSolution, solutionConsumer, () -> false);
    }

    /**
     * Search for exact cover solution.
     *
     * @param initialSolution The row values that are known to be part
     *                        of the solution (for example the initial
     *                        numbers given in a sudoku puzzle). Can be
     *                        empty.
     * @param solutionConsumer The consumer which collects the results.
     * @param emergencyBrake A boolean supplier which is periodically
     *                       checked to prevent runaway execution. When
     *                       this supplier returns true, the execution
     *                       is stopped as soon as possible. This can be
     *                       used, for example, in conjunction with the
     *                       solutionConsumer to stop execution as soon
     *                       as a solution is found or to check if runtime
     *                       limit has been exceeded.
     */
    public void search(
            RandomAccessCollection<T> initialSolution,
            Consumer<RandomAccessCollection<T>> solutionConsumer,
            BooleanSupplier emergencyBrake) {

        // Find the distinct set of columns that have constraints
        // that conflict with the initial solution and cover them.
        final IndexedCollection<Integer> hiddenColumns =
                collectHiddenColumns(initialSolution);
        for (int i = 0; i < hiddenColumns.size(); i++) {
            Column column = columns.get(hiddenColumns.get(i));
            cover(column);
        }

        final IndexedCollection<T> solution = new ArrayBackedList<>();
        solution.addAll(initialSolution);

        recursiveSearch(solution, solutionConsumer, emergencyBrake);

        // Uncover the initial hidden columns in reverse order to
        // restore the matrix to original state.
        for (int i = hiddenColumns.size() - 1; i >= 0; i--) {
            Column column = columns.get(hiddenColumns.get(i));
            uncover(column);
        }
    }

    private void recursiveSearch(
            IndexedCollection<T> solution,
            Consumer<RandomAccessCollection<T>> solutionConsumer,
            BooleanSupplier emergencyBrake) {

        // If there are no uncovered columns, the list contains a solution.
        if (head.right == head) {
            solutionConsumer.accept(solution);
            return;
        }

        if (emergencyBrake.getAsBoolean()) {
            return;
        }

        // Select and cover column.
        final Column column = findColumn();
        cover(column);

        // For each row that has a constraint in this column, add the
        // row value to the result, cover all columns that are in conflict
        // with this row constraint and recurse.
        for (Node n0 = column.down; n0 != column; n0 = n0.down) {
            solution.add(n0.value);
            for (Node n1 = n0.right; n1 != n0; n1 = n1.right) {
                cover(n1.column);
            }

            recursiveSearch(solution, solutionConsumer, emergencyBrake);

            // Uncover changes made before recursion.
            for (Node n1 = n0.left; n1 != n0; n1 = n1.left) {
                uncover(n1.column);
            }
            solution.removeAt(solution.size() - 1);

            if (emergencyBrake.getAsBoolean()) {
                break;
            }
        }

        uncover(column);
    }

    private void cover(Column column) {
        column.left.right = column.right;
        column.right.left = column.left;

        for (Node i = column.down; i != column; i = i.down) {
            for (Node j = i.right; j != i; j = j.right) {
                j.down.up = j.up;
                j.up.down = j.down;
                j.column.size--;
            }
        }
    }

    private void uncover(Column column) {
        for (Node i = column.up; i != column; i = i.up) {
            for (Node j = i.left; j != i; j = j.left) {
                j.column.size++;
                j.down.up = j;
                j.up.down = j;
            }
        }

        column.right.left = column;
        column.left.right = column;
    }

    /**
     * Find an uncovered column with the smallest non-zero number of
     * constraints.
     */
    private Column findColumn() {
        Column smallest = null;
        Column candidate = (Column) head.right;
        while (candidate != head) {
            if (candidate.size == 0) {
                continue;
            }

            if (candidate.size == 1) {
                return candidate;
            }

            if (smallest == null || smallest.size > candidate.size) {
                smallest = candidate;
            }

            candidate = (Column) candidate.right;
        }

        return smallest;
    }

    /**
     * Collect hidden columns from the initial solution.
     */
    private IndexedCollection<Integer> collectHiddenColumns(
            RandomAccessCollection<T> initialSolution) {

        // Gather columns that should be hidden.
        final Set<Integer> temp = new HashSet<>();
        initialSolution.forEach(t -> {
            for (int columnIndex: columnMapper.from(t)) {
                temp.put(columnIndex);
            }
            return true;
        });
        final IndexedCollection<Integer> hiddenColumns =
                new ArrayBackedList<>(temp.size());
        hiddenColumns.addAll(temp);
        return hiddenColumns;
    }
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I suggest you declare Node and Column as static final. static will remove an implicit reference to a an enclosing object from each Node and Column thus saving some space. \$\endgroup\$
    – coderodde
    Dec 19, 2023 at 11:55

1 Answer 1

1
\$\begingroup\$
// If there are no uncovered columns, the list contains a solution.
if (head.right == head) {
    solutionConsumer.accept(solution);
    return;
}

Having a dummy column header for the "header of the whole matrix" is completely normal in DLX, but it's easy to forget at this point in the code that that's what's going on. That could be noted here (and in findColumn where starting at head.right looks mysterious without this context).

I noticed that findColumn ignores/skips columns with a size of zero. Encountering an empty column means that the current problem is unsoveable, so I expected that condition to be detected and reported to recursiveSearch so that it can backtrack, rather than recurse into subproblems that will also be unsolveable. findColumn can also return null if there is no non-empty column, and recursiveSearch does not handle that gracefully. It seems to me that you can remove the special case for size == 0, then findColumn would return an empty column if one exists, and recursiveSearch does handle that.

cover and uncover are unexplained, those node manipulations may not be obvious to the general public.

\$\endgroup\$
1
  • \$\begingroup\$ Good points, that column selection was a bug. \$\endgroup\$ Dec 20, 2023 at 6:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.