Creative Games sans Violence?

jolyon_jnr asks: "I'm looking for games to use in an unusual educational setting: a school within a Juvenile Detention Centre. I don't set policy, so the 'no violence' is a fixed criteria. I want to engage students' creativity and problem solving skills, without using 'boring educational software'. I've thought of Lemmings and The Incredible Machine. What other suggestions can you offer? Please bear in mind that most students have very low literacy levels, but will learn if motivated sufficiently."