Describe the gentle Pardoner's puzzle's ?
Answers
This is one of those problems that’s pretty easy to solve using recursion.
Setting off from the starting location, it’s possible to go North, East, South or West. Whichever way we go initially, we increment the count of the number of straight lines used (When we set-off, any direction is the start of a new line).
Then from each of these new locations, it’s possible to go North, East, South or West again but, we’re not allowed to revisit any town, so each time we are considering moving we need to check that:
The town has not yet been visited.
That it’s possible to move that way (not at an edge/corner, nor at the restricted link on the bottom).
That if we need to change direction we don’t exceed the 15 lines limit.
From every square we check the four possible cardinal moves according to the criterion above. If a move is possible we recurse in. Each move, we pass the state of the board (the towns already visited), the direction we travelled, and the running count of the number of lines to get to this stage (incrementing the number of lines drawn if the direction moved is not the same as the previous direction travelled).
We carry on recursing in until we have visited all the towns (success), or there are no more moves (fail: we painted ourselves into a corner or dead end), or if the move would take the line count over 15 lines (fail: we can stop immediately, as the line count will only get larger and there can be no solution downstream of this point).
I HOPE HELPFUL FOR YOU AND MARK AS THE BRAINLIST ANSWER FOLLOW ME