This is a personal project.
The tangram is a dissection puzzle consisting of seven flat shapes, which are put together to form shapes. The tangram has long been a popular puzzle game among children and teenagers. In this project, I managed to solve tangram problems automatically with the strategies of heuristic search. After users input any outline of a solvable problem, the algorithm is able to figure out the solution in 5 seconds.
Representation of Input Pictures
I used edge detection and noise reduction algorithms to abstract an input picture into one or several circular linked lists. The angle information and length of sides were then recorded.
During the heuristic search process, the algorithms explored by trying putting different pieces into the area surrounded by circular linked lists. The number of linked lists, used pieces and remaining area to be solved were all used as heuristic search.
The result is shown in the picture below.
The demo can be downloaded at: https://github.com/juhuagg/tangram