package?eightPuzzle;
?
import?java.util.HashMap;
import?java.util.HashSet;
import?java.util.Map;
import?java.util.Queue;
import?java.util.Set;
import?java.util.Stack;
import?java.util.concurrent.linkedBlockingDeque;
?
?
public?class?EightPuzzle
{
???private?String?targetState?=?““;//目標狀態
???private?int[][]?startMatrix?=?new?int[3][3];//目標矩陣
???private?int[][]?targetMatrix?=?new?int[3][3];//目標矩陣
???private?Set?hashState?=?new?HashSet（）;//判斷狀態是否出現
???private?int[]?dx?=?{-1010};
???private?int[]?dy?=?{010-1};
???private?Map?path?=?new?HashMap（）;
???private?int?step?=?0;
???/**
????*?求狀態矩陣除去0后的逆序數
????*?@param?Matrix?狀態矩陣
????*?yle=“font-size:14px;“>@returnyle=“font-size:14px;“>?????狀態矩陣除去0位置的逆序數
????*/
???public?EightPuzzle（）{
	???int?k?=?0;
	???for（int?i?=?0;?i????????{
???????????for（int?j?=?0;?j????????????{
????????	???startMatrix[i][j]?=?EightPuzzleframe.startArray[k];
????????	???targetMatrix[i][j]?=?EightPuzzleframe.endArray[k];
????????	???targetState?+=?EightPuzzleframe.endArray[k];
????????	???k++;
???????????}
???????}
???}
???
???private?int?countInverseNumber（int[][]?Matrix）
???{
???????int[]?tmpElem?=?new?int[9];
???????int?size?=?0;
???????for（int?i?=?0;?i????????{
???????????for（int?j?=?0;?j????????????{
???????????????if（Matrix[i][j]?!=?0）
???????????????{
???????????????????tmpElem[size++]?=?Matrix[i][j];
???????????????}
???????????}
???????}
???????int?ans?=?0;
???????for（int?i?=?0;?i????????{
???????????for（int?j?=?i+1;?j????????????{
???????????????if（tmpElem[i]?>?tmpElem[j]）
???????????????{
???????????????????ans++;
???????????????}
???????????}
???????}
???????return?ans;
???}
????
???/**
????*?判斷是否可以由初始的8數碼狀態到目標狀態
????*?@param?startMatrix?初始化8數碼的狀態矩陣
????*?yle=“font-size:14px;“>@returnyle=“font-size:14px;“>?????是否可以求解
????*/
???private?boolean?isCanSolve（）
???{
???????return?（countInverseNumber（startMatrix）?%?2?==?（countInverseNumber（targetMatrix）%2））;
???}
????
???/**
????*?把存儲8數碼的矩陣轉換為狀態字符串
????*?@param?Matrix?8數碼存儲矩陣
????*?yle=“font-size:14px;“>@returnyle=“font-size:14px;“>?????狀態字符串
????*/
???private?String?convertToStrState（int[][]?Matrix）
???{
???????String?string?=?““;
???????for（int?i?=?0;?i????????{
???????????for（int?j?=?0;?j????????????{
???????????????string?+=?Matrix[i][j];
???????????}
???????}
???????return?string;
???}

???private?int[][]?convertToMatrix（String?state）
???{
???????int[][]?matrix?=?new?int[3][3];
???????for（int?i?=?0;?i????

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2015-04-26?17:51??人工智能作業\
?????目錄???????????0??2015-04-26?19:56??人工智能作業\八數碼（寬度優先）\
?????目錄???????????0??2015-04-26?17:57??人工智能作業\八數碼（寬度優先）\AIhomework1\
?????文件?????????301??2015-04-24?12:44??人工智能作業\八數碼（寬度優先）\AIhomework1\.classpath
?????文件?????????387??2015-04-26?17:54??人工智能作業\八數碼（寬度優先）\AIhomework1\.project
?????目錄???????????0??2015-04-26?17:57??人工智能作業\八數碼（寬度優先）\AIhomework1\.settings\
?????文件?????????598??2015-04-24?12:44??人工智能作業\八數碼（寬度優先）\AIhomework1\.settings\org.eclipse.jdt.core.prefs
?????目錄???????????0??2015-04-26?17:57??人工智能作業\八數碼（寬度優先）\AIhomework1\bin\
?????目錄???????????0??2015-04-26?17:57??人工智能作業\八數碼（寬度優先）\AIhomework1\bin\eightPuzzle\
?????文件????????5093??2015-04-26?17:55??人工智能作業\八數碼（寬度優先）\AIhomework1\bin\eightPuzzle\EightPuzzle.class
?????文件????????1193??2015-04-26?17:54??人工智能作業\八數碼（寬度優先）\AIhomework1\bin\eightPuzzle\EightPuzzleframe$1.class
?????文件?????????738??2015-04-26?17:54??人工智能作業\八數碼（寬度優先）\AIhomework1\bin\eightPuzzle\EightPuzzleframe$2$1.class
?????文件????????1345??2015-04-26?17:54??人工智能作業\八數碼（寬度優先）\AIhomework1\bin\eightPuzzle\EightPuzzleframe$2.class
?????文件?????????744??2015-04-26?17:54??人工智能作業\八數碼（寬度優先）\AIhomework1\bin\eightPuzzle\EightPuzzleframe$3.class
?????文件????????3757??2015-04-26?17:54??人工智能作業\八數碼（寬度優先）\AIhomework1\bin\eightPuzzle\EightPuzzleframe.class
?????目錄???????????0??2015-04-26?17:57??人工智能作業\八數碼（寬度優先）\AIhomework1\src\
?????目錄???????????0??2015-04-26?17:57??人工智能作業\八數碼（寬度優先）\AIhomework1\src\eightPuzzle\
?????文件????????6817??2015-04-26?17:55??人工智能作業\八數碼（寬度優先）\AIhomework1\src\eightPuzzle\EightPuzzle.java
?????文件????????4221??2015-04-24?15:22??人工智能作業\八數碼（寬度優先）\AIhomework1\src\eightPuzzle\EightPuzzleframe.java
?????文件????????8980??2015-04-29?22:19??人工智能作業\八數碼（寬度優先）\eightPuzzle.jar
?????文件??????????43??2015-04-26?19:38??人工智能作業\八數碼（寬度優先）\start.bat
?????文件??????????72??2015-04-26?19:56??人工智能作業\八數碼（寬度優先）\點擊這個運行.vbs
?????目錄???????????0??2015-04-26?19:50??人工智能作業\正交輸入模式集\
?????目錄???????????0??2015-04-26?17:57??人工智能作業\正交輸入模式集\AIhomework2\
?????文件?????????301??2015-04-24?12:44??人工智能作業\正交輸入模式集\AIhomework2\.classpath
?????文件?????????387??2015-04-26?17:54??人工智能作業\正交輸入模式集\AIhomework2\.project
?????目錄???????????0??2015-04-26?17:57??人工智能作業\正交輸入模式集\AIhomework2\.settings\
?????文件?????????598??2015-04-24?12:44??人工智能作業\正交輸入模式集\AIhomework2\.settings\org.eclipse.jdt.core.prefs
?????目錄???????????0??2015-04-26?17:57??人工智能作業\正交輸入模式集\AIhomework2\bin\
?????目錄???????????0??2015-04-26?17:57??人工智能作業\正交輸入模式集\AIhomework2\bin\hebb\
?????文件????????2652??2015-04-26?17:55??人工智能作業\正交輸入模式集\AIhomework2\bin\hebb\Hebb.class
............此處省略5個文件信息