Title :
A constructive proof for the subsets completeness of 8-puzzle state space
Author_Institution :
Sch. of Electron. & Inf. Eng., Xi´´an Jiaotong Univ., Xi´´an, China
Abstract :
Based on the mathematical analysis, the accessibility between various states in 8-puzzle state space is discussed in this paper. A necessary and sufficient condition in which the states can be transformed into each other is proposed, and its correctness is proved. On the basis of which, a complete mathematical structure of the 8-puzzle state space is esta-blished by utilizing the accessible relation as an equivalence relation. Furthermore, a valid deduction is given, that is, for the 7 numbers that are in a Style Box, each of their states can be transformed into each other.
Keywords :
equivalence classes; mathematical analysis; set theory; 8-puzzle state space; constructive proof; equivalence relation; mathematical analysis; subset completeness; US Department of Energy; 8-puzzle problem; construction of path;
Conference_Titel :
Artificial Intelligence and Education (ICAIE), 2010 International Conference on
Conference_Location :
Hangzhou
Print_ISBN :
978-1-4244-6935-2
DOI :
10.1109/ICAIE.2010.5641085
