README.md

Python AI Stuff

This contains a maze solver and a (comparatively smaller) constraint satisfaction project, which involves allocating classes to classrooms based on class times and seats available.

A* Maze Solver

Using Pygame for visuals, this is a maze solver which always returns the optimal solution (if one is available), using the reliable A* search algorithm.

You can supply these as parameters to the program, or go with the defaults:

• Density: recommended 15 to 50, but not below 0 or 100. A higher number means there will be more obstacles, and consequently a higher chance that the maze won't be solvable. Defaults to 25
• Board Size: should be at least 10, but never below 0. The board generated by this program will be n by n tiles. Defaults to 50
• Diagonal movement allowed: If 'y' is inputted, then diagonal movements will be permitted with a cost of 1 (like horizontal/vertical movements). Any other input will ban diagonal movement, leaving only horizontal/vertical movements available. Defaults to NO

Technical Stuff

Chebyshev Distance Heuristic if diagonal movement is allowed. $$h = \max\left(|x_2 - x_1|, |y_2 - y_1|\right)$$

Manhattan Distance Heuristic if diagonal movement is not allowed. $$h = |x_2 - x_1| + |y_2 - y_1|$$

Constraint Satisfaction Classroom Allocator

This is a demonstration of the AC-3 algorithm, which is used for constraint satisfaction, a process in artificial intelligence. Given random courses and rooms available, the aim is to allocate every course section to a room, with no two classes using the same room at the same time..

See output.txt for a sample output file. This was not run with the course restriction, and took a few tries to get!

Here, we use it to allocate sections of courses to rooms based on numerous factors:

• Class size (random, but higher codes generally mean less seats)
• Timeslots
• Rooms available

Course sections are randomly generated with random times and sizes. Rooms are also randomly generated with random capacities.

If the algorithm completes:

• Each course's domain (which has all possible rooms) is reduced to just one room which holds as little seats as possible while fitting the course (i.e. for a course with 40 seats, we want a room with 40 seats over a room with 70)
• A file 'output.txt' is written to which lists what room each course is allocated to.

Technical Stuff

Out of the pool of courses available, only about half of these will generally be used in a run to avoid frequent runs that result in empty domains. You can remove this limit, but unsolvable world states may happen more often as a result.