An implementation of Knuth's Algorithm X and Dancing Linked List with Rust.

algo_x.rs

pub fn algorithm_x(
    list: &mut DancingLinkedList,
    stack: &mut Vec<usize>,
    solutions: &mut Vec<Vec<usize>>,
) {
    if list.is_empty() {
        solutions.push(stack.clone());
        return;
    }

    list.split_rows_by_minimal_columns(|picking_row, residential| {
        stack.push(picking_row.column_idx().unwrap());
        algorithm_x(residential, stack, solutions);
        stack.pop();
    });
}

dancing_linked_list.rs

use std::marker::{PhantomData, PhantomPinned};
use std::pin::Pin;
use std::ptr::NonNull;
use std::{borrow::BorrowMut, cell::Cell};

/// An implementation of [dancing linked list](https://arxiv.org/pdf/cs/0011047).
///
/// This cannot be shared it with other threads (!Sync).
pub struct DancingLinkedList {
    original_column_len: usize,
    master: Pin<Box<Node>>,
    node_arena: Pin<Box<[Node]>>,
}

pub struct Node {
    left: NonNull<Node>,
    right: NonNull<Node>,
    up: NonNull<Node>,
    down: NonNull<Node>,
    info: NodeInfo,
    _phantom: (PhantomData<Cell<u8>>, PhantomPinned),
}

#[derive(Debug)]
pub enum NodeInfo {
    Master,
    Header {
        column_len: usize,
        label: usize,
    },
    Leaf {
        column: NonNull<Node>,
        column_idx: usize,
        label: usize,
    },
}

#[derive(Clone)]
pub struct NodeRow<'a> {
    head: Option<NonNull<Node>>,
    tail: Option<NonNull<Node>>,
    _phantom: PhantomData<&'a DancingLinkedList>,
}

pub struct NodeRowMut<'a> {
    head: Option<NonNull<Node>>,
    tail: Option<NonNull<Node>>,
    _phantom: PhantomData<&'a mut DancingLinkedList>,
}

#[derive(Clone)]
pub struct NodeColumn<'a> {
    head: Option<NonNull<Node>>,
    tail: Option<NonNull<Node>>,
    _phantom: PhantomData<&'a DancingLinkedList>,
}

pub struct NodeColumnMut<'a> {
    head: Option<NonNull<Node>>,
    tail: Option<NonNull<Node>>,
    _phantom: PhantomData<&'a mut DancingLinkedList>,
}

impl std::fmt::Debug for DancingLinkedList {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
        let width = {
            let mut count = 0;
            let mut acc = self.original_column_len - 1;
            while acc > 0 {
                acc /= 10;
                count += 1;
            }
            count
        };
        writeln!(f, "GRID:")?;
        for i in 0..self.original_column_len {
            if i != 0 {
                writeln!(f)?;
            }
            write!(f, "{i:0width$} ", width = width)?;
            for column_head in self.headers() {
                let mut found = false;
                for node in column_head.same_column() {
                    if node.column_idx() == Some(i) {
                        write!(f, "X")?;
                        found = true;
                        break;
                    }
                }
                if !found {
                    write!(f, " ")?;
                }
            }
        }
        writeln!(f)?;
        writeln!(f, "COLUMNS:")?;
        for header in self.headers() {
            if let NodeInfo::Header { column_len, label } = header.info() {
                writeln!(f, "{label} has {column_len} bits")?;
            }
        }
        Ok(())
    }
}

impl DancingLinkedList {
    pub fn new() -> Self {
        Self {
            original_column_len: 0,
            master: Box::pin(Node::master()),
            node_arena: Box::pin([]),
        }
    }

