• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

what can i add to this code - backtracking algorithm

 
Ranch Hand
Posts: 94
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.

 
Marshal
Posts: 8857
637
Mac OS X VI Editor BSD Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Marshal
Posts: 8857
637
Mac OS X VI Editor BSD Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Bartender
Posts: 5465
212
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
reply
    Bookmark Topic Watch Topic
  • New Topic