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!

3
Contributors
4
Replies
5
Views
8 Years
Discussion Span
Last Post by gmunk

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.

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).

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]?

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!

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.