RiverIQGame.swf

Recently, my gf sent me a Flash game, embedded in an excel file. Too bad, I cannot run the Flash in OpenOffice. Why do people like to place Flash in excel files? Pasting a link in email is an easier mode of distribution. Anyway, I found the Flash at http://freeweb.siol.net/danej/riverIQGame.swf.

This is a typical math puzzle. It is the a of the Missionaries and Cannibals Problem. These are the rules (copied from Wikipedia):

  1. At most two persons on the raft at any time
  2. The father cannot stay with any of the daughters without their mother’s presence
  3. The mother cannot stay with any of the sons without their father’s presence
  4. The thief (striped shirt) cannot stay with any family member if the police officer is not there
  5. Only the father, the mother and the police officer know how to operate the raft

At first, I thought that this problem is much more complex, because of its large brunching factor. Actually it is not. It can be easily solved by hand using depth-first-search. During the “depth-first-search exercise” I found out that the contraints reduce the brunches to <= 2 at each level. Usually, I do not need to backtrack for more then 2 steps.

This is my “depth-first-search exercise”. I used ‘F’, ‘M’, ‘G’, ‘B’, ‘T’, ‘P’, ‘X’ to represent Father, Mother, Girl, Boy, Thief, Police, and boat respectively.

Posted in Blog at April 21st, 2009. No Comments.