Extra Credit Assignment 2
This extra credit assignment is worth 5 points (the same amount as a homework). You wont get any credit until you get the full credit (i.e., if you turn in a half completed project, you wont get any credit). You may submit it as many times as possible. This assignment must be completed by November 31st.
Your task is to write a program that solves the Kakuro puzzle game
(wikipedia). Your program should take in some sort of text file that contains the board, then outputs the result.
Try 3 different approaches to solving the game. Kakuro is NP-Complete (which means solving it is pretty much going to take exponential time). Approaches include Brute Force (DFS, BFS, DFS-ID), A*, Genetic Algorithms, Simulated Annealing, k-beam search and more. If you would like access to MAPLE's computational server (8 cores, loads of ram) to run your experiments, let Don know. Also, you may want to think about how to split your process into multiple threads or processes so that it takes advantage of multiple cores. If you would like some advice in how to overcome large problems like this one, talk to Don.
What to turn in:
- Your source code implementation of all 3 approaches, in the language of your choice. Your algorithms should print out all kinds of statistics, like how long it took, how many states it explored, etc.
- Several Kakuro boards (in your format) and their solutions.
- A user manual that describes how to compile, run and use your program.
- A writeup that describes how your project works, compares the 3 techniques in detail and covers anything else you would like to talk about.
Send these things to Don when your project is complete.