Splicing All Possible Convex and Non-convex Pentagons with Tangram using DFS
Shixu Li · 2022
The tangram is an ancient Chinese traditional intellectual toy that includes seven puzzles of different sizes and shapes. Those seven fragments can combine thousands of different shapes. However, it is known as an NP-hard problem to solve the tangram puzzle problems due to the unboundedness and multiformity. This paper provides an approach for solving all possibilities to form pentagons using Deep First Search(DFS) algorithm and other Mathematical theories, which reduce the searching counts. Specifically, a heuristic search is considered, in which the border of the pentagon can be limited to a specified area. The key point of the proposed method is to find the contours of the pentagon that meet the conditions and then to fill in the outline with 7 pieces of tangrams using the DFS algorithm. Our basic idea is to separate all 53 pentagons into 2 convex pentagons and 51 nonconvex pentagons, then separate those non-convex pentagons into those whose vertices are contained in the same orthogonal lattice (20 kinds) and whose are not (31 kinds). Our results illustrate that tangram can make at least 53 different contours and there is at least one patchwork approach in each contour using computer programming.