Another "Board Game"ish problem that you might consider is Pentominos. The challenge is to write a piece of software that can, for example, list all the solutions for the 6x10 board. When it comes to displaying the results either a simple printout, a graphical display or, better still, an actual physical set can be quite effective.

The solution exercises a variety of CS concepts and yet even a brute force approach can quickly yield a few usable results.