I do like it when I can have the students write an entire project from start to finish; they seem to like this as well. This project is one such. However, over a few iterations of this project, I've found a couple of early sticking points, which if the students get them wrong, completely munge up the entire remainder of the project. They're not even the main point of the project!
But, rather than just provide them with a starting code base, I prep the project with a homework containing three completely independent code-writing questions. This gives me a chance to check their work on the sticking points, and set them right, before they start on the main body of the project. If you have some sort of design checkpoint, or another regular feedback mechanism during the course of the project, the homework questions could easily be folded into the project proper.
This project just keeps on giving, too: by the time we're done, the students have noticed that the stack-based and queue-based solution processes have rather different behaviour, but haven't quite figured out why yet. Some speculate that one or the other is always better (depending on their test cases, usually); in any case, debriefing this project serves as a perfect introduction to the ideas of depth-first and breadth-first search. I also use it as a bit of a preview of things to come---here we used two of the agenda types, but what would happen if we used a priority queue instead? Well, that'd be a best-first search. See also my A-star version of this project.
Above is a screenshot from my reference solution, with a (queue-based) solution in progress. (Click it for a full-size version.) The green dot is the start, the target is the finish, and the grey squares are the ones that have been explored already.
This page is too easily googlable, so I don't want to post it here, but I'm happy to email the solution to any CS teacher. Just email me at firstname.lastname@example.org. Preferably, email from your school email account, and if possible include a link to some official school website that includes your name on faculty/staff (so I can verify that this is on the up-and-up).