#Trying to understand recursion and backtracking on brute-forcing Knight's Tour

1 messages · Page 1 of 1 (latest)

undone peakBOT
#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question run !howto ask.

humble stratus
#

a) you call a function called knightTour with (... , ..., 1) the next time you call it like this knightTour(... , ... , pos + 1) after the first call pos is 1, for the next call you say pos + 1 so that value is now 2 but only inside the next function call!

1 <-- first call
  2 <-- second call
    3 <-- third/last call, here the function fully ends without continueing to call it self. Thus it returns and we are back in the previous function that called this, this had 2 as the pos value.
  2 same as before here
1

does that help ? it actually goes back to 1 not 0

weary saffron
#

I think I understand

humble stratus
#

b) I think in theory yes it could be any value since you do not do any additions(and its overwritten by the other values) now this only works because every square is visitable if that wasnt the case you would have bullshit values but then i would also choose -1 as the intializer, but 0 here is just the default value, until we explore all paths each cell has the value of 0.

weary saffron
#

okay I see

humble stratus
#

c) i dont quite get what you want to change

#

can you paste the modified code?

weary saffron
#

so if you notice the addition of the print function

#

the difference with that and the original one is that the return; and the visited[x][y]=0. They're both gone, but it still works

#

I'm kind of confused on why

humble stratus
#

ah visited should actually be 0 because of !visited[newX][newY]

weary saffron
#

I mean I know it's a function so it only has a copy of the primary function's variables. But I am having more trouble just understanding the backtracking thing anyway

humble stratus
#

because that way it determines if a square has been visited cause 0 == false

weary saffron
#

OHHHHH

#

okay

#

I see that too

humble stratus
#

and the reason why it works with your change is that, this condition isValid(newX, newY) && !visited[newX][newY] will never be true, if pos >= N*N

#

you can test this by adding this

        if (pos >= N * N && (isValid(newX, newY) && !visited[newX][newY]))
        {
            std::cout << "SOMETHING BAD HAPPENED" << std::endl;
            exit(1);
        }

after

        int newX = x + row[k];
        int newY = y + col[k];
#

and you see its never printed/the program never exists

#

so one could say that return from above is an early return which optimizes the function a bit more because it will skip 8 unnecessary loops and not call is valid and not tested visited[newX][newY]

weary saffron
#

okay I think I see

#

also one last thing, the visited[x][y] part is the thing that initiates a backtrack to the first part of the code, is it correct to say that?

#

back to the top of the knightTour function

humble stratus
#

mhh, not quite sure what you mean by this

weary saffron
#

I think I'm asking more just how the backtracking happens

#

when it reaches that line of code

humble stratus
#

the backtracking part is more the recursive function call, without that it wouldnt backtrack at all

weary saffron
#

OH okay

#

I see I think

humble stratus
#

i mean if you remove that i t would be just one function call

weary saffron
#

right

#

anyway I think i'm about done, thanks a lot for your help I rly appreciate it

#

should I just close?

#

I forgot how to close this one lol

humble stratus
#

!close

undone peakBOT
weary saffron
#

!close

undone peakBOT
#

Thank you and let us know if you have any more questions!

This thread is now set to auto-hide after an hour of inactivity

humble stratus
#

no problem ; )