import?java.util.ArrayList;
import?java.util.List;
import?java.util.Stack;
import?java.util.TreeSet;

public?class?Search?{
	/**
	?*?@param?args
	?*/
	public?TreeSet?open?=?new?TreeSet（）;
	public?List?closed?=?new?ArrayList（）;

	//?修改測試數據?1：（來源書上）
	//?int[]?start_array?=?{?2?8?3?1?0?4?7?6?5?};
	//?int[]?end_array?=?{?1?2?3?8?0?4?7?6?5?};

	//?修改測試數據?2：（來源書上）
	int[]?start_array?=?{?8?0?3?2?1?4?7?6?5?};
	int[]?end_array?=?{?1?2?3?8?0?4?7?6?5?};

	public?StateNode?start?=?new?StateNode（start_array）;
	public?StateNode?end?=?new?StateNode（end_array）;

	public?boolean?init（）?{
		if?（isAbleSearch（start?end））?{
			StateInvaluate.setStatevaluate（start?end）;
			open.add（start）;
			return?true;
		}?else
			return?false;
	}

	public?boolean?isAbleSearch（StateNode?start?StateNode?end）?{
		//?初始和目標的逆序數同偶或同奇可解
		int?s1?=?0?s2?=?0;
		for?（int?i?=?0;?i?			for?（int?j?=?i;?j?>=?0;?j--）?{
				if?（start.blocks[i]?>?start.blocks[j]
						&&?start.no_block_position?!=?i
						&&?start.no_block_position?!=?j）
					s1++;
				if?（end.blocks[i]?>?end.blocks[j]?&&?end.no_block_position?!=?i
						&&?end.no_block_position?!=?j）
					s2++;
			}
		}
		return?（s1?%?2?==?s2?%?2）;
	}

	private?void?outputResult（Stack?solvepath）?{
		//?TODO?Auto-generated?method?stub
		System.out.println（“初始狀態：\n“?+?start）;
		System.out.println（“目標狀態：\n“?+?end）;
		System.out.println（“===================移動路徑如下：===================\n“）;
		int?i?=?1;
		while?（!solvepath.isEmpty（））?{
			System.out.println（“第“?+?（i++）?+?“步：“）;
			System.out.println（solvepath.pop（））;
		}

	}

	public?static?void?main（String[]?args）?{
		//?TODO?Auto-generated?method?stub
		Search?search?=?new?Search（）;

		//?判斷是否可解
		if?（!search.init（））?{
			System.out.println（“cannot?search?solution!!“）;
			System.exit（0）;
		}

		//?搜索解
		StateNode?temp?=?null;
		while?（!search.open.isEmpty（））?{
			temp?=?search.open.first（）;
			search.open.remove（temp）;
			if?（temp.equals（search.end））
				break;
			StateGenerator.setChildState（temp）;
			for?（int?i?=?0;?i?				if?（!search.closed.contains（temp.childs.get（i）））?{
					StateInvaluate.setStatevaluate（temp.childs.get（i）
							search.end）;
					if?（!search.open.contains（temp））
						search.open.add（temp.childs.get（i））;
				}
			}
			search.closed.add（temp）;
		}

		//?構建解路徑
		Stack?solvepath?=?new?Stack（）;
		while?（temp?!=?null）?{
			solvepath.push（temp）;
			temp?=?temp.parent;
		}

		//?輸出結果
		search.outputResult（solvepath）;
	}

}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????3106??2010-05-02?00:00??八數碼\bin\Search.class

?????文件???????1333??2010-05-02?00:00??八數碼\bin\StateGenerator.class

?????文件???????1009??2010-05-02?00:00??八數碼\bin\StateInvaluate.class

?????文件???????2057??2010-05-02?00:00??八數碼\bin\StateNode.class

?????文件??????24566??2010-05-03?10:02??八數碼\IA實驗報告.docx

?????文件???????2778??2010-04-06?11:19??八數碼\src\Search.java

?????文件???????1900??2010-04-04?18:01??八數碼\src\StateGenerator.java

?????文件???????1341??2010-04-04?18:01??八數碼\src\StateInvaluate.java

?????文件???????1931??2010-04-06?11:21??八數碼\src\StateNode.java

?????文件????????433??2010-04-06?11:18??八數碼\實驗結果演示.bat

?????目錄??????????0??2010-05-03?10:02??八數碼\bin

?????目錄??????????0??2010-05-03?10:02??八數碼\src

?????目錄??????????0??2010-05-03?10:02??八數碼

-----------?---------??----------?-----??----

????????????????40454????????????????????13