前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >dancing links解决X问题的C++实现

dancing links解决X问题的C++实现

作者头像
forrestlin
发布2018-05-24 11:24:32
9837
发布2018-05-24 11:24:32
举报
文章被收录于专栏:蜉蝣禅修之道

X问题,也称精确覆盖问题,就是给定一个01矩阵,需要从中选取一些行组成一个子矩阵,这个子矩阵的每一列有且仅有一个1。这个问题听起来就知道很难,必须使用回溯算法来解决,但是我们知道回溯算法要提高效率,就必须做好剪枝和回溯恢复的工作。这时算法大师Donald E.Knoth给出了一个巧妙的数据结构,十字链表,每个节点都有上下左右的指针。其实这个结构参考的是双链表删除和恢复的便利性,思考一下,在双链表中,删除一个节点的代码就是n->left->right=n->right; n->right->left=n->left,而撤销删除的代码就是n->left->right=n; n->right->left=n;这几乎不需要任何代价就能解决。举个例子,一个如下的01矩阵

代码语言:javascript
复制
board.push_back("0010110");
board.push_back("1001001");
board.push_back("0110010");
board.push_back("1001000");
board.push_back("0100001");
board.push_back("0001101");

利用十字链表就表示如下:

其中第一行是特殊的节点,我们可以称为列节点,第一个是头节点,他们都是不存储数据,然后其他节点就是矩阵中的1,为了调试方便,把它们的节点数据都写为节点序号,说了那么多,都忘记给出节点的数据结构了:

代码语言:javascript
复制
struct Cell{
	Cell* up,*down,*left,*right;
	Cell* col;
	int rowIndex;
	Cell(int r):up(NULL),down(NULL),left(NULL),right(NULL),col(NULL),rowIndex(r){}
};

细心的读者肯定会发现,节点结构中除了上下左右指针外,还有一个col指针,没错,这个是指向每一列的列节点的指针。说了这里,也应该开始讲算法思路了,

1.取出nextCell=head->right,如果nextCell等于head,则算法结束,返回答案,否则进入第2步。

2.删除nextCell,遍历nextCell下面的所有节点,将这些节点所在的行都删除。

3.取出downCell=nextCell->down,如果downCell等于nextCell,则代表不能继续搜索,需要回溯,进入第5步,否则进入第4步。

4.遍历downCell右边的所有节点,将每个节点的列节点都按照第2步的方法删除,然后重新进入第1步。

5.回溯恢复到删除downCell所有右节点的列节点的状态,然后downCell=downCell->down,如果downCell等于nextCell,证明也不能回溯了,需要恢复nextCell,继续返回上一级恢复,否则进入第4步。

算法的思路就只有这么多了,其中恢复节点看上去很难,但只要按照删除的顺序逆回去,堆栈就会很好地帮你实现了。具体删除和恢复的代码如下:

代码语言:javascript
复制
bool removeColCell(Cell* colCell){
	colCell->left->right=colCell->right;
	colCell->right->left=colCell->left;
	Cell* downCell=colCell->down;
	if(downCell==colCell)
		return false;
	while(downCell!=colCell){
		Cell* downRightCell=downCell->right;
		while(downRightCell!=downCell){
			downRightCell->up->down=downRightCell->down;
			downRightCell->down->up=downRightCell->up;
			downRightCell=downRightCell->right;
		}
		downCell=downCell->down;
	}
	return true;
}
void recoverColCell(Cell* colCell){
	Cell* downCell=colCell->down;
	while(downCell!=colCell){
		Cell* downRightCell=downCell->right;
		while(downRightCell!=downCell){
			downRightCell->up->down=downRightCell;
			downRightCell->down->up=downRightCell;
			downRightCell=downRightCell->right;
		}
		downCell=downCell->down;
	}
	colCell->left->right=colCell;
	colCell->right->left=colCell;
}

DLX算法主体代码如下:

