An interesting article by J.R. Partington investigating puzzles of a mathematical nature to be found embedded within computer fantasy games may be found at Mathematical Puzzles in Fantasy Games. The following is an example of the whimsical delights to be found therein.

A Scheduling Problem from Sangraal When the Sangraal (Holy Grail) is almost won you arrive at the castle where the Foul Fiend has imprisoned 8 knights. These are as follows: Agravain - lightly bound - badly wounded Bors - lightly bound - scratched Caradoc - bound a bit more - badly wounded Dagonet - bound as C - scratched Ector - bound and gagged - somewhat wounded Feirefiz - in chains - badly wounded Gareth - in chains and gagged - somewhat wounded Harry - bound really tight in chains (poor chap) - scratched Here the state of binding means that it will take 1, 1, 2, 2, 3, 4, 5 and 6 minutes (respectively) to free them: a freed knight then goes away to wash and recover himself physically in time for the Sangraal's arrival. The time he takes for this second stage is 5, 10 or 15 minutes, according to injury. In twenty minutes' time the sun will set and the Sangraal will arrive. How many knights can you bring? We see, for example that if you want F, you must free him almost at once, as he can only be ready in 19 minutes at the earliest. Freeing Harry, though it takes 6 minutes, is not urgent, as he only needs to be freed by the 15th minute.

Had the objective been simply to minimize the total time to free and prepare all knights the puzzle would be mathematically equivalent to a standard job shop scheduling problem. However, the requirement that we need to maximize the number of knights to be freed and prepared within a given time renders the problem slightly more challenging. Specifically, we will need to add dummy variables to indicate whether or not a knight is freed and prepared within the time limit. Full details of an IP formulation follow.

Coefficients

f_i - time to free knight i
r_i - preparation time for knight i

Variables

x_i,j = 1 if knight i is in position j, 0 otherwise
t_j - finish time for knight in position j
d_j = 1 if knight in position j is freed and prepared within 20 minutes, 0 otherwise.

The objective of the puzzle is to maximize the number of knights that are freed and prepared within 20 minutes. This may be written down more formally as

Each knight may only occupy one position.

Mosel code to implement the model is here.

The following is an Excel spreadsheet layout that may be used to implement the above formulation.

here

Reference

Partington, J.R. (2002), Mathematical Puzzles in Fantasy Games, (last accessed on July 8, 2004).

	To download a printable version (pdf) of this paper, click here. To download the Adobe Acrobat reader for viewing and printing pdf files, click here.
	To reference this paper, please use:  Chlond M. J., (2004), "Fantasy OR," INFORMS Transactions on Education, Vol. 4, No 3,  http://ite.pubs.informs.org/Vol4No3/Chlond/