拼圖演算法題

1. 寫一個簡單地自動拼圖程序， 求指教裡面的演算法。

可以根據0的排列方式確定其中一種1*16,2*8,4*4,8*2,16*1
(倘若有piece的4邊都是非0的一定屬於4*4)
然後找到4個角,搜索相鄰的2個piece

2. 拼圖游戲的演算法（推動的拼圖）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

3. 滑塊拼圖游戲演算法實現

這個游戲要想單純靠程序實現不太容易，20分誰願意？加點分。
要不你用專門做這方面的軟體，靠FLASH實現不會太難。用它的命令實現是比較容易的，也不用寫什麼代碼，系統自動生成（那個命令叫什麼名字我也忘了）。

4. 關於數字拼圖的問題，什麼演算法可以找出最優的操作步驟數

先排好123，下面的只要排好65478的順序順時針轉就好。

5. 九宮格拼圖·求此問題解法~~思路~代碼都可~~就是關於其還原演算法的·急~在線等~多謝哈

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

重要函數的介紹結束;下面是程序的運行結果和運算結果：

6. 急求拼圖的演算法

驗完了數是否合理以後就硬上吧...
n<=5而且不能旋轉,出題人已經相當仁慈了.

建一個5*5*5 boolean存片

dfs每一片
圖[x,y]and片[n,x,y]=true時剪掉

應該不難的吧...

7. java 數字拼圖 演算法

要想得到最優的就需要使用廣度優先搜索，九宮的所有排列有9！種，也就是362880種排法，數據量是非常大的，使用廣度搜索，需要記住每一個結點的排列形式，要是用數組記錄的話會佔用很多的內存，可以把數據進行適當的壓縮。使用dword形式保存，壓縮形式是每個數字用3位表示，這樣就是3×9＝27個位元組，由於8的二進製表示形式1000，不能用3位表示，使用了一個小技巧就是將8表示為000，然後用多出來的5個字表示8所在的位置，就可以用dword表示了。用移位和或操作將數據逐個移入，比乘法速度要快點。定義了幾個結果來存儲遍歷到了結果和搜索完成後保存最優路徑。

8. 用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;

}

9. 拼圖游戲演算法分析

BFS演算法。

隊列初始化
Repeat
h=當前狀態
for a=1 to 4 do begin
生成下一個目標
加入隊列
康托展開計算hash碼，標記訪問和步數
如果達到目標則退出過程
end
h退出隊列
until 隊列空

說明：隊列就是從頭進從尾出的一種線性數據結構，不懂自己查

康托展開不懂自己查，這個hash是必要的，不然不能在要求時間內解決問題。

bfs演算法應該就不錯。A*不能得到最優解。