State Space and Optimal Solution of Jigsaw Puzzle

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)

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  -