- 浏览: 169514 次
- 性别:
- 来自: 广州
博客专栏
-
TCP/IP详解卷一>阅读...
浏览量:12550
文章分类
最新评论
-
master11:
你好,博主看完你的解释,好厉害啊!!佩服。如果想运行看一下效果 ...
数独人工解法的一些技巧及其python实现 -
evasiu:
chenxun1012033254 写道lz这么辛苦我也是醉了 ...
数独人工解法的一些技巧及其python实现 -
chenxun1012033254:
lz这么辛苦我也是醉了作为一名oier我说有一个算法叫做dan ...
数独人工解法的一些技巧及其python实现 -
xuyfiei:
lz很厉害,现在该是毕业了吧
恨毕业--读研一年总结 -
nphoenix:
呵呵 肯踏實的學東西已經很不錯了。畢業了工作之後,你就會發現個 ...
恨毕业--读研一年总结
折腾了一个星期,发现自己的大脑真的是短路了,智力水平下降到历史最低点,竟然折腾了那么久才理解了dancing link。所幸经过几天的反思,终于列出了接下来应该做的几件事:
1. 产生数独题:
1.1 实现解数独的算法dlx
1.2 从数独终盘中随机选择一个cell,判断该cell是否可以挖掉而不会造成解不唯一
2. 用pygame实现基本界面
今天完成了1.1的编码,借此总结一下。
老实说,我也不明白为什么dancing link X会花了我那么多时间去理解,尤其是当我最后理解了它并用三种方法把它实现了之后。也许是Donald 26页的论文[1]把我吓到了,也许是我真的变笨了,或者老了。。
在那篇26页的论文里,其实Donald主要讲了两件事(我关心的两件事,后面的我也没有仔细看):
1. 解决exact-cover问题的算法,也即Dancing link X里的那个算法X,Donald说他暂时没有想到一个更好的名字,所以管它叫algorithm X
2. 算法X的实现上的一些技巧,也即著名的dancing link,也就是说,dancing link并不是一种算法,它只是一种技巧而已~
Exact-Cover问题:
问题描述:给定一个0/1矩阵(一般是稀疏矩阵),选出一些行,使得由这些行构成的新矩阵中每一列有且仅有一个1。换个说法,把列看成域(universe)中的元素,把行看成域里的一个子集,exact-cover问题就是找出一些不相交的子集,它们的并集覆盖整个域。
问题举例:
有如下0/1矩阵:
矩阵的行(1,4,5)构成的新矩阵中每一行每一列都有且仅有一个1.
解决方案:
我们知道,当我们选择某一行时,其他与该行在某列上同时有一个1的行都将不能再入选。也就是说,这些行在下一次遴选前都将被删除,而相应的列也可以被删除,因为这些列已经有了1了。也就是说,我们可以通过删除矩阵的行、列来缩小问题的规模,直到最终矩阵为空,说明我们已经找到了一个合法的解。假如矩阵出现没有1的列,说明这个问题无解,因为它说明这个列没有办法得到一个1.下面是Donald总结的算法流程:
上面的描述便是前面提到的algorithm X。它其实是一个深搜问题。在行4,算法选择一个非确定性的(nondeterministic)行r,这将形成搜索树上的不同分枝,例如上面的例子我们确定性地选择列1做为我们的初始入口,选择行2或选择行4将形成搜索树的两个分支,我们首先沿着行2这个分枝搜索下去,如果找不到解,将一步一步回溯,最后返回root,然后再从行4这个分枝搜索。在这个过程中,算法将花费很多时间在矩阵的操作(删除行/列)上。
Donald在文章的开篇就提出了一件很是让人感到aha~!的事情:
假设x指向双向链表的一个元素,x.left指向x的左元素,x.right指向x的右元素,当我们决定删除x时,可以做如下操作:
而下面这两句精练的对称的语句将重新将x放回链表上:
是不是很美妙呢?而这,便是dancing link的精华了。
让我们换个数据结构来表现一个稀疏的0/1矩阵,形象一点,就是下图这样的表示:
每个矩阵元素,我们称之为data object,有四个指针,分别指向其上、下、左、右元素,矩阵的每一行、每一列都是一个双向循环链表,每一列还连带一个list header,我们称之为column object,以方便我们进行列的删除操作。column object同样也是双向链表中的一部分。每个data object除了那四个指针外,还带有一个column object的引用,以方便对该列进行删除。而column object则还另外包括一个size元素,说明该列总共有多少个元素。还记得我们前面提到的算法不?我们每次选一个列c,该c拥有的每一个行都将成为一个分支。实际上我们做的事情是在众多未知数中先假设某个未知数,从而缩小搜索的空间,再在未知数中做新的假设,,直到最后所有假设都符合题目限制于是成功获得结果或者某个限制被打破从而搜索失败必须回溯。该列有多少个元素将决定了搜索树在该子根下将有多少个分支,那我们当然希望越在上层的分枝越少就越好,(因为随着树的深入,可能很多未知量都变成已知的),因此就有了这个size,以方便我们进行列的选择。由column object组成的双向横向链表还包含一个root,用来标志矩阵是否为空,当root.right==root时。上面的算法通过改用这个数据结构,可以重新描述如下:
cover跟uncover的操作如下:
是不是相当简洁呢?对于上面的那个例子,下图是cover了column A后的矩阵:
当我们选择了行2后,将cover column D跟G,下面是cover了D跟G后的矩阵:
Dancing link使矩阵的行/列删除变得相当快捷,有如弹弹手指般容易。实现起来也相当地容易。不过由于我对python还是很不熟,而当时又感觉自己没有弄懂dancing link的样子,于是我只好从自己比较熟悉的c++开始编码了,于是就有了下面两个版本的dlx:
C++封装做得不是很好,呵呵。
下面是python的实现版本,显然比c++要简洁好多:
从数独到Exact-Cover问题:
那么,数独跟Exact-Cover有什么关系呢?我们来看看数独的限制:
1. 每个格里只能填一个数(1-9),有且只有一个
2. 每个数(1-9)在每一行里只能出现一次,有且只有一次
3. 每个数在每一列里只能出现一次,有且只有一次
4. 每个数在每一个块(block)只能出现一次,有且只有一次
这么多个“有且只有一次”显然在向我们发出强烈的信号:这是一个exact-cover问题!于是便有了下面的转换:
我们知道,在没有任何限制下,数独的第i行,第j列可以填入数字k,其中0<i,j,k<=9,因此我们实际上是从9^3个(i,j,k)中选择81个,同时使其满足以上4个限制。对于每一个(i,j,k),格(i,j)只能填一个数字的限制将表现为列(ci,cj)从k=[1,9]为1,所以我们只能选其中一行,也就是,在k=[1,9]中,只有一个(i,j,k0)被选中。对于每一个(i,j,k),行i只能出现一次k的限制将表现为列(ci, ck)从j=[1,9]为1,我们只能选择其中一行。对于限制3,4也是同样的道理。总共将需要81*4列,9^3行。这里[2]把这个问题说得很清楚。
下面分别是C++和python的数独求解:
最后最后,这里[3]提供了一个30行的dlx的python代码,非常的精致,建议大家都去看一看~!
__________________________________________
[1]Dancing Links, Donald E. Knuth(附件下载)
[2]http://cgi.cse.unsw.edu.au/~xche635/dlx_sodoku/
[3]http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html
1. 产生数独题:
1.1 实现解数独的算法dlx
1.2 从数独终盘中随机选择一个cell,判断该cell是否可以挖掉而不会造成解不唯一
2. 用pygame实现基本界面
今天完成了1.1的编码,借此总结一下。
老实说,我也不明白为什么dancing link X会花了我那么多时间去理解,尤其是当我最后理解了它并用三种方法把它实现了之后。也许是Donald 26页的论文[1]把我吓到了,也许是我真的变笨了,或者老了。。
在那篇26页的论文里,其实Donald主要讲了两件事(我关心的两件事,后面的我也没有仔细看):
1. 解决exact-cover问题的算法,也即Dancing link X里的那个算法X,Donald说他暂时没有想到一个更好的名字,所以管它叫algorithm X
2. 算法X的实现上的一些技巧,也即著名的dancing link,也就是说,dancing link并不是一种算法,它只是一种技巧而已~
Exact-Cover问题:
问题描述:给定一个0/1矩阵(一般是稀疏矩阵),选出一些行,使得由这些行构成的新矩阵中每一列有且仅有一个1。换个说法,把列看成域(universe)中的元素,把行看成域里的一个子集,exact-cover问题就是找出一些不相交的子集,它们的并集覆盖整个域。
问题举例:
有如下0/1矩阵:
矩阵的行(1,4,5)构成的新矩阵中每一行每一列都有且仅有一个1.
解决方案:
我们知道,当我们选择某一行时,其他与该行在某列上同时有一个1的行都将不能再入选。也就是说,这些行在下一次遴选前都将被删除,而相应的列也可以被删除,因为这些列已经有了1了。也就是说,我们可以通过删除矩阵的行、列来缩小问题的规模,直到最终矩阵为空,说明我们已经找到了一个合法的解。假如矩阵出现没有1的列,说明这个问题无解,因为它说明这个列没有办法得到一个1.下面是Donald总结的算法流程:
Exact_Cover(A): if A is empty: problem solve, return else pick a column c: choose a row, r, such that A[r,c]=1 include r in the partial solution for each j such that A[r,j]=1: delete column j from matrix A for each i such that A[i,j]=1: delete row i from matrix A repeat this algorithm recursively on the reduced matrix A
上面的描述便是前面提到的algorithm X。它其实是一个深搜问题。在行4,算法选择一个非确定性的(nondeterministic)行r,这将形成搜索树上的不同分枝,例如上面的例子我们确定性地选择列1做为我们的初始入口,选择行2或选择行4将形成搜索树的两个分支,我们首先沿着行2这个分枝搜索下去,如果找不到解,将一步一步回溯,最后返回root,然后再从行4这个分枝搜索。在这个过程中,算法将花费很多时间在矩阵的操作(删除行/列)上。
Donald在文章的开篇就提出了一件很是让人感到aha~!的事情:
假设x指向双向链表的一个元素,x.left指向x的左元素,x.right指向x的右元素,当我们决定删除x时,可以做如下操作:
x.left.right = x.right x.right.left = x.left
而下面这两句精练的对称的语句将重新将x放回链表上:
x.left.right = x x.right.left = x
是不是很美妙呢?而这,便是dancing link的精华了。
让我们换个数据结构来表现一个稀疏的0/1矩阵,形象一点,就是下图这样的表示:
每个矩阵元素,我们称之为data object,有四个指针,分别指向其上、下、左、右元素,矩阵的每一行、每一列都是一个双向循环链表,每一列还连带一个list header,我们称之为column object,以方便我们进行列的删除操作。column object同样也是双向链表中的一部分。每个data object除了那四个指针外,还带有一个column object的引用,以方便对该列进行删除。而column object则还另外包括一个size元素,说明该列总共有多少个元素。还记得我们前面提到的算法不?我们每次选一个列c,该c拥有的每一个行都将成为一个分支。实际上我们做的事情是在众多未知数中先假设某个未知数,从而缩小搜索的空间,再在未知数中做新的假设,,直到最后所有假设都符合题目限制于是成功获得结果或者某个限制被打破从而搜索失败必须回溯。该列有多少个元素将决定了搜索树在该子根下将有多少个分支,那我们当然希望越在上层的分枝越少就越好,(因为随着树的深入,可能很多未知量都变成已知的),因此就有了这个size,以方便我们进行列的选择。由column object组成的双向横向链表还包含一个root,用来标志矩阵是否为空,当root.right==root时。上面的算法通过改用这个数据结构,可以重新描述如下:
search(k): if root.right == root: solution found, return true or print it~ { as we've mentioned before, choose one column that has least elements} choose a column c cover column c {remember c is a column object} for each r <- c.down, c.down.down, ..., while r!=c solution[k]=r for each j <- r.right, r.right.right, ..., while j!=r cover column j if search(k+1): return true {doing clean up jobs} for each j <- r.left, r.left.left, ..., while j!=r uncover column j {if we get here, no solution is found} uncover column c return false
cover跟uncover的操作如下:
cover( column object c ): c.left.right = c.right c.right.left = c.left for each i <- c.down, c.down.down, ..., while i!=c: for each j <- i.right, i.right.right, ..., while j!=i: j.down.up = j.up j.up.down = j.down j.column.size-- uncover( column object c ): for each i <- c.up, c.up.up, ..., while i!=c: for each j <- i.left, i.left.left, ..., while j!=i: j.down.up = j j.up.down = j j.column.size++ c.left.right = c c.right.left = c
是不是相当简洁呢?对于上面的那个例子,下图是cover了column A后的矩阵:
当我们选择了行2后,将cover column D跟G,下面是cover了D跟G后的矩阵:
Dancing link使矩阵的行/列删除变得相当快捷,有如弹弹手指般容易。实现起来也相当地容易。不过由于我对python还是很不熟,而当时又感觉自己没有弄懂dancing link的样子,于是我只好从自己比较熟悉的c++开始编码了,于是就有了下面两个版本的dlx:
C++封装做得不是很好,呵呵。
//ExtractCoverMatrix.h #include<iostream> using namespace std; struct Node { Node* left, *right, *up, *down; int col, row; Node(){ left = NULL; right = NULL; up = NULL; down = NULL; col = 0; row = 0; } Node( int r, int c ) { left = NULL; right = NULL; up = NULL; down = NULL; col = c; row = r; } }; struct ColunmHeader : public Node { int size; ColunmHeader(){ size = 0; } }; class ExactCoverMatrix { public: int ROWS, COLS; //这是存储结果的数组 int* disjointSubet; //接收矩阵其及维度 ExactCoverMatrix( int rows, int cols, int** matrix ); //释放内存 ~ExactCoverMatrix(); //在行r列c的位置上插入一个元素 void insert( int r, int c ); //即我们的cover和uncover操作了 void cover( int c ); void uncover( int c ); //即我们的algorithm X的实现了 int search( int k=0 ); private: ColunmHeader* root; ColunmHeader* ColIndex; Node* RowIndex; }; //ExactCoverMatrix.cpp #include "ExtracCoverMatrix.h" ExtracCoverMatrix::ExtracCoverMatrix( int rows, int cols, int** matrix ) { ROWS = rows; COLS = cols; disjointSubet = new int[rows+1]; ColIndex = new ColunmHeader[cols+1]; RowIndex = new Node[rows]; root = &ColIndex[0]; ColIndex[0].left = &ColIndex[COLS]; ColIndex[0].right = &ColIndex[1]; ColIndex[COLS].right = &ColIndex[0]; ColIndex[COLS].left = &ColIndex[COLS-1]; for( int i=1; i<cols; i++ ) { ColIndex[i].left = &ColIndex[i-1]; ColIndex[i].right = &ColIndex[i+1]; } for ( int i=0; i<=cols; i++ ) { ColIndex[i].up = &ColIndex[i]; ColIndex[i].down = &ColIndex[i]; ColIndex[i].col = i; } ColIndex[0].down = &RowIndex[0]; for( int i=0; i<rows; i++ ) for( int j=0; j<cols&&matrix[i][j]>0; j++ ) { insert( i, matrix[i][j] ); } } ExtracCoverMatrix::~ExtracCoverMatrix() { delete[] disjointSubet; for( int i=1; i<=COLS; i++ ) { Node* cur = ColIndex[i].down; Node* del = cur->down; while( cur != &ColIndex[i] ) { delete cur; cur = del; del = cur->down; } } delete[] RowIndex; delete[] ColIndex; } void ExtracCoverMatrix::insert( int r, int c ) { Node* cur = &ColIndex[c]; ColIndex[c].size++; Node* newNode = new Node( r, c ); while( cur->down != &ColIndex[c] && cur->down->row < r ) cur = cur->down; newNode->down = cur->down; newNode->up = cur; cur->down->up = newNode; cur->down = newNode; if( RowIndex[r].right == NULL ) { RowIndex[r].right = newNode; newNode->left = newNode; newNode->right = newNode; } else { Node* rowHead = RowIndex[r].right; cur = rowHead; while( cur->right != rowHead && cur->right->col < c ) cur = cur->right; newNode->right = cur->right; newNode->left = cur; cur->right->left = newNode; cur->right = newNode; } } void ExtracCoverMatrix::cover( int c ) { ColunmHeader* col = &ColIndex[c]; col->right->left = col->left; col->left->right = col->right; Node* curR, *curC; curC = col->down; while( curC != col ) { Node* noteR = curC; curR = noteR->right; while( curR != noteR ) { curR->down->up = curR->up; curR->up->down = curR->down; ColIndex[curR->col].size--; curR = curR->right; } curC = curC->down; } } void ExtracCoverMatrix::uncover( int c ) { Node* curR, *curC; ColunmHeader* col = &ColIndex[c]; curC = col->up; while( curC != col ) { Node* noteR = curC; curR = curC->left; while( curR != noteR ) { ColIndex[curR->col].size++; curR->down->up = curR; curR->up->down = curR; curR = curR->left; } curC = curC->up; } col->right->left = col; col->left->right = col; } int ExtracCoverMatrix::search( int k ) { if( root->right == root ) return k; ColunmHeader* choose = (ColunmHeader*)root->right, *cur=choose; while( cur != root ) { if( choose->size > cur->size ) choose = cur; cur = (ColunmHeader*)cur->right; } if( choose->size <= 0 ) return -1; cover( choose->col ); Node* curC = choose->down; while( curC != choose ) { disjointSubet[k] = curC->row; Node* noteR = curC; Node* curR = curC->right; while( curR != noteR ) { cover( curR->col ); curR = curR->right; } int res=-1; if( (res = search( k+1 ))>0 ) return res; curR = noteR->left; while( curR != noteR ) { uncover( curR->col ); curR = curR->left; } curC = curC->down; } uncover( choose->col ); return -1; }
下面是python的实现版本,显然比c++要简洁好多:
#这段代码基本上来自http://code.google.com/p/mycodeplayground/ #我更多的是理解和欣赏python程序的写法。。。 class Node(object): '''data object in dancing link Basic element for a sparse matrix doubly linked in both horizontal and vertical direction''' def __init__( self, left = None, right = None, up = None, down = None, column_header = None, row_header = None ): self.left = left or self self.right = right or self self.up = up or self self.down = down or self self.column_header = column_header self.row_header = row_header def nodes_in_direction( self, dir ): '''Generator for nodes in different direction :Parameters: dir: str dir can be 'up', 'down', 'left', 'right' ''' node = getattr( self, dir ) while node != self: #print node.column_header.size yield node node = getattr( node, dir ) class ColumnHeader(Node): '''list header, or column object in dancing link has an extra element of size recording the number of data object in this column''' def __init__( self, *args, **kargs ): Node.__init__( self, *args, **kargs ) self.size = 0 class RowHeader(Node): '''RowHeader is an extra element for dancing link to record the row no. of a row so that we can trace down which rows are picked up''' def __init__( self, rowno, *args, **kargs ): Node.__init__( self, *args, **kargs ) self.rowno = rowno self.row_header = self class DLXSolver(object): def __init__( self ): pass def solve(self, matrix, num_columns): '''solve the exact cover problem of a given matrix :Parameters: matrix is in the form as: { k:[x0, x1, ..., xn] } where k is the line number while xi(0<=xi<num_columns) is the column of the matrix where there is a 1 num_columns: number of columns in the matrix :Return: solution: [k] solution is a list of line number that is picked ''' self._partial_answer = {} self._k = 0 self._construct( matrix, num_columns ) self._search(0) return [self._partial_answer[k] for k in xrange(self._k)] def _construct( self, matrix, num_columns ): '''construct a matrix into a sparse matrix using doubly link list :Parameter: parameters are same as solve ''' self.root = Node() self.column_headers = [] #constructing column_headers for i in xrange(num_columns): new_column_header = ColumnHeader(left=self.root.left, right=self.root) self.root.left.right = new_column_header self.root.left = new_column_header self.column_headers.append( new_column_header ) #inserting nodes into the sparse matrix for k in matrix: if not matrix[k]: continue column_id_sorted = sorted(matrix[k]) column_header = self.column_headers[column_id_sorted[0]] column_header.size += 1 new_row_header = RowHeader(k, up=column_header.up, down=column_header, column_header=column_header) column_header.up.down = new_row_header column_header.up = new_row_header column_id_sorted.pop(0) #constructing remaining nodes for i in column_id_sorted: column_header = self.column_headers[i] column_header.size += 1 new_node = Node( left=new_row_header.left, right=new_row_header, up = column_header.up, down = column_header, column_header = column_header, row_header = new_row_header ) column_header.up.down = new_node column_header.up = new_node new_row_header.left.right = new_node new_row_header.left = new_node def _cover( self, column_header ): '''cover a column of a matrix as what donald said''' column_header.left.right = column_header.right column_header.right.left = column_header.left for eachNode in column_header.nodes_in_direction("down"): for node in eachNode.nodes_in_direction("right"): node.column_header.size -= 1 node.up.down = node.down node.down.up = node.up def _uncover( self, column_header ): '''uncover a column of a matrix in the reverse order as cover do''' for eachNode in column_header.nodes_in_direction("up"): for node in eachNode.nodes_in_direction("left"): node.column_header.size += 1 node.down.up = node node.up.down = node column_header.left.right = column_header column_header.right.left = column_header def _search( self, k ): if self.root.right == self.root: self._k = k return True column_header=min([header for header in self.root.nodes_in_direction("right")], key=lambda h:h.size) self._cover( column_header ) for eachNode in column_header.nodes_in_direction("down"): self._partial_answer[k] = eachNode.row_header.rowno for node in eachNode.nodes_in_direction("right"): self._cover(node.column_header) if self._search( k+1 ): return True for node in eachNode.nodes_in_direction("left"): self._uncover(node.column_header) self._uncover(column_header) return False '''test case for dlxSolver''' if __name__ == "__main__": matrix = { 1:[2, 4,5], 2:[0,3,6], 3:[1,2,5], 4:[0,3], 5:[1,6], 6:[3,4,6]} testSolver = DLXSolver() print testSolver.solve( matrix, 7 )
从数独到Exact-Cover问题:
那么,数独跟Exact-Cover有什么关系呢?我们来看看数独的限制:
1. 每个格里只能填一个数(1-9),有且只有一个
2. 每个数(1-9)在每一行里只能出现一次,有且只有一次
3. 每个数在每一列里只能出现一次,有且只有一次
4. 每个数在每一个块(block)只能出现一次,有且只有一次
这么多个“有且只有一次”显然在向我们发出强烈的信号:这是一个exact-cover问题!于是便有了下面的转换:
我们知道,在没有任何限制下,数独的第i行,第j列可以填入数字k,其中0<i,j,k<=9,因此我们实际上是从9^3个(i,j,k)中选择81个,同时使其满足以上4个限制。对于每一个(i,j,k),格(i,j)只能填一个数字的限制将表现为列(ci,cj)从k=[1,9]为1,所以我们只能选其中一行,也就是,在k=[1,9]中,只有一个(i,j,k0)被选中。对于每一个(i,j,k),行i只能出现一次k的限制将表现为列(ci, ck)从j=[1,9]为1,我们只能选择其中一行。对于限制3,4也是同样的道理。总共将需要81*4列,9^3行。这里[2]把这个问题说得很清楚。
下面分别是C++和python的数独求解:
#include<iostream> #include "ExactCoverMatrix.h" using namespace std; const int N_Cell = 3; const int N = 9; const int OFFSET = 9*9; const int ROWS = N*N*N; const int COLS = N*N*4; void solve_sudoku( int (*grid)[N] ) { //tranform a sudoku to a exact cover problem int** sudoku_matrix = new int*[ROWS]; for( int i=0; i<ROWS; i++ ) sudoku_matrix[i] = new int[5]; for( int i=0; i<N; i++ ) for( int j=0; j<N; j++ ) { int b = (i/N_Cell)*N_Cell + (j/N_Cell); int r = i*N*N + j*N; for( int k=1; k<=N; k++ ) { sudoku_matrix[r][0]=i*N+j+1; sudoku_matrix[r][1]=OFFSET+(i*N+k); sudoku_matrix[r][2]=OFFSET*2+(j*N+k); sudoku_matrix[r][3]=OFFSET*3+(b*N+k); sudoku_matrix[r][4]=-1; r++; } } SparseMatrix sudoku( ROWS, COLS, sudoku_matrix ); //cover those have been filled for( int i=0; i<N; i++ ) for( int j=0; j<N; j++ ) { int k; if( k = grid[i][j] ) { /* corresponding to insert( r, i*N+j+1 ); insert( r, OFFSET+(i*N+k) ); insert( r, OFFSET*2+(j*N+k) ); insert( r, OFFSET*3+(b*N+k) ); */ int b = (i/N_Cell)*N_Cell + j/N_Cell; sudoku.cover( i*N+j+1 ); sudoku.cover( OFFSET+( i*N+k ) ); sudoku.cover( OFFSET*2+(j*N+k) ); sudoku.cover( OFFSET*3+(b*N+k) ); } } int solved=0; if( (solved=sudoku.search())>0 ) { int c, r, k; for( int i=0; i<solved; i++ ) { r = sudoku.disjointSubet[i]/(N*N); c = (sudoku.disjointSubet[i]/N)%N; k = sudoku.disjointSubet[i]%N; grid[r][c]=k+1; } cout<<"here is the result: "<<endl; for( int i=0; i<N; i++ ) { for( int j=0; j<N; j++ ) cout<<grid[i][j]<<' '; cout<<endl; } } else cout<<"no solution for this sudoku"<<endl; } bool verify_puzzle( int (*grid)[N] ) { int line[N+1]={0}; for( int i=0; i<N; i++ ) { for( int j=0; j<=N; j++ ) line[j] = 0; for( int j=0; j<N; j++ ) { if( line[grid[i][j]] ) { cout<<"row wrong: "<<i<<endl; return false; } else line[grid[i][j]] = 1; } } for( int i=0; i<N; i++ ) { for( int j=0; j<N+1; j++ ) line[j] = 0; for( int j=0; j<N; j++ ) { if( line[grid[j][i]] ) { cout<<"column wrong"<<endl; return false; } else line[grid[j][i]] = 1; } } for( int i=0; i<N_Cell; i++ ) for( int j=0; j<N_Cell; j++ ) { for( int x=0; x<=N; x++ ) line[x] = 0; for( int k=0; k<N_Cell; k++ ) for( int t=0; t<N_Cell; t++ ) { int x = k+i*N_Cell; int y = t+j*N_Cell; if( line[grid[x][y]] ) { cout<<"block wrong"<<endl; return false; } else line[grid[x][y]] = 1; } } return true; } int main() { int puzzle[N][N]={ {0, 0, 0, 0, 0, 3, 0, 8, 1}, {2, 0, 0, 4, 0, 0, 0, 0, 0}, {0, 5, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 2, 3, 0, 7, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 5, 0}, {0, 0, 8, 6, 0, 0, 0, 0, 0}, {7, 0, 0, 0, 0, 0, 4, 0, 0}, {0, 9, 0, 0, 8, 0, 0, 0, 0}, {0, 0, 0, 0, 5, 0, 2, 0, 0}}; solve_sudoku( puzzle ); if( !verify_puzzle( puzzle ) ) cout<<"wrong answer!"<<endl; }
from __future__ import division from dlx_1 import DLXSolver class SudokuSolver(object): digits = set(map(str, range(1,10))) GRIDOFFSET=0 #column 0~80 is for testing each cell has only one digit ROWOFFSET=81 #column 81~161 is for testing each line contain each number exactly once COLOFFSET=162 #column 162~242 is for testing each column contain each number exactly once BLKOFFSET=243 #colunm 243~323 is for testing each block contain each number exactly once COLUNMS = 324 def __init__( self ): self.dlx_solver = DLXSolver() def solve( self, puzzle ): '''solve the given sudoku puzzle unfilled cell is represented with other symbols except 1~9 ''' dlx_matrix = self._construct(puzzle) result = self.dlx_solver.solve( dlx_matrix, self.COLUNMS ) solved_sudoku=list(puzzle) for row, col, val in result: solved_sudoku[row*9+col]=val+1 return solved_sudoku def _construct( self, puzzle ): '''construct a sudoku puzzle to a dlx_matrix''' linear_puzzle = ''.join(puzzle.split()) if len(linear_puzzle) != 81: print 'invalid puzzle!' return dlx_matrix={} for i, c in enumerate(linear_puzzle): row, col = divmod(i,9) if c in self.digits: val = int(c)-1 dlx_matrix[(row, col, val)]=self._get_ones(row, col, val) else: for val in range(9): dlx_matrix[(row, col, val)]=self._get_ones(row, col, val) return dlx_matrix def _get_ones(self, row, col, val): blk = (row//3)*3 + col//3 ones = [row*9+col+self.GRIDOFFSET, row*9+val+self.ROWOFFSET, col*9+val+self.COLOFFSET, blk*9+val+self.BLKOFFSET] return ones if __name__=="__main__": puzzle = "4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......" solver = SudokuSolver() res = solver.solve(puzzle) for i in range(9): print res[i*9: i*9+9]
最后最后,这里[3]提供了一个30行的dlx的python代码,非常的精致,建议大家都去看一看~!
__________________________________________
[1]Dancing Links, Donald E. Knuth(附件下载)
[2]http://cgi.cse.unsw.edu.au/~xche635/dlx_sodoku/
[3]http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html
发表评论
-
我对KM算法的理解
2012-12-26 15:47 25848一般对KM算法的描述, ... -
一个小题目(单词统计)
2012-08-14 23:12 1316今天休息的时候看到一个关于单词统计的小题目: 统计一段由字符 ... -
数独人工解法的一些技巧及其python实现
2012-06-13 16:31 6602这段日子实现了十几种 ... -
Eva'Sudoku-0.1新鲜出炉啦~~
2012-05-27 21:06 1328呵呵,经过将近一个星期的对pygame的了解与熟悉,我终于磕磕 ... -
产生数独迷题
2012-05-24 18:13 1960随着数独解题算法DLX的 ... -
总共有多少个数独?
2012-05-12 15:31 12741憋屈地看了一个星期的 ... -
编程之美续
2012-04-06 15:37 1115看完编程之美后看很多题,都会发现原来只是里面一些题目的变种(也 ... -
编程之美
2012-04-02 16:54 1411前段日子又看了编程之美,后来闲着无聊学python去了,想着书 ... -
数据结构——2-3树
2012-02-10 14:25 7143年前实现了一个2-3树, ... -
数据结构 -- 二叉树(BST, AVLTree, RBTree, SplayTree)
2012-01-17 21:31 2761在《基于树的索引结构介绍》(http://philoscien ... -
编程珠玑--关于查找(二分法、自组织链、哈希)
2011-12-31 19:36 2104查找是我们现实生活中 ... -
编程珠玑 -- 关于堆
2011-12-28 15:31 1133堆是这样一种数据结构,它首先是一棵二叉树,而且还是一棵完全二叉 ... -
编程珠玑 -- 关于排序
2011-12-27 20:12 976《编程珠玑》主要提到 ... -
Heritrix总结及消重算法初探
2011-06-02 12:38 2616好久没有更新博客了。最后一次更新居然已经是一个月以前的事了。忍 ... -
图论--旅行商问题
2011-05-04 14:57 1462五一果然基本献给了数据压缩(除了两个晚上用于打球),看了小波的 ... -
图论--寻找欧拉回路
2011-04-27 21:05 1782首先介绍一下fleury算法。 大概描述是这样子的: (1 ... -
图论--中国邮递员问题
2011-04-27 20:25 13969中国邮递员问题就比较 ... -
图论--关键路径
2011-04-27 19:37 1834最近忙着做作业。主要是《代数与图论》的一些算法的实现,五一估计 ... -
C语言中的文件操作
2011-04-16 11:34 781常常觉得,我对很多东西都是要求会用就好,不求甚解。比如说每次一 ...
相关推荐
### ACM Dancing Link 数据结构详解 #### 一、概述 **ACM Dancing Link**(简称 DLX)是一种高效解决**精确覆盖问题**的数据结构。它在实际应用中特别适用于解决诸如**数独**这类问题,其核心思想是通过双向链表...
【标题】:“Dancing Links X”算法详解 【描述】:Dancing Links(跳舞链接)是一种高效的回溯算法,由Donald Knuth在2000年提出,主要用于解决全排列、数独等组合优化问题。它以其独特的数据结构和操作方式,显著...
标题中的"DancingLink acm 算法 跳表"是三种不同的数据结构或算法技术,它们在解决特定问题时都有其独特的作用。这里分别介绍这三个概念: 1. **DancingLink算法**:Dancing Links(舞动链接)是由Donald Knuth提出...
标题中的“java超高速解数独软件 源码”表明这是一个使用Java编程语言实现的高效数独求解器,其核心算法是Dancing Links。数独是一种逻辑推理游戏,玩家需要通过填充数字来完成一个9x9的网格,使得每一行、每一列...
"Dancing Links"是指X算法的一种实现方式,即通过链表的数据结构解决精确覆盖问题。在此问题中,骑士遍历问题即马踏棋盘问题,是该算法的一个应用场景。该问题要求马在8*8的国际象棋盘上进行移动,且每个方格只能...
let L[x] and R[x] point to the predecessor and successor of that element. Then the operations L R[x] ← L[x], R L[x] ← R[x] (1) remove x from the list; every programmer knows this. But comparatively...
在 Dancing Links 中,链接表示一个解的元素,取消链接则代表回溯。算法通过操作这些链接来控制搜索过程。当一个元素被选择时,与其相关的所有列头节点都会被链接;当元素不再满足条件时,这些链接会被取消,从而...
### Dancing Links中文版:一种高效的回溯算法应用 #### 精确覆盖问题与Dancing Links Dancing Links,简称DLX,是由Donald E. Knuth教授在斯坦福大学提出的一种算法,主要用于解决精确覆盖问题(Exact Cover ...
标题与描述中的“Dancing Links”(舞动链接)是一种数据结构操作技术,由计算机科学领域的传奇人物Donald E. Knuth在2000年提出。该技术特别适用于解决回溯算法中的问题,如N皇后问题等。Knuth在文章中强调了这种...
第四卷的第五册《C语言版Dancing Links1》专注于一种高效的算法——Dancing Links(舞蹈链接)。这个算法是解决回溯问题,特别是全排列、组合和子集问题的有效工具。Dancing Links是一种基于链表的数据结构,它巧妙...
标题中的“dancing rose.rar”多次出现,暗示这是一个与“dancing rose”相关的压缩文件,可能包含特定的程序或数据。描述中同样如此,但并未提供额外信息。标签“dancing rose”进一步确认了主题。从压缩包子文件的...
提供dancing links 的模板,适合ACMer 使用,
该游戏为《跳舞的线》的...下载后进入文件夹,双击 ”Dancing Line.exe“ 开始游戏。进入游戏后,在start game菜单中选择关卡。Chinese Garden,Piano关卡仍在设计中,Winter关卡可以正常游玩。游戏支持玩家自制关卡。
**Dancing Links 算法详解** Dancing Links(舞动链接)算法,由Donald Knuth教授提出,是一种用于解决完全回溯问题的有效方法,尤其在处理0-1背包问题、N皇后问题等经典计算机科学难题时表现出色。这个算法的名字...
该游戏为《跳舞的线》的自制复刻版,仅用于学习用途,不产生任何商业...下载后进入文件夹,双击 ”Dancing Line.exe“ 开始游戏。Chinese Garden与Piano关卡仍在设计中,Winter关卡可以正常游玩。游戏支持玩家自制关卡