    /// Constructs a new dancing linked list from the connection matrix.
    pub fn from_connections(matrix: &[Vec<bool>]) -> Self {
        let column_len = matrix.len();
        let row_len = matrix.iter().map(|row| row.len()).max().unwrap_or(0);

        if row_len == 0 || column_len == 0 {
            return Self::new();
        }

        let mut master = Box::new(Node::master());
        let master_ptr = NonNull::new(&mut *master as *mut _).unwrap();
        master.up = master_ptr;
        master.down = master_ptr;
        master.left = master_ptr;
        master.right = master_ptr;

        let mut node_arena = Vec::with_capacity((column_len + 1) * row_len);

        // Construct uninitialized headers and link between
        for j in 0..row_len {
            node_arena.push(Node::dangling());
            let ref_mut = &mut node_arena[j];
            let ptr: NonNull<_> = ref_mut.into();
            ref_mut.info = NodeInfo::Header {
                column_len: 0,
                label: j,
            };
            ref_mut.up = ptr;
            ref_mut.down = ptr;
            ref_mut.left = ptr;
            ref_mut.right = ptr;
        }
        unsafe {
            connect_left_right(master.as_mut().into(), node_arena[0].borrow_mut().into());
            connect_left_right(
                node_arena[row_len - 1].borrow_mut().into(),
                master.as_mut().into(),
            );
        }
        for j in 1..row_len {
            unsafe {
                connect_left_right(
                    node_arena[j - 1].borrow_mut().into(),
                    node_arena[j].borrow_mut().into(),
                );
            }
        }

        // Construct uninitialized nodes and link header
        for i in 0..column_len {
            for j in 0..row_len {
                node_arena.push(Node::dangling());
                let (headers, leaves) = node_arena.split_at_mut(row_len);
                let column_ptr = headers[j].borrow_mut().into();
                let ref_mut = &mut leaves[i * row_len + j];
                let ptr: NonNull<_> = ref_mut.into();
                ref_mut.up = ptr;
                ref_mut.down = ptr;
                ref_mut.left = ptr;
                ref_mut.right = ptr;

                if matrix[i][j] {
                    ref_mut.info = NodeInfo::Leaf {
                        column: column_ptr,
                        column_idx: i,
                        label: j,
                    };
                    unsafe {
                        // SAFETY: The element will not be relocated.
                        Pin::new_unchecked(&mut headers[j]).increment_column_len();
                    }
                }
            }
        }
        // Link between horizontally
        for i in 0..column_len {
            let mut first_found = None;
            let mut last_found: Option<NonNull<Node>> = None;
            for j in 0..row_len {
                if matrix[i][j] {
                    let current: NonNull<_> = (&mut node_arena[(i + 1) * row_len + j]).into();
                    if let Some(last) = last_found {
                        unsafe {
                            connect_left_right(last, current);
                        }
                    }
                    if first_found.is_none() {
                        first_found = Some(current);
                    }
                    last_found = Some(current);
                }
            }
            if let Some((first, last)) = first_found.zip(last_found) {
                unsafe {
                    connect_left_right(last, first);
                }
            }
        }
        // Link between vertically
        for j in 0..row_len {
            let mut first_found = None;
            let mut last_found: Option<NonNull<Node>> = None;
            for i in 0..column_len {
                if matrix[i][j] {
                    let current = (&mut node_arena[(i + 1) * row_len + j]).into();
                    if let Some(last) = last_found {
                        unsafe {
                            connect_up_down(last, current);
                        }
                    }
                    if first_found.is_none() {
                        first_found = Some(current);
                    }
                    last_found = Some(current);
                }
            }
            if let Some((first, last)) = first_found.zip(last_found) {
                unsafe {
                    connect_up_down(last, node_arena[j].borrow_mut().into());
                    connect_up_down(node_arena[j].borrow_mut().into(), first);
                }
            }
        }

        Self {
            original_column_len: matrix.len(),
            master: Box::into_pin(master),
            node_arena: Box::into_pin(node_arena.into_boxed_slice()),
        }
    }

    pub fn into_nodes(self) -> Pin<Box<[Node]>> {
        self.node_arena
    }

    pub fn len(&self) -> usize {
        self.headers().count()
    }

    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    pub fn row_len(&self) -> usize {
        self.headers().count()
    }

    pub fn column_len(&self) -> usize {
        self.master.as_ref().column_len()
    }

    /// Creates an iterator that retrieves columns.
    pub fn headers(&self) -> NodeRow {
        NodeRow {
            head: Some(self.master.right),
            tail: Some(self.master.left),
            _phantom: PhantomData,
        }
    }

    /// Creates an iterator that retrieves columns.
    pub fn headers_mut(&mut self) -> NodeRowMut {
        NodeRowMut {
            head: Some(self.master.right),
            tail: Some(self.master.left),
            _phantom: PhantomData,
        }
    }

    /// Finds a column which has the minimal connections.
    fn minimal_column(&mut self) -> Option<Pin<&mut Node>> {
        let mut min_len = usize::MAX;
        for header in self.headers() {
            if let &NodeInfo::Header { column_len, .. } = header.info() {
                min_len = min_len.min(column_len);
            }
        }
        self.headers_mut()
            .filter(move |header| {
                if let NodeInfo::Header { column_len, .. } = header.info() {
                    *column_len == min_len
                } else {
                    false
                }
            })
            .next()
    }

