Looking for puzzle/game programmes, so students can write solvers
There is a fairly well known game called, alternatively, Hare and Hounds or the French Military Game. It is a two person game in which one player controls one piece (the Crook/Spy) and the other controls three pieces (the Police). The object is for the Police to "trap" the Spy. The board is a directed graph with limitations on movement. 

There is a well known solution for automating the Spy so that it plays optimally, though naively at first, learning from subsequent plays. I believe there is a known "win" for the Spy if it plays correctly. 

A Java program for the automated version can be found at the Green Room. The implementation can use either arrays or Collections. 

The thing that makes it interesting as a program is that the game is simple enough that a complete play (all positions of all players) can be captured in a very compact way, making it feasible to retain the complete history of plays. 

The game and its solution are also discussed in detail in Beyond Karel J Robot by J Bergin.