代码语言:javascript
复制
bool solveWithDLX(Cell* head,vector<int>& answers){
	if(head->right==head)
		return true;
	Cell* nextCell=head->right;
	if(!removeColCell(nextCell))
		return false;
	Cell* downCell=nextCell->down;
	while(downCell!=nextCell){
		Cell* downRightCell=downCell->right;
		while(downRightCell!=downCell){
			Cell* rightColCell=downRightCell->col;
			removeColCell(rightColCell);
			downRightCell=downRightCell->right;
		}
		if(solveWithDLX(head,answers)){
			answers.push_back(downCell->rowIndex);
			return true;
		}else{
			Cell* downRightCell=downCell->right;
			while(downRightCell!=downCell){
				Cell* rightColCell=downRightCell->col;
				recoverColCell(rightColCell);
				downRightCell=downRightCell->right;
			}
			downCell=downCell->down;
		}
	}
	recoverColCell(nextCell);
	return false;
}

然后构建十字链表的代码如下:

代码语言:javascript
复制
	vector<string> board;
	board.push_back("0010110");
	board.push_back("1001001");
	board.push_back("0110010");
	board.push_back("1001000");
	board.push_back("0100001");
	board.push_back("0001101");
	Cell* head=new Cell(0);
	Cell* lastCell=head;
	vector<Cell*> columnCells;
	for(int i=0;i<7;i++){
		Cell* cell=new Cell(-1-i);
		lastCell->right=cell;
		cell->left=lastCell;
		cell->up=cell;
		cell->down=cell;
		columnCells.push_back(cell);
		lastCell=cell;
	}
	lastCell->right=head;
	head->left=lastCell;
	int index=1;
	for(int i=0;i<board.size();i++){
		Cell *lastCell=NULL,*firstCell=NULL;
		for(int j=0;j<board[i].length();j++){
			if(board[i][j]=='1'){
				Cell* columnCell=columnCells[j];
				Cell* cell=new Cell(i+1);
				cell->up=columnCell->up;
				cell->down=columnCell;
				columnCell->up->down=cell;
				columnCell->up=cell;
				cell->col=columnCell;
				if(lastCell==NULL){
					firstCell=cell;
					lastCell=cell;
				}
				cell->left=lastCell;
				lastCell->right=cell;
				lastCell=cell;
			}
		}
		firstCell->left=lastCell;
		lastCell->right=firstCell;
	}
	vector<int>answers;
	solveWithDLX(head,answers);
	for(int i=0;i<answers.size();i++){
		cout<<answers[i]<<endl;
	}

最终代码会输出选择的行号。

最后的最后,虽然上面的代码解决一般的X问题没问题,但是当我将数独问题转化成X问题时,再用DLX算法却始终没跑出来,还请各位大神帮忙看一眼,其中删除和恢复的代码都是一样的,只是构建十字链表不太一样,这个十字链表一共有324列,也就是81*4,第一个81是代表81个格子中第几个格子有数,第二个81是代表第几行有哪个数字,第三个81是代表第几列有哪个数字,第四列是代表第几个九宫格有哪个数字,举个例子,如果第2个格子是9,那么在十字链表中将插入一行,这一行在第1列是1,第81+8列是1,第81*2+9+8列是1,以及第81*3+8列是1,而如果第2个格子是空的,那么这个格子会有9种可能,所以会插入9行,第0行中第1列是1,第81+0列是1,第81*2+9+0列是1,第81*3+0是1,其他行也如此类推。代码如下:

