• Post Reply Bookmark Topic Watch Topic
  • New Topic

what can i add to this code - backtracking algorithm  RSS feed

 
Dan D'amico
Ranch Hand
Posts: 94
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
you start at arr [0][0] and end at arr[n-1][n-1]
the algorithm should return true if there's a path from start to end , that each move is one more from the previous, cant go through diagnals. only up down left or right .
the method should be static and recursive.
it sould work on any n*n array , this is only example - the bold numbers here are the path :

here's what i did until now , it return false instead of true.
i also added to the code the main method with the excact example the excersice gave.

 
Liutauras Vilda
Sheriff
Posts: 4928
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
To ask question correctly (at least ask), it requires to put some effort as well. And it is a critical part in order to get correct answer.

I strongly advise you to go through the section > HowToAskQuestionsOnJavaRanch
 
Dan D'amico
Ranch Hand
Posts: 94
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Liutauras Vilda wrote:To ask question correctly (at least ask), it requires to put some effort as well. And it is a critical part in order to get correct answer.

I strongly advise you to go through the section > HowToAskQuestionsOnJavaRanch


"While it's nice to SayThanks, the best way to show your gratitude for their effort is to be respectful. What does that mean? Take some time and try and find the answer yourself first"
the code i just past in this thread. i wrote it , thats my effort , it took me along time. now i'm stuck and ask for help.
 
Liutauras Vilda
Sheriff
Posts: 4928
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
1. There are no questions in your thread.
2. There are no stated any issues you are struggling with.

I'd suggest you do not mess around in your assignment exercises. You created one thread about recursion already, but you didn't solve it. Finished recursion problem first, then you'll get more clear understanding what you have to do over here.
 
Dan D'amico
Ranch Hand
Posts: 94
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Liutauras Vilda wrote:1. There are no questions in your thread.
2. There are no stated any issues you are struggling with.

I'd suggest you do not mess around in your assignment exercises. You created one thread about recursion already, but you didn't solve it. Finished recursion problem first, then you'll get more clear understanding what you have to do over here.


its not assignment exercises, i have final exam at 19/2 i'm solving old exams. i solve it only for me.
ok. but here its different , here i need to go back and try other paths.
 
Piet Souris
Master Rancher
Posts: 2044
75
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Dan,

you start with 'isPath(mat, 0, 0, 0, 0)'. (see line 20).
Now, look at line 26 (ish; the line numbers are getting
out of sync on my monitor here).
You test:

if mat(0,0) + 1 != mat(0,0) then return false.

I must say: I do not understand the structure of your code: two public classes?

Anyway: my advice is: if you test your code, then put a boolean 'forward' as
a parameter in your 'isPath'. And depending on whether you go deeper or are going back,
set that parameter accordingly. Then, print out, as one of the first things of the isPath
routine, what the value is of x, y and this forward.

Start with a 2x2 matrix, and follow what is happening.

Greetz,
Piet
 
Dan D'amico
Ranch Hand
Posts: 94
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:hi Dan,

you start with 'isPath(mat, 0, 0, 0, 0)'. (see line 20).
Now, look at line 26 (ish; the line numbers are getting
out of sync on my monitor here).
You test:

if mat(0,0) + 1 != mat(0,0) then return false.

I must say: I do not understand the structure of your code: two public classes?

Anyway: my advice is: if you test your code, then put a boolean 'forward' as
a parameter in your 'isPath'. And depending on whether you go deeper or are going back,
set that parameter accordingly. Then, print out, as one of the first things of the isPath
routine, what the value is of x, y and this forward.

Start with a 2x2 matrix, and follow what is happening.

Greetz,
Piet

about the two public classes. my mistake. not on purpose.
i changed the code :


my approche for solving this problem and when i get stuck.
1) base cases :
*if array is out of bounce
*if there are no neighbores indexes which has a value 1 more then the current index.
2)if col == [n-1] and row == [n-1] return true - goal achieved .
3) now its my problem. i increment to the next col or to the next row. but i dont understand how to go back to where i was. that the all idea. for example - go left go left go right ; dead end; go back all the steps you made.
i need help to understand the part of the backtraing.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!