Course:CPSC312-2017-Kingdom-of-Zed-seerat-david-jordan

Kingdom of Zed

Authors: Seerat Sekhon, Jordan Schalm, David Julien

What is the problem?

We will implement the Kingdom of Zed puzzle as defined here: http://www.cs.sfu.ca/CourseCentral/383/pjj/a1.html

What is the something extra?

Our "something extra" will be to add the following "Additional Features" as described in the assignment description.

• Ability to solve arbitrary-size inputs
• Display of the kingdom as a grid rather than a list
• Solve maze using a more intelligent solving strategy rather than just brute force: depth-first-search with constraint propagation

What did we learn from doing this?

Code is hosted here.

We have determined that functional programming and Haskell are good candidates for implementing a Kingdom of Zed solver. While programming in Haskell, we learned that Haskell makes it easy to intuitively write functions that handle only one thing. This results in code that is succinct and readable.

We also learned that defining data and types specific to a project is very useful. For example, defining a Kingdom as a structure containing a map from Positions to Counties is much more descriptive and readable compared to a Kingdom with a map from (Int, Int) to an Int.

We also implemented a brute force solver (with a hardcoded size) and when compared with the DFS solver, the brute force solution was much slower, averaging around 10 seconds. Although probably obvious, this shows us that generating permutations of possible solutions is very costly.