Using DFS Search and Enumerate Method to Find All Solutions in 13 Convex Figures in Tangram Game
Hongbo Wang · 2021 International Conference on Computer Information Science and Artificial Intelligence (CISAI) · 2021
Tangram, a well-known traditional puzzle, is a tool in elementary education which is often associated with creative thinking. It consists of 7 boards (five triangles, one square and one parallelogram). Using tangram, we could build over 1600 kinds of shapes, such as houses, towers, and animals. However, it is very difficult to supplement a complete graphic with 7 boards. Therefore, this program was developed. In this program, the author used the DFS search algorithm and enumeration method to find all the solutions in the 13 convex figures in the Tangram. Then the author improved this search method to make the search algorithm run faster. The program is built using the Qt application development framework and C++ computer language and uses a user interface to display all the different results about the 13 convex graphics. The result of the research is that every convex polygon made of seven boards is not unique. Some graphics have only 16 transformations, but some will produce 224 different combinations of positions and colors.