Introduction to Dance Chain (DLX)

Name:

$DL$，$Dancing\space Link$The dance chain, which is made up of$Donald\space Knuth$The proposed data structure for optimizing$X$ algorithm, so called$DLX$

$X$algorithm detailing

for solving exact coverage problems.Definition of the precise coverage problem: Given a matrix consisting of 0-1, is it possible to find a set of rows such that each column in the set contains exactly one 1

Example:

as$A,B,C \subseteq S$

$A \space \cap \space B= Ø$，$A \space \cup \space B=S$，then the set (math.)$A,B$It's a solution to a problem.

$X$Algorithms to solve simulations:

matrix matrix (math.)$A$

\[A=\left( \begin{matrix} 0&0&1&0&1&1&0\\1&0&0&1&0&0&1\\0&1&1&0&0&1&0\\1&0&0&1&0&0&0\\0&1&0&0&0&0&1\\0&0&0&1&1&0&1 \end{matrix} \right) \]

Select the first column:

\[\left( \begin{matrix} 0&0&1&0&1&1&0\\\\\\\\\\ \end{matrix} \right) \]

would have$1$of the column extends downward, if the row has the$1$, mark the line, process the$A$matrix to obtain$B$matrices

\[B=\left( \begin{matrix} 0&0&1&0&1&1&0\\&&0&&0&0\\0&1&1&0&0&1&0\\&&0&&0&0\\&&0&&0&0\\0&0&0&1&1&0&1 \end{matrix} \right) \]

$S matrix = A matrix - B matrix$(Delete marked rows and columns)

\[A_1=\left( \begin{matrix} 1&0&1&1\\1&0&1&0\\0&1&0&1 \end{matrix} \right) \]

Select the first column again

\[\left( \begin{matrix} 1&0&1&1\\\\\\ \end{matrix} \right) \]

marking

\[B_1= \left( \begin{matrix} 1&0&1&1\\1&&1&0\\0&1&0&1 \end{matrix} \right) \]

The new matrix is obtained, which in turn leads to an exact coverage problem of smaller size

\[S_1= \left( \begin{matrix} 0 \end{matrix} \right) \]

discoveries$A$The matrix is not empty and none of the columns have$1$(unable to proceed)

look back upon

\[A_1=\left( \begin{matrix} 1&0&1&1\\1&0&1&0\\0&1&0&1 \end{matrix} \right) \]

Can't try the first line, mark the second line and try to continue the expansion

\[B_2= \left( \begin{matrix} 1&0&1&1\\1&0&1&0\\0&&0 \end{matrix} \right) \]

The same reasoning leads to

\[A_3= \left( \begin{matrix} 1&1 \end{matrix} \right) \]

$A_3$Only$1$rows, and all of them$1$Select this line and the problem will be solved

Therefore, the solution of the problem is the matrix$A$The first row in the matrix$A_1$Fourth periodic report of the Secretary-General$2$Row, Matrix$A_3$The first row of the matrix$A$Fourth periodic report of the Secretary-General$1、4、5$classifier for objects in rows such as words

Back to the point, what is DLX again?

Introducing DL, Dance Chain

Build something like thisCross-crossed cyclic bi-directional chain，Yes, only for those who have$1$The connected edges of this graph correspond to the matrices$A$

gainElement, i.e. element$C1$Labeling elements$C1$violet (color)

Try the line first.$2$The following elements in the row are labeled with the$Element 5 and Element 6$The first element of the column in which it is located is orange, i.e., the element$C4$and elements$C7$

Remove the orange portion and the purple portion and the rest is as shown in the picture

gainElement, i.e. element$C2$Labeling elements$C2$violet (color)

columns$C2$Only elements$7$Override, so the answer can only choose the line$3$

select line$3$, and by the same token, the labeling element$C3$and labeling elements$C6$orange

Remove and get

No element can cover the$C5$, stating that the solution failed, backtracking

Returns the first element of the column in the reverse order of the labeled elementsi.e. return column header C6, return column header C3, return column header C2, return column header C7, return column header C4

Therefore, you can't choose a line$2$Try the line.$4$, and by the same token, the labeling element$C4$orange

Remove and get

gainElement, labeling element$C2$violet (color)

select line$3$, and by the same token, the labeling element$C3$cap (a poem)$C6$orange

Similarly, we have