    /// Splits the list into tuples of row and residual by minimal columns. Panicking `body` can break some links of nodes (but memory-safe).
    pub fn split_rows_by_minimal_columns(
        &mut self,
        mut body: impl FnMut(Pin<&mut Node>, &mut Self),
    ) {
        let this = self as *mut DancingLinkedList;
        if let Some(min_column_head) = self.minimal_column() {
            for mut picking_row in min_column_head
                .same_column_mut()
                .filter(|cell| cell.is_leaf())
            {
                for picked in picking_row.as_mut().same_row_mut() {
                    picked.remove_column();
                }
                let column_len = picking_row.as_ref().column_len();
                picking_row.as_mut().remove_row();

                unsafe {
                    // SAFETY: `picking_row` is splitted from `self` safely. It cannot be sought from `self` now.
                    // FIXME: Seeking from `picking_row` may occur unsoundness. More inspection needed.
                    body(picking_row.as_mut(), &mut *this);
                }

                picking_row.as_mut().restore_row();
                for picked in picking_row.as_mut().same_row_mut() {
                    picked.restore_column();
                }
                debug_assert_eq!(column_len, picking_row.as_ref().column_len());
            }
        }
    }
}

impl std::fmt::Debug for Node {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_tuple("Node").field(&self.info).finish()
    }
}

impl Node {
    fn master() -> Self {
        Self {
            left: NonNull::dangling(),
            right: NonNull::dangling(),
            up: NonNull::dangling(),
            down: NonNull::dangling(),
            info: NodeInfo::Master,
            _phantom: (PhantomData, PhantomPinned),
        }
    }

    fn dangling() -> Self {
        Self {
            left: NonNull::dangling(),
            right: NonNull::dangling(),
            up: NonNull::dangling(),
            down: NonNull::dangling(),
            info: NodeInfo::Leaf {
                column: NonNull::dangling(),
                column_idx: usize::MAX,
                label: usize::MAX,
            },
            _phantom: (PhantomData, PhantomPinned),
        }
    }

    pub const fn info(&self) -> &NodeInfo {
        &self.info
    }

    pub fn column_idx(&self) -> Option<usize> {
        if let NodeInfo::Leaf { column_idx, .. } = self.info {
            Some(column_idx)
        } else {
            None
        }
    }

    pub fn label(&self) -> Option<usize> {
        if let NodeInfo::Leaf { label, .. } = self.info {
            Some(label)
        } else {
            None
        }
    }

    pub const fn is_master(&self) -> bool {
        matches!(self.info, NodeInfo::Master)
    }

    pub const fn is_leaf(&self) -> bool {
        matches!(self.info, NodeInfo::Leaf { .. })
    }

    fn column_len(self: Pin<&Self>) -> usize {
        match self.info {
            NodeInfo::Master => self
                .as_ref()
                .same_row()
                .filter(|node| !node.is_master())
                .map(|node| node.as_ref().column_len())
                .max()
                .unwrap_or(0),
            NodeInfo::Header { column_len, .. } => column_len,
            NodeInfo::Leaf { column, .. } => unsafe {
                Pin::new_unchecked(column.as_ref()).column_len()
            },
        }
    }

    fn increment_column_len(self: Pin<&mut Self>) {
        match unsafe { &mut *self.map_unchecked_mut(|this| &mut this.info) } {
            NodeInfo::Master => {}
            NodeInfo::Header { column_len, .. } => {
                *column_len += 1;
            }
            NodeInfo::Leaf { column, .. } => unsafe {
                Pin::new_unchecked(column.as_mut()).increment_column_len();
            },
        }
    }

    fn decrement_column_len(self: Pin<&mut Self>) {
        match unsafe { &mut *self.map_unchecked_mut(|this| &mut this.info) } {
            NodeInfo::Master => {}
            NodeInfo::Header { column_len, .. } => {
                *column_len -= 1;
            }
            NodeInfo::Leaf { column, .. } => unsafe {
                Pin::new_unchecked(column.as_mut()).decrement_column_len();
            },
        }
    }

