Since FET is a fast heuristic method for solving the timetabling problem, which is an NP-complete problem, the method might be applied to other NP-complete problems.
I just thought of a method to apply the FET algorithm to traveling salesman and it seems possible. Also, to graph coloring it applies directly (as a timetable is a graph coloring in n_hours_per_week colors if each activity has duration 1). I didn't think too much, but it seems that 3-SAT and clique problem can also be solved.
Note: by solving, I mean heuristically solving practical cases, like FET does. I do not claim to solve NP-complete problems polynomially.
The algorithm is simple: there are given n inputs: a1, a2, ..., an, and we try to put them into n slots. There are constraints, so that if the algorithm places ai into a slot, then a set of inputs aj, ak, ... will need to be displaced and placed into other slots. So, place ai into a slot and displace aj, ak, ... and place them recursively, like ai. We might need to impose a limit on the recursion level. Also, if recursion seems to work in vain for a time limit, place ai into a slot, displace aj, ak, ..., and start a new iteration with this state.
Also, a good initial sorting might be important.
I recommend you reading the Documentation section on FET homepage, then the doc/ directory of the FET package and then the src/engine/generate.cpp file of the FET package.
Maybe you are interested into spreading the word about this method.
I adapted the algorithm from FET and solved an instance of SAT which is categorized as UNKNOWN-SAT :-)
Attached the files with the solution.
I took the instance from http://www.satcompetition.org/ (SAT 2009 competition).
I'll think about sending a solver for this year's contest.
Sorry, it seems that UNKNOWN-SAT means something different - the problem was also solved by other solvers in the past, easily.
Hi Liviu, I find it's a good idea to partecipate in the contest! 8-)