Some guidence on a problem.

[gmunk]

I'm trying to solve this problem -> http://www.hpcodewars.org/past/cw2/problems/PROB15.HTM.
Or should I say I'm completely unable to generate any ideas how to solve it, so I'd like to have some guidance on what to read or what kind of technique to use. I don't want a solution just some guidance. Thanks in advance!

[griswolf]

Well, you know that sum(each visited node) == node(3,3), so you can work the problem backward: There are two legal cells adjacent to (3,3): (3,2) and (2,3). The sum just prior to reaching those cells would have to be (3,3) - (that cell). And so forth backward. You can prune the search tree any time the current sum is less than the value at (0,0), or if there are no legal backward steps that don't touch a cell already seen.

To do all that, I'd keep a collection of viable partial solutions; and for each partial solution, I'd keep the current sum, the current node, and a set of the nodes that have been seen.

The legal 'next' nodes for cell (n,m) are among (n,m+1), (n,m-1), (n+1,m), (n-1,m) (and of course the index values must be between 0 and 3 inclusive.

You could do this iteratively, or recursively.

[0x69]

Or you could achieve practically same thing with backtracking algorithm-
http://en.wikipedia.org/wiki/Backtracking
Start from (0,0)
Choose next legal node (x,y)
If sum_until(x,y) > (3,3) -> advance backwards to previous cell, and choose next legal move.
Repeat while sum_until(x,y) != (3,3) AND (x,y) is not nearest cell from (3,3).

[griswolf]

And... for a computer science class, please calculate the complexity of this task (Of course you have to generalize he problem to an N X N array). Is it possible to do better than [TEX]O(N^2)[/TEX]?

[gmunk]

Thank you guys for your advice. I will try and produce a solution these days and post it here, though I don't promise anything because from what I read I have a lot of unfamiliar ground to cover up to solve this problem. 10x again!