Skip to content

andrewrong/dancing-links-

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

6 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

这个小程序是我在玩android中的一个小游戏(Tangram polyomino)中的时候想到的.游戏本身主要是给与你一些类似于俄罗斯方块中的那些形状的方块,要求是要使用这些形状的方块去完成某一个特定的形状的拼图.当然这个程序本身就是使用dancing links这个算法去实现自动的寻找结果的功能.

核心算法:
    这部分的程序主要有dancing_link.c和dancing_link.h组成.
    matriccvtlinks:将矩阵转化成算法所要的数据结构
    search:开始搜索解
    display:用来调试的时候使用的一个输出的函数
    free_links:释放中间的一些动态产生的内存空间
    display_key:这个主要是用来将解用一种比较直观的形式展示出来

显示问题展示成算法能解决的一个初始化的过程:
    init:初始化一些中间使用的数据
    get_possible:用来获得所有的可能性,主要用来计算后面的矩阵的行的个数
    init_matrix:将实际问题变成矩阵
    matrix_display:调试使用,用来显示矩阵本身
    free_matrix:用来释放中间的内存空间

/mem:
    这个下面的代码主要是对malloc,free这两个函数进行了封装

使用方法:
    这个小程序本身如果要使用的话会存在一定的问题,由于本身程序面向的那个游戏所以如果你要用来解决其他问题就必须自己重写关于实际问题到矩阵的那个步骤,不过核心算法那个部分是可以使用的.还有就是如果你想它用来解那个游戏的问题,你必须去看看init_shape这个函数,因为游戏中的形状和个数是不一定的,所以程序本身是动态变化的.不过我想这个程序也就我一个人会使用的....

About

dancing links 算法应用于拼图问题

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages