3拼图算法
1. 九宫格拼图·求此问题解法~~思路~代码都可~~就是关于其还原算法的·急~在线等~多谢哈
http://www.cublog.cn/u/8780/showart.php?id=163291
在一个3×3的九宫中有1－8这8个数及一个空格随机的摆放在其中的格子里，如图1－1所示。现在要求实现这个问题：将其调整为如图1－1右图所示的形式。调整的规则是：每次只能将与空格（上、下、或左、右）相邻的一个数字平移到空格中。试编程实现这一问题的求解。
（图1－1）
二、题目分析：
这是人工智能中的经典难题之一，问题是在3×3方格棋盘中，放8格数，剩下的没有放到的为空，每次移动只能是和相邻的空格交换数。程序自动产生问题的初始状态，通过一系列交换动作将其转换成目标排列（如下图1－2到图1－3的转换）。
（图1－2） （图1－3）
该问题中，程序产生的随机排列转换成目标共有两种可能，而且这两种不可能同时成立，也就是奇数排列和偶数排列。可以把一个随机排列的数组从左到右从上到下用一个一维数组表示，如上图1－2我们就可以表示成｛8，7，1，5，2，6，3，4，0｝其中0代表空格。
在这个数组中我们首先计算它能够重排列出来的结果，公式就是：
∑（F（X））＝Y，其中F（X）
是一个数前面比这个数小的数的个数,Y为奇数和偶数时各有一种解法。（八数码问题是否有解的判定 ）
上面的数组可以解出它的结果。
F（8）＝0；
F（7）＝0；
F（1）＝0；
F（5）＝1；
F（2）＝1；
F（6）＝3；
F（3）＝2；
F（4）＝3；
Y＝0＋0＋0＋1＋1＋3＋2＋3＝10
Y＝10是偶数，所以其重排列就是如图1－3的结果，如果加起来的结果是奇数重排的结果就是如图1－1最右边的排法。
三、算法分析
求解方法就是交换空格（0）位置，直至到达目标位置为止。图形表示就是：
（图3－1）
要想得到最优的就需要使用广度优先搜索，九宫的所以排列有9！种，也就是362880种排法，数据量是非常大的，使用广度搜索，需要记住每一个结点的排列形式，要是用数组记录的话会占用很多的内存，可以把数据进行适当的压缩。使用DWORD形式保存，压缩形式是每个数字用3位表示，这样就是3×9＝27个字节，由于8的二进制表示形式1000，不能用3位表示，使用了一个小技巧就是将8表示为000，然后用多出来的5个字表示8所在的位置，就可以用DWORD表示了。用移位和或操作将数据逐个移入，比乘法速度要快点。定义了几个结果来存储遍历到了结果和搜索完成后保存最优路径。
类结构如下：
class CNineGird
{
public:
struct PlaceList
{
DWORD Place;
PlaceList* Left;
PlaceList* Right;
};
struct Scanbuf
{
DWORD Place;
int ScanID;
};
struct PathList
{
unsigned char Path[9];
};
private:
PlaceList *m_pPlaceList;
Scanbuf *m_pScanbuf;
RECT m_rResetButton;
RECT m_rAutoButton;
public:
int m_iPathsize;
clock_t m_iTime;
UINT m_iStepCount;
unsigned char m_iTargetChess[9];
unsigned char m_iChess[9];
HWND m_hClientWin;
PathList *m_pPathList;
bool m_bAutoRun;
private:
inline bool AddTree(DWORD place , PlaceList*& parent);
void FreeTree(PlaceList*& parent);
inline void ArrayToDword(unsigned char *array , DWORD & data);
inline void DwordToArray(DWORD data , unsigned char *array);
inline bool MoveChess(unsigned char *array , int way);
bool EstimateUncoil(unsigned char *array);
void GetPath(UINT depth);
public:
void MoveChess(int way);
bool ComputeFeel();
void ActiveShaw(HWND hView);
void DrawGird(HDC hDC , RECT clientrect);
void DrawChess(HDC hDC , RECT clientrect);
void Reset();
void OnButton(POINT pnt , HWND hView);
public:
CNineGird();
~CNineGird();
};
计算随机随机数组使用了vector模板用random_shuffle（，）函数来打乱数组数据，并计算目标结果是什么。代码：
void CNineGird::Reset()
{
if(m_bAutoRun) return;
vector vs;
int i;
for (i = 1 ; i < 9 ; i ++)
vs.push_back(i);
vs.push_back(0);
random_shuffle(vs.begin(), vs.end());
random_shuffle(vs.begin(), vs.end());
for ( i = 0 ; i < 9 ; i ++)
{
m_iChess[i] = vs[i];
}
if (!EstimateUncoil(m_iChess))
{
unsigned char array[9] = {1,2,3,8,0,4,7,6,5};
memcpy(m_iTargetChess , array , 9);
}
else
{
unsigned char array[9] = {1,2,3,4,5,6,7,8,0};
memcpy(m_iTargetChess , array , 9);
}
m_iStepCount = 0;
}
数据压缩函数实现：
inline void CNineGird::ArrayToDword(unsigned char *array , DWORD& data)
{
unsigned char night = 0;
for ( int i = 0 ; i < 9 ; i ++)
{
if (array[i] == 8)
{
night = (unsigned char)i;
break;
}
}
array[night] = 0;
data = 0;
data = (DWORD)((DWORD)array[0] << 29 | (DWORD)array[1] << 26 |
(DWORD)array[2] << 23 | (DWORD)array[3] << 20 |
(DWORD)array[4] << 17 | (DWORD)array[5] << 14 |
(DWORD)array[6] << 11 | (DWORD)array[7] << 8 |
(DWORD)array[8] << 5 | night);
array[night] = 8;
}
解压缩时跟压缩正好相反，解压代码：
inline void CNineGird::DwordToArray(DWORD data , unsigned char *array)
{
unsigned char chtem;
for ( int i = 0 ; i < 9 ; i ++)
{
chtem = (unsigned char)(data >> (32 - (i + 1) * 3) & 0x00000007);
array[i] = chtem;
}
chtem = (unsigned char)(data & 0x0000001F);
array[chtem] = 8;
}
由于可扩展的数据量非常的大，加上在保存的时候使用的是DWORD类型，将每一步数据都记录在一个排序二叉树中，按从小到大从左到有的排列，搜索的时候跟每次搜索将近万次的形式比较快几乎是N次方倍，把几个在循环中用到的函数声明为内联函数，并在插入的时候同时搜索插入的数据会不会在树中有重复来加快总体速度。二叉树插入代码：
inline bool CNineGird::AddTree(DWORD place , PlaceList*& parent)
{
if (parent == NULL)
{
parent = new PlaceList();
parent->Left = parent->Right = NULL;
parent->Place = place;
return true;
}
if (parent->Place == place)
return false;
if (parent->Place > place)
{
return AddTree(place , parent->Right);
}
return AddTree(place , parent->Left);
}
计算结果是奇数排列还是偶数排列的代码：
bool CNineGird::EstimateUncoil(unsigned char *array)
{
int sun = 0;
for ( int i = 0 ; i < 8 ; i ++)
{
for ( int j = 0 ; j < 9 ; j ++)
{
if (array[j] != 0)
{
if (array[j] == i +1 )
break;
if (array[j] < i + 1)
sun++;
}
}
}
if (sun % 2 == 0)
return true;
else
return false;
}
移动到空格位的代码比较简单，只要计算是否会移动到框外面就可以了，并在移动的时候顺便计算一下是不是已经是目标结果，这是用来给用户手工移动是给与提示用的，代码：
inline bool CNineGird::MoveChess(unsigned char *array , int way)
{
int zero , chang;
bool moveok = false;
for ( zero = 0 ; zero < 9 ; zero ++)
{
if (array[zero] == 0)
break;
}
POINT pnt;
pnt.x = zero % 3;
pnt.y = int(zero / 3);
switch(way)
{
case 0 : //up
if (pnt.y + 1 < 3)
{
chang = (pnt.y + 1) * 3 + pnt.x ;
array[zero] = array[chang];
array[chang] = 0;
moveok = true;
}
break;
case 1 : //down
if (pnt.y - 1 > -1)
{
chang = (pnt.y - 1) * 3 + pnt.x ;
array[zero] = array[chang];
array[chang] = 0;
moveok = true;
}
break;
case 2 : //left
if (pnt.x + 1 < 3)
{
chang = pnt.y * 3 + pnt.x + 1;
array[zero] = array[chang];
array[chang] = 0;
moveok = true;
}
break;
case 3 : //right
if (pnt.x - 1 > -1)
{
chang = pnt.y * 3 + pnt.x - 1;
array[zero] = array[chang];
array[chang] = 0;
moveok = true;
}
break;
}
if (moveok && !m_bAutoRun)
{
m_iStepCount ++ ;
DWORD temp1 ,temp2;
ArrayToDword(array , temp1);
ArrayToDword(m_iTargetChess , temp2);
if (temp1 == temp2)
{
MessageBox(NULL , "你真聪明这么快就搞定了!" , "^_^" , 0);
}
}
return moveok;
}
在进行广度搜索时候，将父结点所在的数组索引记录在子结点中了，所以得到目标排列的时候，只要从子结点逆向搜索就可以得到最优搜索路径了。用变量m_iPathsize来记录总步数，具体函数代码：
void CNineGird::GetPath(UINT depth)
{
int now = 0 , maxpos = 100 ;
UINT parentid;
if (m_pPathList != NULL)
{
delete[] m_pPathList;
}
m_pPathList = new PathList[maxpos];
parentid = m_pScanbuf[depth].ScanID;
DwordToArray(m_pScanbuf[depth].Place , m_pPathList[++now].Path);
while(parentid != -1)
{
if (now == maxpos)
{
maxpos += 10;
PathList * temlist = new PathList[maxpos];
memcpy(temlist , m_pPathList , sizeof(PathList) * (maxpos - 10));
delete[] m_pPathList;
m_pPathList = temlist;
}
DwordToArray(m_pScanbuf[parentid].Place , m_pPathList[++now].Path);
parentid = m_pScanbuf[parentid].ScanID;
}
m_iPathsize = now;
}
动态排列的演示函数最简单了，为了让主窗体有及时刷新的机会，启动了一个线程在需要主窗体刷新的时候，用Slee（UINT）函数来暂停一下线程就可以了。代码：
unsigned __stdcall MoveChessThread(LPVOID pParam)
{
CNineGird * pGird = (CNineGird *)pParam;
RECT rect;
pGird->m_iStepCount = 0;
::GetClientRect(pGird->m_hClientWin , &rect);
for ( int i = pGird->m_iPathsize ; i > 0 ; i --)
{
memcpy(pGird->m_iChess , pGird->m_pPathList[i].Path , 9);
pGird->m_iStepCount ++;
InvalidateRect( pGird->m_hClientWin , &rect , false);
Sleep(300);
}
char msg[100];
sprintf(msg , "^_^ ! 搞定了!\r\n计算步骤用时%d毫秒" , pGird->m_iTime);
MessageBox(NULL , msg , "~_~" , 0);
pGird->m_bAutoRun = false;
return 0L;
}
最后介绍一下搜索函数的原理，首先得到源数组，将其转换成DWORD型，与目标比较，如果相同完成，不同就交换一下数据和空格位置，加入二叉树，搜索下一个结果，直到没有步可走了，在搜索刚刚搜索到的位置的子位置，这样直到找到目标结果为止，函数：
bool CNineGird::ComputeFeel()
{
unsigned char *array = m_iChess;
UINT i;
const int MAXSIZE = 362880;
unsigned char temparray[9];
DWORD target , fountain , parent , parentID = 0 , child = 1;
ArrayToDword(m_iTargetChess , target);
ArrayToDword(array , fountain);
if (fountain == target)
{
return false;
}
if (m_pScanbuf != NULL)
{
delete[] m_pScanbuf;
}
m_pScanbuf = new Scanbuf[MAXSIZE];
AddTree(fountain ,m_pPlaceList);
m_pScanbuf[ 0 ].Place = fountain;
m_pScanbuf[ 0 ].ScanID = -1;
clock_t tim = clock();
while(parentID < MAXSIZE && child < MAXSIZE)
{
parent = m_pScanbuf[parentID].Place;
for ( i = 0 ; i < 4 ; i ++) // 0 :UP , 1:Down ,2:Left,3:Right
{
DwordToArray(parent , temparray);
if (MoveChess(temparray,i)) //是否移动成功
{
ArrayToDword(temparray , fountain);
if (AddTree(fountain, m_pPlaceList)) //加入搜索数
{
m_pScanbuf[ child ].Place = fountain;
m_pScanbuf[ child ].ScanID = parentID;
if (fountain == target) //是否找到结果
{
m_iTime = clock() - tim;
GetPath(child);//计算路径
FreeTree(m_pPlaceList);
delete[] m_pScanbuf;
m_pScanbuf = NULL;
return true;
}
child ++;
}
}
} // for i
parentID++;
}
m_iTime = clock() - tim;
FreeTree(m_pPlaceList);
delete[] m_pScanbuf;
m_pScanbuf = NULL;
return false;
}
重要函数的介绍结束;下面是程序的运行结果和运算结果：
2. 急急急，算法高手进，关于拼图算法
参考POJ1077题解网上都是
一般做法就是遍历和a星算法
具体资料多看看吧我就不贴了
没编程基础还是比较难搞懂的！～
希望对你有帮助
3. 觅算法－－数字拼图算法
LZ可以来这里看一下,说明很生动的,呵呵,而且也有源代码
http://www.cublog.cn/u/8780/showart.php?id=163291
4. 拼图游戏算法分析
BFS算法。
队列初始化
Repeat
h=当前状态
for a=1 to 4 do begin
生成下一个目标
加入队列
康托展开计算hash码，标记访问和步数
如果达到目标则退出过程
end
h退出队列
until 队列空
说明：队列就是从头进从尾出的一种线性数据结构，不懂自己查
康托展开不懂自己查，这个hash是必要的，不然不能在要求时间内解决问题。
bfs算法应该就不错。A*不能得到最优解。
5. 用c语言拼图编程程序，或者算法
你好，我写了一个C++的，在VS上完美运行，希望能够帮到你。
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<time.h>
/*定义全局变量*/
intpuzz[9]; //九格游戏数组
inti=0,j,k; //i初始化界面的提示语，j获取空格位置，k移动次数
intspace; //空缺位置
/*自定义函数原型*/
voidinterface(); //界面，包括打印充填矩形和数字
voidchange(inta,intb); //交换
voidpress(); //按键
voidstart() ; //初始化和判断是否胜利
voidstart() //初始化和判断是否胜利
{
inta,b,c;
intstar[22]={300,120,320,160,360,160,320,200,340,240,300,200,260,240,280,200,240,160,280,160,300,120};
k=0;
for(a=0;a<8;a++)
puzz[a]=a+1;
puzz[8]=0;
interface();
for(c=0;c<100;c++) //随机打乱顺序
{
a=rand()%9;
b=(a+2)%8; //关于有无解问题，搞不清楚，引用的
change(a,b);
}
while(1)
{
interface();
for(a=0;a<8;a++)
if(puzz[a]!=a+1)
break;
if(a==8)
{
drawpoly(11,star); //五角星
setcolor(1); //文本“SUCCESSFUL”颜色
setfillstyle(1,4); //五角星填充色
floodfill(300,150,15); //五角星内一点
outtextxy(260,180,"SUCCESSFUL!!");
getch();
start();
}
for(j=0;j<=8;j++)
if(puzz[j]==0)
break;
space=j;
press();
}
}
voidinterface() //界面，包括打印充填矩形和数字
{
clearviewport(); //清楚屏幕图形
setbkcolor(6); //设置背景色
setfillstyle(2,2); //矩形块颜色
if(puzz[0]!=0)
bar(160,60,240,140);
if(puzz[1]!=0)
bar(260,60,340,140);
if(puzz[2]!=0)
bar(360,60,440,140);
if(puzz[3]!=0)
bar(160,160,240,240);
if(puzz[4]!=0)
bar(260,160,340,240);
if(puzz[5]!=0)
bar(360,160,440,240);
if(puzz[6]!=0)
bar(160,260,240,340);
if(puzz[7]!=0)
bar(260,260,340,340);
if(puzz[8]!=0)
bar(360,260,440,340);
gotoxy(25,7);
if(puzz[0]!=0)
printf("%d",puzz[0]);
gotoxy(38,7);
if(puzz[1]!=0)
printf("%d",puzz[1]);
gotoxy(50,7);
if(puzz[2]!=0)
printf("%d",puzz[2]);
gotoxy(25,13);
if(puzz[3]!=0)
printf("%d",puzz[3]);
gotoxy(38,13);
if(puzz[4]!=0)
printf("%d",puzz[4]);
gotoxy(50,13);
if(puzz[5]!=0)
printf("%d",puzz[5]);
gotoxy(25,19);
if(puzz[6]!=0)
printf("%d",puzz[6]);
gotoxy(38,19);
if(puzz[7]!=0)
printf("%d",puzz[7]);
gotoxy(50,19);
if(puzz[8]!=0)
printf("%d",puzz[8]);
if(i==0)
{
printf(" Pressanykeytodare");
getch();
}
gotoxy(60,4); //打印移动次数
printf("%dth",k);
i+=1;
return;
}
intmain()
{
intgdriver=VGA,gmode=VGAHI;
initgraph(&gdriver,&gmode,"c:\tc30\BGI");
srand((unsigned)time(NULL)); //播种子
clearviewport(); //清屏
printf(" ///////////////////////////// ");
printf(" ");
printf(" PUZZLEGAME ");
printf(" ");
printf(" ///////////////////////////// ");
printf(" Pressanykeytostartgame");
printf(" PressEsctoexit ");
if(getch()==27)
{
clrscr();
clearviewport();
printf(" ////////////////////////////////// ");
printf(" Seeyounexttime ");
printf(" ////////////////////////////////// ");
printf(" Pressanykeytoexit");
getch();
closegraph();
return0;
}
start();
return0;
}
6. 拼图游戏的算法（推动的拼图）FLASH版
不一定只让一个方块移动,算法可以是先把一张图片分割好,为每个方块指定一个整形的数字。然后写一个方法，让i行j列的方块随机往一个方向移动。调用这个方法若干次，效果上就像你让人家玩魔方前，自己手工把它打乱。
数据结构方面，由于AS并不支持真正的多维数组，你可以用数组的数组来存放N*N的方块:
var num:Number=10;
var blocks:Array=new Array();
var count:Number=0;
for(var i:Number=0;i<num;i++){
var row:Array=new Array();
for(var j:Number=0;j<num;j++){
row.push(count++);
}
blocks.push(row);
}
function randomMove(rowIndex:Number,colIndex:Number){
..
}
Good Luck
7. 急求拼图的算法
验完了数是否合理以后就硬上吧...
n<=5而且不能旋转,出题人已经相当仁慈了.
建一个5*5*5 boolean存片
dfs每一片
图[x,y]and片[n,x,y]=true时剪掉
应该不难的吧...
8. 3*3 型的拼图界面。数字1~8 和一个空格。要实现能拼图功能~~大概的算法是怎样的！！
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<time.h>
int main(void)
{
void swap(int *a,int *b); //子函数声明
int i,j,k,n,puzzle[81]={0},parity[81]={0}; //拼图数组和奇偶性数组
char ch; //用来记录拼图数组可以转换成顺序矩阵，还是逆序矩阵
printf("游戏说明\n");
printf("↑ ：数字向上 ↓ ：数字向下\n");
printf("← ：数字向左 → ：数字向右\n");
printf("Esc：退出程序 Space：重置矩阵\n");
printf("\n");
loop1:
printf("难度设置\nn：");
scanf("%d",&n);
loop2:
system("cls"); //清屏
srand((unsigned)time(NULL)); //动态获取数据
for(i=0;i<=n*n-1;i++)
{
loop3:
k=rand()%(n*n); //记录新的数据
for(j=0;j<i;j++) //和旧的数据进行比较，当新的数据
if(puzzle[j]==k) goto loop3; //出现过时，重新获取
if(j==i)
{
puzzle[j]=k; //当新的数据和旧的数据都不同时，将
} //数据放入拼图数组中
}
for(i=0;i<=n*n-1;i++)
{
parity[i]=puzzle[i]; //将拼图数组赋予奇偶性数组
}
for(i=0;i<=n*n-1;i++)
{
if(parity[i]==0) break; //找出奇偶性数组中0（空格）的位置
}
k=i;
for(j=1;j<=i/n;j++) //将0（空格）换到第1行
{
swap(&parity[k],&parity[k-n]);
k=k-n; //更新奇偶性数组中0（空格）的位置
}
for(j=1;j<=i%n;j++) //将0（空格）换到第1列
{
swap(&parity[k],&parity[k-1]);
k=k-1; //更新奇偶性数组中0（空格）的位置
}
k=0;
for(i=0;i<=n*n-1;i++)
for(j=i;j<=n*n-1;j++)
{
if(parity[i]>parity[j]) k++; //求奇偶性数组的“逆序数和”
}
if(k%2==0) printf("%d\n顺序矩阵",n),ch='0'; //“逆序数和”为偶数时，是顺序矩阵
else printf("%d\n逆序矩阵",n),ch='1'; //“逆序数和”为奇数时，是逆序矩阵
printf("\n");
for(i=0;i<=n*n-1;i++) //打印拼图数组
{
if(puzzle[i]==0) printf("%*c",n,' '); //是0（空格）的位置，打印空格
else printf("%-*d",n,puzzle[i]); //是数字的位置，打印对应宽度的数字
if((i+1)%n==0&&i!=n*n-1) printf("\n"); //每打印n个数字，换一行打印
}
while(1)
{
for(i=0;i<=n*n-1;i++)
{
if(puzzle[i]==0) break; //记录拼图数组中0（空格）的位置
}
switch(getch())
{
case 72:if( i<n*(n-1)) swap(&puzzle[i],&puzzle[i+n]);break; //数字向上
case 80:if( i>1*(n-1)) swap(&puzzle[i],&puzzle[i-n]);break; //数字向下
case 75:if((i+1)%n!=0) swap(&puzzle[i],&puzzle[i+1]);break; //数字向左
case 77:if((i+0)%n!=0) swap(&puzzle[i],&puzzle[i-1]);break; //数字向右
case 27:exit(0); //退出程序
case 32:goto loop2; //重置矩阵
}
system("cls"); //清屏
switch(ch)
{
case '0':printf("%d\n顺序矩阵\n",n);break; //完成拼图的最终目标
case '1':printf("%d\n逆序矩阵\n",n);break; //完成拼图的最终目标
}
for(i=0;i<=n*n-1;i++)
{
if(puzzle[i]==0) printf("%*c",n,' '); //是0（空格）的位置，打印空格
else printf("%-*d",n,puzzle[i]); //是数字的位置，打印对应宽度的数字
if((i+1)%n==0&&i!=n*n-1) printf("\n"); //每打印n个数字，换一行打印
}
for(i=0;i<=n*n-3;i++)
{
if(puzzle[i]!=i) break; //判断拼图数组是否为顺序矩阵或逆序矩阵
}
if(i==n*n-2)
{ //是顺序矩阵或是逆序矩阵时，完成拼图
printf("\n恭喜你，拼图完成了！\n"); //打印完成标志
printf("Continue(y/n)?");
if(getch()=='y')
{
system("cls"); //清屏
goto loop1; //重新开始
}
else
{
exit(0); //退出程序
}
}
}
getch(); //显示运行结果
return(0); //正常运行返回0
}
void swap(int *a,int *b)
{
int c;
c=*a;
*a=*b;
*b=c;
}