Similarly, backtrackingThe return column header C6, return column header C3.

This choice of line$5$Labeling elements$C7$orange

Remove and get

gainElement, labeling element$C3$violet (color)

Only elements$1$Override, so the answer can only choose the line$3$, and by the same token, the labeling element$C5$and elements$C6$orange

Remove and get

on account of$=head$, so the solution is over and the answers in the answer stack are$4、5、1$, which means that the solution to the problem is the first$4、5、1$The rows cover all the columns, i.e. the blue part of the picture below

summarize$Dancing Links$solution (math.)

function entry
Judgment $ \space ? = head $, if true, output answer, return solved, exit function
attainmentparticular element$C$
identifying element$C$
Acquisition of elements$C$An element of the column in which
The column header element that identifies the other elements in the same row as this element.
Get a simplified problem, recursively, and exit the function if it returns solved
If what you've just tried doesn't work, return the first element of the column where the other elements in the same row are located, in the reverse order of the previous labels.
Acquisition of elements$C$the next element in the column where it is located, and if so, jump to "the first element of the column labeled with the name of the other element in the same row as this element".
If not, the return element$C$, return unresolved, exit function

Example P4929

code implementation

#include"bits/stdc++.h"
using namespace std;
const int N=250015;//N*M
#define inl inline
#define reg register
#define regi register int
#define PII pair<int,int>
inl int read(void)
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x*f;
}
int l[N],r[N],up[N],down[N],col[N],row[N];//Left, right, up and down pointers for each point，and the rows and columns in which each point is located
int head[N];int sz[N];//Header nodes for each row,Number of nodes per column
int ans[N];//answer stack
int n,m,cnt;
void build(int m)
{
	for(int i=0;i<=m;i++) r[i]=i+1,l[i]=i-1,up[i]=down[i]=i;
	r[m]=0,l[0]=m;
	memset(sz,0,sizeof sz);
	cnt=m+1;//It's taken care of.0classifier for objects in rows such as words，从第一classifier for objects in rows such as words开始insert
}
void insert(int R,int C)//existRclassifier for objects in rows such as wordsCColumn Insertion Points
{
	sz[C]++;
	row[++cnt]=R,col[cnt]=C;
	up[cnt]=C,down[cnt]=down[C];
	up[down[C]]=cnt,down[C]=cnt;
	if(!head[R]) head[R]=r[cnt]=l[cnt]=cnt;
	else r[cnt]=head[R],l[cnt]=l[head[R]],r[l[head[R]]]=cnt,l[head[R]]=cnt;
}
void remove(int C)//removingCset of columns
{
	r[l[C]]=r[C],l[r[C]]=l[C];
	for(int i=down[C];i!=C;i=down[i])
		for(int j=r[i];j!=i;j=r[j])
			up[down[j]]=up[j],down[up[j]]=down[j],sz[col[j]]--;
}
void resume(int C)//resumptionCset of columns
{
	for(int i=up[C];i!=C;i=up[i])
		for(int j=l[i];j!=i;j=l[j])
			up[down[j]]=down[up[j]]=j,sz[col[j]]++;
	r[l[C]]=C,l[r[C]]=C;
}
bool dance(int dep)
{
	if(r[0]==0)//=head
	{
		for(int i=0;i<dep;i++) printf("%d ",ans[i]);
		return 1;
	}
	int C=r[0];
	for(int i=r[0];i;i=r[i]) if(sz[i]<sz[C]) C=i;//Find the column with the fewest points（make superior）
	remove(C);
	for(int i=down[C];i!=C;i=down[i])
	{
		ans[dep]=row[i];//压入answer stack
		for(int j=r[i];j!=i;j=r[j]) remove(col[j]);
		if(dance(dep+1)) return 1;
		for(int j=l[i];j!=i;j=l[j]) resume(col[j]);
	}
	resume(C);
	return 0;
}
int main(void)
{
	n=read(),m=read();
	int s;
	build(m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			s=read();
			if(s) insert(i,j);
		}
	if(!dance(0)) puts("No Solution!");//insoluble (i.e. unable to solve)
	return 0;
}

Introduction to Dance Chain (DLX)

Name:

\(X\)algorithm detailing

\(X\)Algorithms to solve simulations:

look back upon

Introducing DL, Dance Chain

summarize\(Dancing Links\)solution (math.)