@MASTERSTHESIS\{IMM2008-05625,
    author       = "C. Agerbeck and M. O. Hansen",
    title        = "A Multi-Agent Approach to Solving {NP-}Complete Problems",
    year         = "2008",
    school       = "Informatics and Mathematical Modelling, Technical University of Denmark, {DTU}",
    address      = "Richard Petersens Plads, Building 321, {DK-}2800 Kgs. Lyngby",
    type         = "",
    note         = "Supervised by Assoc. Prof. Thomas Bolander, {IMM,} {DTU}.",
    url          = "http://www2.compute.dtu.dk/pubdb/pubs/5625-full.html",
    abstract     = "This master's project concerns the use of multi-agent design principles in making efficient solvers for {NP-}complete problems. The design of computer programs as multi-agent systems presents a new and very promising software engineering paradigm, where systems are described as individual problem-solving agents pursuing high-level goals. Recently, researchers have started to apply the multi-agent paradigm to the construction of efficient solvers for {NP-}complete problems. This has resulted in very effective tools for routing problems, graph partitioning and {SAT-}solving.

The objective of the present project is to make further studies into the application of multi-agent principles to solving {NP-}complete problems. More specifically, the project has the following two goals. First, it should result in a general discussion of the use of multi-agent approaches to solving {NP-}complete problems. This should include a discussion of strengths and weaknesses compared to other approaches of solving the same problems. Second, it should result in a concrete software tool for solving n2 £ n2 Sudoku puzzles, which is known to be an {NP-}complete problem. The tool should be benchmarked against other solvers for Sudoku."
}