浅谈神仙算法——DLX

6 7
1 0 0 1 0 0 1
1 0 0 1 0 0 0
0 0 0 1 1 0 1
0 0 1 0 1 1 0
0 1 1 0 0 1 1
0 1 0 0 0 0 1

//顺着链表a，遍历除s以外的所有元素
#define FOR(i,a,s) for(int i = a[s]; i != s ; i = a[i]) 
struct DLX
{
	int n,sz;
	int head;
	int l[maxnode],r[maxnode],u[maxnode],d[maxnode];
	int s[MAXN];//s[i]代表第i列节点的个数 
	int col[maxnode],row[maxnode];
	//row[i] 代表节点i在第几行，col[i]代表节点i在第几列 
	int ans[MAXN];//答案栈 
	int ansd;
	void init()
	{
		head = 0;
		for(int i=0;i<=m;i++)//有m列,处理m个虚拟节点 
		//从0开始是因为还有一个head节点 
		{
			u[i] = i;
			d[i] = i;
			l[i] = i - 1;
			r[i] = i + 1;
			//这里没必要维护row与col因为维护了也没卵用 
		} 
		r[m] = head;
		l[head] = m;
        //链表循环
		sz = m + 1;
		memset(s,0,sizeof(s));
	}
	void addRow(int R,vector <int> columns)//添加第r行,cloumns[i]代表第r行存在哪些数
	//例如colums = {1,2,9}，代表01矩阵中第r行第2个是1，如此类推 
	{
		int first = sz;
		for(int i=0;i<columns.size();i++)
		{
			int c = columns[i];
			//维护当前节点 
			l[sz] = sz - 1;
			r[sz] = sz + 1;
			//当前节点的左边是上一节点，右边是下一节点
			d[sz] = c;
			u[sz] = u[c]; 
			//由于c是当前列的编号，也就是该列虚拟节点的编号，那么u[c]其实是目前节点上方的节点编号 
			//为了使链表循环，每一个链表的最后一个节点的下方应当指向head节点,head节点的上方应当指向下方节点
			d[u[c]] = sz;
			//上一个节点的下方此时不应当是head了而应当是当前节点
			u[c] = sz;
			//重新使链表循环 
			col[sz] = c;
			row[sz] = R;
			//维护col和row
			++s[c];
			++sz; 
		}
		r[sz-1] = first ;l[first] = sz - 1;
		//使链表循环 
	}
	void remove(int c)//删除第c列 
	{
		r[l[c]] = r[c];
		l[r[c]] = l[c];
		//先删虚拟节点 
		FOR(i,d,c)//遍历第c列的down列表
			FOR(j,r,i)//遍历第c列每个节点
				{d[u[j]] = d[j] , u[d[j]] = u[j] , --s[col[j]] ;}//删除上述遍历的所有节点 
	}
	void restore(int c)//恢复 = 删除逆操作，不解释 
	{
		FOR(i,u,c)
			FOR(j,l,i)
				{++s[col[j]] , d[u[j]] = j,u[d[j]] = j;}
		r[l[c]] = c;
		l[r[c]] = c;
	}
	//前方高能！！！！！！！！！ 该算法最美丽的地方！ 
	bool dance(int step)//step为递归深度 
	{
		if(r[head] == head)//找到解 
		{
			ansd = step;
			return true;
		}
		int c = r[head];//第一个没被删除的列 
		FOR(i,r,head)
			if(s[i] < s[c])
				c = i;
		//贪心找节点最少的一列，这样可以让枚举情况最少
		remove(c);//删除 
		FOR(i,d,c)//c列表下的每一个节点 
		{
			//目前选取第row[i]行来覆盖
			//那么就应当把第row[i]行所覆盖的其他列也给删除
			ans[step] = row[i];
			FOR(j,r,i)
				remove(col[j]);
			if(dance(step + 1))
				return true;//如果找到解了，直接返回
			//要不然还要恢复并且尝试下一个i
			FOR(j,l,i)
				restore(col[j]); 
		}
		restore(c);
		//恢复
		return false; 
	}
    void print()//输出解
    {
    	for(int i = 0;i<ansd;i++)
        	cout<<ans[i]<<' ';
	}
};

每行中每个数只能出现一遍，ROW(x,v)表示第x行有数字v。

每列中每个数只能出现一遍，COL(x,v)表示第x列有数字v。

每宫中每个数只能出现一遍，BLOCK(i,v)表示编号为i的九宫格块内有数字v

每格中只能填一个数，EXIST(x,y)表示第x行y列有数字。

ROW(r,v)

COL(c,v)

BLOCK(zu(r,c),v)

EXIST(r,c,v)