    /// Returns whether there is only this node in the belonging row.
    pub fn is_single_in_row(self: Pin<&Self>) -> bool {
        let this: NonNull<_> = (&*self).into();
        // SAFETY: right is always valid.
        self.left == self.right
            && (self.right == this || unsafe { self.right.as_ref().is_master() })
    }

    /// Returns whether there is only this node in the belonging column.
    pub fn is_single_in_column(self: Pin<&Self>) -> bool {
        let this: NonNull<_> = (&*self).into();
        // SAFETY: down is always valid.
        self.up == self.down && (self.down == this || unsafe { self.down.as_ref().is_master() })
    }

    /// Constructs an iterator which retrieves nodes on the same column.
    pub fn same_column(self: Pin<&Self>) -> NodeColumn {
        NodeColumn {
            head: Some((&*self).into()),
            tail: Some(self.up),
            _phantom: PhantomData,
        }
    }

    /// Constructs an iterator which retrieves nodes on the same column.
    pub fn same_column_mut(self: Pin<&mut Self>) -> NodeColumnMut {
        let tail = self.up;
        let head = unsafe { NonNull::new_unchecked(Pin::into_inner_unchecked(self) as *mut Node) };
        NodeColumnMut {
            head: Some(head),
            tail: Some(tail),
            _phantom: PhantomData,
        }
    }

    /// Constructs an iterator which retrieves nodes on the same row.
    pub fn same_row(self: Pin<&Self>) -> NodeRow {
        NodeRow {
            head: Some((&*self).into()),
            tail: Some(self.left),
            _phantom: PhantomData,
        }
    }

    /// Constructs an iterator which retrieves nodes on the same row.
    pub fn same_row_mut(self: Pin<&mut Self>) -> NodeRowMut {
        let tail = self.left;
        let head = unsafe { NonNull::new_unchecked(Pin::into_inner_unchecked(self) as *mut Node) };
        NodeRowMut {
            head: Some(head),
            tail: Some(tail),
            _phantom: PhantomData,
        }
    }

    /// Removes a row which the data belonging to.
    pub fn remove_row(self: Pin<&mut Self>) {
        if !self.is_leaf() {
            return;
        }
        for mut cell in self.same_row_mut() {
            cell.as_mut().decrement_column_len();
            unsafe {
                // SAFETY: `up` and `down` are always valid.
                connect_up_down(cell.as_ref().up, cell.as_ref().down);
            }
        }
    }

    /// Restores a row which the data belonging to.
    pub fn restore_row(self: Pin<&mut Self>) {
        if !self.is_leaf() {
            return;
        }
        for mut cell in self.same_row_mut() {
            unsafe {
                // SAFETY: `cell`, `up` and `down` are always valid.
                let target: NonNull<_> =
                    NonNull::new_unchecked(Pin::into_inner_unchecked(cell.as_mut()) as *mut Node);
                connect_up_down(target.as_ref().up, target);
                connect_up_down(target, target.as_ref().down);
            }
            cell.as_mut().increment_column_len();
        }
    }

    /// Removes a column which the data belonging to.
    pub fn remove_column(self: Pin<&mut Self>) {
        if self.is_master() {
            return;
        }
        for cell in self.same_column_mut() {
            unsafe {
                // SAFETY: `left` and `right` are always valid.
                connect_left_right(cell.as_ref().left, cell.as_ref().right);
            }
        }
    }

    /// Restores a column which the data belonging to.
    pub fn restore_column(self: Pin<&mut Self>) {
        if self.is_master() {
            return;
        }
        for mut cell in self.same_column_mut() {
            unsafe {
                // SAFETY: `cell`, `up` and `down` are always valid.
                let target: NonNull<_> =
                    NonNull::new_unchecked(Pin::into_inner_unchecked(cell.as_mut()) as *mut Node);
                connect_left_right(cell.as_ref().left, target);
                connect_left_right(target, cell.as_ref().right);
            }
        }
    }
}

/// Connects nodes vertically. It makes that `up` points `down` as its downward and `down` points `up` as its upward.
///
/// # Safety
///
/// Each of `up` and `down` must refer valid `Node` object.
unsafe fn connect_up_down(mut up: NonNull<Node>, mut down: NonNull<Node>) {
    up.as_mut().down = down;
    down.as_mut().up = up;
}

