CS105/CS360/SE360
Artificial Intelligence
Pentagons Formation using Tangram Pieces
Tangram is one of the most popular games to play with. You put figures of 7 pieces together (five
triangles, one square and one parallelogram). You must use all pieces. They must touch but not
overlap.

All seven tangram pieces consist of many half squares(triangles), each with this shape:

There are 32 half squares or 16 squares altogether.

We could take the half-squared triangle as the basic form, because each square built for all seven
tangram pieces has the simple length (perimeter) of 4 units.
There are many convex and non-convex figures/shapes of pentagons that you can build from all the
7 tangram pieces. Some of them are given below.






In this project, you are required to use AI search methods (uninformed search methods such as
Breadth First search, Depth First search, Iterative Deepening and Uniform Cost search) and
(Informed or heuristic search methods such as Greedy search, A* algorithm and Iterative Deepening
version of A* : IDA*) to perform pattern matching, recognition and pentagons formation. For some
figures with the same look, there are more than one ways to form it. Your jobs are given as follows:
1. Try to form all the possible distinct pentagons (convex and non-convex) from all these 7 pieces.
2. For some figures, find all the possible ways to form them, e.g., an above convex pentagon has 4
ways to form it.

3. Setup important problem formulation that is most suitable/useful for solving this problem.
4. Use at least TWO uninformed and at least TWO informed search methods to solve this problem.
5. Implement these search methods in a computer system so that all the 7 pieces could be used to
form all distinct convex and non-convex pentagons. Bonus will be given to team(s) who could
give/find all the possible ways to form same figures.
6. Analyze the properties of these search methods in terms of completeness, optimality, time
complexity and space complexity when solving this problem.
7. You are required to form teams yourself. Each team should have 3 or 4 students. You are advised
to include in your team at least ONE student who knows how to do programming, any
programming languages, Matlab, Python, R, C, C++ and/or Java etc. could be used.
8. Submit to me student names, ID and course, class of your team members in week 4 in the class
session. Students forming a team should come from the same course (e.g., CS360, SE360 or
CS105) and same class (e.g., D1 or D2).
9. A user friendly interface should be provided. A system name/title is given, e.g., ͞A Pattern
Matching, Recognition, and Pentagons Formation System .͟ The system should have options
such as pull-down menu of convex or non-convex figures, pull-down menu of different search
methods, etc. for user to choose from and execute. The results are displayed on the screen.
10. Each team is required to submit a report which includes the introduction, detailed description
of your problem formulation, number of goal states (Pentagons) you could reach, get or form,
problems you have solved, your contributions, what you have achieved in your system.
11. A clear, succinct, easy to understand user manual/guide on how to INSTALL and EXECUTE the
software (freeware or others) and your DEVELOPED system should be included in the report.
12. You are also required to submit a full and detailed report including the following information.
z All your team members͛ name, ID number and team number (assigned in the week 12),
Course (e.g., CS360, SE360 or CS105) and Class (e.g., D1 or D2).
z The problems you have solved.
z Which uninformed or informed search methods you have used, how and why?
z What evaluation function you have used to guide you in branching (expanding) nodes?
z How and why such functions or changes are introduced? What are the reasons behind
introducing such changes?
z Figures or diagrams showing the problem formulation of your system should be included.
z A comparison of properties of different adopted or implemented search methods in terms
of Completeness, Optimality, Time and Space complexity need to be done and included.
z The results you have obtained. Different figures showing results, many goal states, etc.
13. You are required to submit in the last/final class session (Presentation Session(s) held in week
14 and/or week 15) your Hardcopy report and a USB which contains the source codes of your
developed system, shareware and/or freeware used, user manual/guide on how to INSTALL and
EXECUTE your system, and your FULL report mentioned in points 10 -- 12.