Proceedings of the 2017 2nd International Conference on Control, Automation and Artificial Intelligence (CAAI 2017)

State Space and Optimal Solution of Jigsaw Puzzle

Authors
Zhongping Liu, Xiaoyuan Liu
Corresponding Author
Zhongping Liu
Available Online June 2017.
DOI
10.2991/caai-17.2017.107How to use a DOI?
Keywords
jigsaw puzzle; eight digits; breadth first tree; inverse number; two-dimensional bubbling
Abstract

this paper hopes to find a planning algorithm for puzzle which is not based on search. The main idea is using the method of reducing dimension to decompose the puzzle. Firstly, we defined the jigsaw puzzle as discrete state space, and provided the functions of action space generation and state transformation; secondly, we built two breadth first trees through goal-driven strategies. One is a set of state spaces which are solvable, and another is a set of state spaces which have non solution; thirdly, a theorem for determining whether state space have a solution was obtained through extracting feature of inverse number from state spaces, and then we proposed an initialization algorithm which can get solvable state surely; Finally, we suggested a method to reduce the dimension step by step, and put forward a two-dimensional bubbling algorithm. Experiments show that this algorithm is simple and effective, and the results meet expectations.

Copyright
© 2017, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

Volume Title
Proceedings of the 2017 2nd International Conference on Control, Automation and Artificial Intelligence (CAAI 2017)
Series
Advances in Intelligent Systems Research
Publication Date
June 2017
ISBN
978-94-6252-360-9
ISSN
1951-6851
DOI
10.2991/caai-17.2017.107How to use a DOI?
Copyright
© 2017, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Cite this article

TY  - CONF
AU  - Zhongping Liu
AU  - Xiaoyuan Liu
PY  - 2017/06
DA  - 2017/06
TI  - State Space and Optimal Solution of Jigsaw Puzzle
BT  - Proceedings of the 2017 2nd International Conference on Control, Automation and Artificial Intelligence (CAAI 2017)
PB  - Atlantis Press
SP  - 475
EP  - 479
SN  - 1951-6851
UR  - https://doi.org/10.2991/caai-17.2017.107
DO  - 10.2991/caai-17.2017.107
ID  - Liu2017/06
ER  -