Course:CPSC312-2017-Zed Solver
Kingdom of Zed Solver
Authors: David Zhang, Ruimou Xu
What is the problem?
We will be writing a solver for the Kingdom of Zed problem. Our implementation will focus on the 4x4 board case and will use some sort of backtracking algorithm to exhaustively search for valid game states.
What is the something extra?
Our something extra involves improving the usability of our program for the user. This will involve:
- Allowing the user to call our program on a text file with easily-laid out input instead of having to call functions manually.
- Formatting the result of our algorithm in an easy-to-interpret text representation instead of a raw list of lists
What did we learn from doing this?
Functional programming ended up being a bit cumbersome for our project. Backtracking search involves mutating state (our current guess) as the algorithm runs, so it's hard to implement in Haskell without making use of monads. Since one of the benefits of functional programming is not having to reason about state, using FP for this problem is counter-intuitive. That being said, we ended up coming up with a different method of exhaustively searching for the correct Zed map. We just generated a list of every possible map and then iterated through them until we found one that was valid. Haskell's laziness was a huge boon here as only the maps that were checked were generated, so we could get efficient run-times even though there are a huge total number of possible maps for higher n.