Thread: Help with grid problem (dynamic programming)

In the classical knights tour of a chessboard, the dynamic Warndorff's algorithm can be used to greatly simplify the problem.

It relies on moving to the square which, on the *next* move, look most favorable. (which is, oddly, the move with the most constraints).

I'm wondering if something like that couldn't be used here. Something akin to:

Look at the current choices, in blocks to move along. For each of those possible moves, count up the number of possible moves you would have, if you were already there.

For each safe next move you find, which also leads either to the right, or upward, give it 5 points. For each safe move you find which leads left or down, give it 1 point (or whatever value seems to work best when testing).

On the basis of these values, choose the best one. This would be the "score" from a one or two ply depth first search, if I were to use it.

In the case of Warnsdorff's algorithm, it only works 100% correctly, if you settle tie scores, in this fashion (looking ahead one more ply).

It is an amazing simplification. Check it out on Wikipedia - "Knights tour". Don't worry about Depth first search, it's very simple. I have a little game that shows it off brilliantly, and you'll get it, straightaway.

adak - Wouldn't evaluating each move to 2 levels bring the algorithm to O(n^2)?

I think there's some insight into this problem that none of us are getting.

Originally Posted by scp89

adak - Wouldn't evaluating each move to 2 levels bring the algorithm to O(n^2)?

I think there's some insight into this problem that none of us are getting.

Only in rare cases do you need to go two ply deep, however.

In any case, you'll have to look at least one ply deep, for any dp type algorithm, to work.

Since you could have "traps" in the way the unsafe streets were laid out, you can't say that only one ply extra would be enough, either.

I'm quite sure you can't solve this problem without some look-ahead or backtracking. Any rule of thumb you employ without it, can be de-railed, miserably.

Think about it, couldn't you set up a bunch of unsafe streets in such a pattern that any algorithm lacking lookahead, would be utterly sunk?

Of course you could.