Problem Description (Party Seating):

Seating guests in party tables is a headache sometimes. There are always guests who, for various reasons, shouldn't or must be seated on the same table.

If we treat the guest seating problem as a math/computer science problem instead a social problem, then we can give the following semi-formal definition of the problem:

• There are N tables, and each table can sit M guests;
• There are G guests and it goes without saying that G is less than or equal to N times M;
• To simplify things, there are C pairs of guests, the two guests in each pair must be seated on the same table;
• And there are A pairs of guests, the two guests in each pair must NOT be seated on the same table.

In the end, the party seating problem becomes to find a table assignment for each guest such that all the constraints (guest demands) are satisfied.

Your Tasks:

Treat the party seating problem as a constrait satisfaction problem and implement an AI agent program that can always provide a satisfactory seating arrangement or report failure if there doesn't exist a seating arrangement that satisfies all the guest demands.

You can design your own format for input information. Here is a sample input file that shows one possible encoding format to communicate a problem's data and constraints to your program.

Your AI agent program should use backtracking algorithm to solve the problem. And your AI agent must use at least two heuristics, minimum remaining values and most constraining variable least constraining value, coupled with the use of forward checking (value propagation) to improve the search efficiency.

Provide a Makefile to automate the compilation of your program.

Provide an assignment report (a .txt or .pdf file) that includes at least the following information:

• How to compile and execute your program? If your source code files need to be placed into subfolders in order to use the makefile, explain how the files should be organized.
• How do you encode the party seating problem as a Constraint Satisfaction Problem? That is, what is the formal problem definition of this particular party seating problem that conforms to the Constraint Satisfaction Problem representation standard.
• How should a user enter the information/data of a party seating problem instance to your program? That is, what is the encoding format of a party seating problem instance's data and constraints acceptable by your program?
• What output can be expected from your program if your AI agent finds a solution to the given problem or fails to find a solution?
• How does your program encode and maintain the problem states so that the required heuristics can be applied?
• Where and how, in your program, are the forward checking and the two required heuristics implemented respectively?
• Any known bugs;
• Any comment you would like the marker to know.

What and How to Submit

You need to submit the following files for this assignment:

• source code file(s) -- I assume that they are written in C/C++, with the extension name .cpp and .h. And .rs, .py and .java are added already. If you use any other programming language in implementing your program, let me know the extension name(s) of these files before you attempt submitting. And make sure that your program can be compiled and executed on otter. Thanks.
• makefile
• assignment report -- it should be either a text file (.txt) or a PDF file (.pdf).

Put all the files you want to submit in one folder on otter, submit them using the following command:
~liuh/bin/submit 485 A2 .

To check what file(s) you have submitted for this assignment, use the following command on otter:
~liuh/bin/checksubmit 485 A2

Alternatively, upload all the files you'd like to submit to VIU Learn, under the CSCI 485/Assessment/Assignment/A2 tab.