/// Connects node horizontally. It makes that `left` points `right` as its right-side and `right` points `left` as its left-side.
///
/// # Safety
///
/// Each of `left` and `right` must refer valid `Node` object.
unsafe fn connect_left_right(mut left: NonNull<Node>, mut right: NonNull<Node>) {
    left.as_mut().right = right;
    right.as_mut().left = left;
}

impl<'a> Iterator for NodeColumn<'a> {
    type Item = Pin<&'a Node>;

    fn next(&mut self) -> Option<Self::Item> {
        let head = self.head?;
        // SAFETY: The substance of `head` is stored in the arena.
        let head = unsafe { Pin::new_unchecked(head.as_ref()) };
        if head.is_master() && unsafe { head.down.as_ref().is_master() } {
            self.head = None;
            self.tail = None;
            return None;
        }
        if head.is_single_in_column() {
            self.head = None;
            return Some(head);
        }
        let next = unsafe {
            let down = head.as_ref().down;
            if down.as_ref().is_master() {
                down.as_ref().down
            } else {
                down
            }
        };
        if self.tail == self.head {
            self.head = None;
        } else {
            self.head = Some(next);
        }
        Some(head)
    }
}

impl std::iter::FusedIterator for NodeColumn<'_> {}

impl<'a> Iterator for NodeColumnMut<'a> {
    type Item = Pin<&'a mut Node>;

    fn next(&mut self) -> Option<Self::Item> {
        let mut head = self.head?;
        // SAFETY: The substance of `head` is stored in the arena.
        let head = unsafe { Pin::new_unchecked(head.as_mut()) };
        if head.is_master() && unsafe { head.down.as_ref().is_master() } {
            self.head = None;
            self.tail = None;
            return None;
        }
        if head.as_ref().is_single_in_column() {
            self.head = None;
            return Some(head);
        }
        let next = unsafe {
            let down = head.as_ref().down;
            if down.as_ref().is_master() {
                down.as_ref().down
            } else {
                down
            }
        };
        if self.tail == self.head {
            self.head = None;
        } else {
            self.head = Some(next);
        }
        Some(head)
    }
}

impl std::iter::FusedIterator for NodeColumnMut<'_> {}

impl<'a> Iterator for NodeRow<'a> {
    type Item = Pin<&'a Node>;

    fn next(&mut self) -> Option<Self::Item> {
        let head = self.head?;
        // SAFETY: The substance of `head` is stored in the arena.
        let head = unsafe { Pin::new_unchecked(head.as_ref()) };
        if head.is_master() && unsafe { head.right.as_ref().is_master() } {
            self.head = None;
            self.tail = None;
            return None;
        }
        if head.as_ref().is_single_in_column() {
            self.head = None;
            return Some(head);
        }
        let next = unsafe {
            let right = head.as_ref().right;
            if right.as_ref().is_master() {
                right.as_ref().right
            } else {
                right
            }
        };
        if self.tail == self.head {
            self.head = None;
        } else {
            self.head = Some(next);
        }
        Some(head)
    }
}

impl std::iter::FusedIterator for NodeRow<'_> {}

impl<'a> Iterator for NodeRowMut<'a> {
    type Item = Pin<&'a mut Node>;

    fn next(&mut self) -> Option<Self::Item> {
        let mut head = self.head?;
        // SAFETY: The substance of `head` is stored in the arena.
        let head = unsafe { Pin::new_unchecked(head.as_mut()) };
        if head.is_master() && unsafe { head.right.as_ref().is_master() } {
            self.head = None;
            self.tail = None;
            return None;
        }
        if head.as_ref().is_single_in_column() {
            self.head = None;
            return Some(head);
        }
        let next = unsafe {
            let right = head.as_ref().right;
            if right.as_ref().is_master() {
                right.as_ref().right
            } else {
                right
            }
        };
        if self.tail == self.head {
            self.head = None;
        } else {
            self.head = Some(next);
        }
        Some(head)
    }
}

impl std::iter::FusedIterator for NodeRowMut<'_> {}

example.rs

fn example() {
    let mut mat = DancingLinkedList::from_connections(&[
        vec![true, false, false, true, false, false, true],
        vec![true, false, false, true, false, false, false],
        vec![false, false, false, true, true, false, true],
        vec![false, false, true, false, true, true, false],
        vec![false, true, true, false, false, true, true],
        vec![false, true, false, false, false, false, true],
    ]);

    let mut ans = vec![];
    algorithm_x(&mut mat, &mut vec![], &mut ans);
    println!("answer: {ans:#?}");
}