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;
}