CodeStepByStep

travel_concepts

Language/Type: Python recursion backtracking exhaustive search

Answer the following questions about the implementation of a `travel` function. (See the travel problem for a description of that function.)

Which of the following matches the first two levels of the decision tree that would have resulted if the backtracking solution had explored NE first instead of last in its recursive function?

```# A.
start (0, 0)
|
+--- N  (0, 1)
|    |
|    +--- N N   (0, 2)
|    +--- N E   (1, 1)
|    +--- N NE  (1, 2)
|
+--- E  (1, 0)
|    |
|    +--- E N   (1, 1)
|    +--- E E   (2, 0)
|    +--- E NE  (2, 1)
|
+--- NE (1, 1)
|    |
|    +--- NE N  (1, 2)
|    +--- NE E  (2, 1)
|    +--- NE NE (2, 2)
```
```# B.
start (0, 0)
|
+--- NE (1, 1)
|    |
|    +--- NE N  (1, 2)
|    +--- NE E  (2, 1)
|    +--- NE NE (2, 2)
|
+--- N  (0, 1)
|    |
|    +--- N N   (0, 2)
|    +--- N E   (1, 1)
|    +--- N NE  (1, 2)
|
+--- E  (1, 0)
|    |
|    +--- E N   (1, 1)
|    +--- E E   (2, 0)
|    +--- E NE  (2, 1)
```
```# C.
start (0, 0)
|
+--- NE (1, 1)
|    |
|    +--- NE NE (2, 2)
|    +--- NE N  (1, 2)
|    +--- NE E  (2, 1)
|
+--- N  (0, 1)
|    |
|    +--- N N   (0, 2)
|    +--- N E   (1, 1)
|    +--- N NE  (1, 2)
|
+--- E  (1, 0)
|    |
|    +--- E N   (1, 1)
|    +--- E E   (2, 0)
|    +--- E NE  (2, 1)
```

And in what order would matches be printed out on the console if NE were explored first?

```# A.
moves: N N E
moves: N E N
moves: N NE
moves: E N N
moves: NE N
```
```# B.
moves: NE N
moves: N NE
moves: N N E
moves: N E N
moves: E N N
```
```# C.
moves: E N N
moves: N E N
moves: N N E
moves: N NE
moves: NE N
```

How many entries are at level 3 of the full decision tree?

 correct decision tree A B C correct order of printing matches A B C entries at level 3 of decision tree 9 18 27 64 256