Lambda the Ultimate

This coming fall, I'm teaching our department's service course for non-majors. The topic is open, and in the past I've offered a version using Mark Guzdial's Python-based image processing course and another surveying algorithms and algorithm analysis (a la David Harel's Algorithmics).

For this fall, I'm thinking about offering a course introducing programming from the logic programming point of view. The students will, for the most part, have the mathematical maturity of Oregon high school graduates who are afraid of math, which is to say, essentially nothing. Almost none of them will have any background in either programming or logic, and I'll have the standard "fear factor" to overcome, as well.

At a minimum, then, I'll have to include a few weeks on propositional logic before diving in to actual programming. My inclination for programming is to use Prolog, probably the SWI compiler, for its fairly rich standard library. Beyond that, however, I'm pretty much at sea, and would really appreciate some suggestions. I've never taught a logic programming course before (other than as a component in a senior-level PL class), certainly not at such a low level, and this is not, in general, an area of expertise for me.

If you were to teach such a course (or if you have already), what would you consider an appropriate range and ordering of topics? Any ideas for cool applications? Sudoku solvers are a neat possibility: I'd love other ideas. Do you know of similar courses that have been successfully deployed?

Is this idea insane?