Travelling salesman is an NP-complete problem. Problems in NP have a
fast (polynomial time) way of checking that a claimed solution achieves
a claimed cost. If any of the NP-complete subset has a polynomial time
solution, so do all problems in NP. Unfortunately, nobody knows whether
any of them do. If you find out the answer, don't bother with topcoder.
Collect the $1,000,000 prize from the Clay Institute instead.

Of course, some variations may be easier than the general problem.

I haven't thought this through, but at first sight it looks to me like a
case for "dynamic programming". I believe that gives a solution in
O(n*n*m*a) where the board is nXn, m is the number of moves, and a is
the number of single moves. "Dynamic programming" is one of several
strategies to consider when looking for an algorithm for an unfamiliar
problem.

It depends on how much you want to improve your algorithm skills. If you
want to learn the strategies, you need a textbook or a really good web
tutorial.

Patricia

Why not jump in?

Think heavy recursion.

Travelling saleschap untried pseudo-code:

void findPath(Node node) {
    List nodes = node.getConnectedNodes();
    for (Iterator i = nodes.iterator(); i.hasNext();) {
        Node nextNode = (Node)i.next();
        nextNode.setPreviousNode(node);
        if (nextNode.getName().equals("New York")) {
            recordPath(nextNode);
        } else {
            findPath(nextNode);
        }
    }
}

void recordPath(Node node) {
    System.out.println("From New York to beginning was via ...");
    Node previousNode = node.getPreviousNode();
    while (previousNode != null) {
        System.out.println(previousNode);
        previousNode = previousNode.getPreviousNode();
    }
}

Of course, you probably won't get further than three cities from the
start before your stack clutches its chest and keels over.

For the chess problem I'm sure there's a way to map all the next
possible moves of each piece to the getConnectedNodes() method.
Actually, that may well be the most interesting part: essentially
mapping your problem-space to a graph. (Feels like a mathematical
transform.)

Note: also jolly useful for finding circular dependencies in code.

[I have read the rest of this thread, but here seems to be as good a place to
reply as any]

I don't think that they will typically be the same problem.  It is true that
there are large classes of problems where the only known solution is one form
or another of brute force (a recursive or iterative exploration of the entire
problem space -- possibly with a bit of early pruning).

But when it comes to problems on TopCoder and the like -- i.e. essentially
/puzzles/ -- you can normally expect that there's a better solution to be
found.  Otherwise it'd be boring !

So you have to look for short-cuts, or other kinds of cleverness, and that's
where the fun comes in (or frustration, depending on your success).  Some
general techniques:
+   Try to formulate the problem in as many different ways as possible.
+   Consider approximations to the problem.
+   Can you find a solution to part of the problem ?
+   Have you seen something a bit similar before (NB: this
     one is particularly dangerous since it can lead you
    right royally up the garden path)
+   Try to produce a /proof/ that the problem isn't soluble.
    Where does the attempt fail ?  That's probably the key
     insight.
+   Try a brute force solution of a few special cases.  Are
     there any patterns that give you a hint ?
+   Post it to Usenet ;-)

There's a lot of satisfaction to be had in solving such puzzles, but they are
not (normally) particularly related to the kinds of algorithm problems that
occur in real programming and design.  Working on them is probably good
practise for real algorithm design (especially the for first of the above
techniques), but it's no substitute for having a basic grounding in the
algorithmic techniques that are already available (I don't mean having an
expert knowledge of all the millions of published algorithms -- just the
basics, so you can navigate the field with confidence).

Bottom line: if your aim is to get more fun from TopCoder then you have to
practice.  If your aim is to be a more knowledgable designer, then buy some
books (/and/ read them ;-)

   -- chris