代码语言:javascript
复制
void solveSudoku(vector<vector<char>>& board) {
	Cell* head=new Cell(0);
	Cell* lastCell=head;
	vector<Cell*> columnCells;
	for(int i=0;i<324;i++){
		Cell* cell=new Cell(-i-1);
		cell->up=cell;
		cell->down=cell;
		lastCell->right=cell;
		cell->left=lastCell;
		columnCells.push_back(cell);
		lastCell=cell;
	}
	lastCell->right=head;
	head->left=lastCell;
	for(int i=0;i<9;i++){
		for(int j=0;j<9;j++){
			if(board[i][j]!='.'){
				int num=board[i][j]-'1';
				int rowIndex=(i*9+j)*10+num;
				Cell* posCell=new Cell(rowIndex);
				Cell* posColumnCell=columnCells[i*9+j];
				posCell->up=posColumnCell->up;
				posCell->down=posColumnCell;
				posColumnCell->up->down=posCell;
				posColumnCell->up=posCell;
				posCell->col=posColumnCell;

				Cell* rowCell=new Cell(rowIndex);
				rowCell->left=posCell;
				posCell->right=rowCell;
				Cell* rowColumnCell=columnCells[i*9+num+81];
				rowCell->up=rowColumnCell->up;
				rowCell->down=rowColumnCell;
				rowColumnCell->up->down=rowCell;
				rowColumnCell->up=rowCell;
				rowCell->col=rowColumnCell;

				Cell* colCell=new Cell(rowIndex);
				colCell->left=rowCell;
				rowCell->right=colCell;
				Cell* colColumnCell=columnCells[j*9+num+81*2];
				colCell->up=colColumnCell->up;
				colCell->down=colColumnCell;
				colColumnCell->up->down=colCell;
				colColumnCell->up=colCell;
				colCell->col=colColumnCell;

				Cell* subCell=new Cell(rowIndex);
				subCell->left=colCell;
				subCell->right=posCell;
				posCell->left=subCell;
				colCell->right=subCell;
				int subIndex=i/3*3+j/3;
				Cell* subColumnCell=columnCells[subIndex*9+num+81*3];
				subCell->up=subColumnCell->up;
				subCell->down=subColumnCell;
				subColumnCell->up->down=subCell;
				subColumnCell->up=subCell;
				subCell->col=subColumnCell;
			}else{
				for(int num=0;num<9;num++){
					int rowIndex=(i*9+j)*10+num;
					Cell* posCell=new Cell(rowIndex);
					Cell* posColumnCell=columnCells[i*9+j];
					posCell->up=posColumnCell->up;
					posCell->down=posColumnCell;
					posColumnCell->up->down=posCell;
					posColumnCell->up=posCell;
					posCell->col=posColumnCell;

					Cell* rowCell=new Cell(rowIndex);
					rowCell->left=posCell;
					posCell->right=rowCell;
					Cell* rowColumnCell=columnCells[i*9+num+81];
					rowCell->up=rowColumnCell->up;
					rowCell->down=rowColumnCell;
					rowColumnCell->up->down=rowCell;
					rowColumnCell->up=rowCell;
					rowCell->col=rowColumnCell;

					Cell* colCell=new Cell(rowIndex);
					colCell->left=rowCell;
					rowCell->right=colCell;
					Cell* colColumnCell=columnCells[j*9+num+81*2];
					colCell->up=colColumnCell->up;
					colCell->down=colColumnCell;
					colColumnCell->up->down=colCell;
					colColumnCell->up=colCell;
					colCell->col=colColumnCell;

					Cell* subCell=new Cell(rowIndex);
					subCell->left=colCell;
					subCell->right=posCell;
					posCell->left=subCell;
					colCell->right=subCell;
					int subIndex=i/3*3+j/3;
					Cell* subColumnCell=columnCells[subIndex*9+num+81*3];
					subCell->up=subColumnCell->up;
					subCell->down=subColumnCell;
					subColumnCell->up->down=subCell;
					subColumnCell->up=subCell;
					subCell->col=subColumnCell;
				}
			}
		}
	}
	vector<int> answers;
	solveWithDLX(head,answers);
	for(int i=0;i<answers.size();i++){
		int rowIndex=answers[i];
		int val=rowIndex%10;
		rowIndex/=10;
		int row=rowIndex/9;
		int col=rowIndex%9;
		if(board[row][col]=='.')
			board[row][col]=val+'1';
	}
}

细心的读者肯定发现,每个节点的数据存的都是行号*9+列号+num,这样我通过最后的answer就知道该在哪个格子中填什么数字。不过这些都不重要,现在是这代码好像进入了死循环,每次跑都会报出栈溢出,恳求大神们看看是不是构建矩阵时出错了。

鸣谢http://www.cnblogs.com/grenet/p/3145800.html给出了大量的图和详细的讲解。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2015年11月13日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档