Reindeer Ordering

The Decision Management Community posted a fun challenge: Santa’s elves are supposed to order nine reindeer according to a set of rules. The rules are:

  1. Comet behind Rudolph, Prancer, and Cupid.
  2. Blitzen behind Cupid.
  3. Blitzen in front of Donder, Vixen, and Dancer.
  4. Cupid in front of Comet, Blitzen, and Vixen.
  5. Donder behind Vixen, Dasher, and Prancer.
  6. Rudolph behind Prancer.
  7. Rudolph in front of Donder, Dancer, and Dasher.
  8. Vixen in front of Dancer and Comet.
  9. Dancer behind Donder, Rudolph, and Blitzen.
  10. Prancer in front of Cupid, Donder, and Blitzen.
  11. Dasher behind Prancer.
  12. Dasher in front of Vixen, Dancer, and Blitzen.
  13. Donder behind Comet and Cupid.
  14. Cupid in front of Rudolph and Dancer.
  15. Vixen behind Rudolph, Prancer, and Dasher.

The challenge is to create a decision model, but this looks like a simple exercise in constraint programming. As presented in Send More Money and Eight Queens posts, SQL is a good fit for these.

Reasoning

There are nine reindeer, each of which can be in a position (1..9); hence the number of all possible permutations is 

9*8*7*6*5*4*3*2*1 = 9! = 362880

A quick memory requirement estimate — 362880 rows of nine integers each — for this data set would be 

362880 * (9*4 + 24) = ~ 22 MB

This should easily fit into memory of an average laptop.

The process is simple:

  1. Generate all possible permutations of reindeer ordering;
  2. Apply the rules to the set of all possible orderings;
  3. Keep all results that satisfy the rules.

Solution

Take a look at the code, a simple query — tested on PostgreSQL and MS SQL Server — is easy to follow; runs within 2 seconds.

There is only one solution that satisfies all the rules:

  1. Prancer
  2. Cupid
  3. Rudolph
  4. Dasher
  5. Blitzen
  6. Vixen
  7. Comet
  8. Donder
  9. Dancer