Final Project FAQ

General questions
Part I
Part II
Part III
Part IV
Part V

If you don’t see your question here, post it on Piazza or come to office hours! See the links in the navigation bar for both of those options.

General questions

What parts of the project should we submit for Problem Set 10?

You should submit parts I and II from the final project. Be sure to submit your work for these parts of the project in the Problem Set 10 section of Apollo.
Are comments needed for each method/function?

As always, please include docstrings. You should also include comments for portions of your code if they might be hard to understand without the comments.

Part I

In the Board class, does the tiles attribute have to be a 2-D list of integers, or can it contain strings?

It must be a 2-D list of integers, with 0 representing the blank cell. For example, let’s say that you construct a Board object as follows:
```
>>> b = Board('012345678')
```
If you then evaluate its tiles attribute, here is what you should see:
```
>>> b.tiles
[[0, 1, 2], [3, 4, 5], [6, 7, 8]]
```
You should not see the following:
```
>>> b.tiles
[['0', '1', '2'], ['3', '4', '5'], ['6', '7', '8']]
```
If you do, you should fix your code.
What should our move_blank method do if a direction other than 'left', 'right', 'up', or 'down' is passed in for the input?

It should print an error message (see the example cases for the format of the message) and return False, without making any changes to the object. Make sure that you don’t try to return the error message. It should be printed, and then you should return False.

Part II

In the __init__ method for the State class, how can we determine the number of moves of the predecessor?

Keep in mind that the predecessor is also a State object. Therefore, you can access its num_moves attribute using dot notation.

For example, if p is the predecessor, you would do p.num_moves. You should replace p with the appropriate expression for the predecessor.
In the is_goal method, how can I access the tiles in the Board object associated with the State object?

Inside any State method, self.board will give us access to the Board object associated with the State object. And because tiles is an attribute of the Board object, you can use the following expression to access the tiles: self.board.tiles
In the generate_successors method, what should we use as the input for the predecessor when we construct the new State object?

As the hints provided for this method suggest, you should use the variable self for the predecessor, since the current state (the one represented by the called object self ) is itself the predecessor of the new state.
In the generate_successors method, when I try to add a successor to the list of successors, I get an error that says State object is not iterable. What am I doing wrong?

When you use the + or += operator to add a State object to the list of successors, you need to perform list concatenation – adding one list to another list. As a result, you need to make sure that you put square brackets [] around the State object.
My generate_successors method doesn’t produce the expected results. What am I doing wrong?

One thing worth checking: Make sure that you aren’t mistakenly calling move_blank() twice for a given move.

Each call to move_blank() does up to two things: if the move is possible, it modifies the contents of the Board object, and it also returns either True or False to indicate whether the move was possible. As a result, you should only call it once per move. However, many people have been mistakenly calling it twice per move: once to check if the move is possible, and once to make the move.

For example, this is not correct:
```
# don't do this!
if b.move_blank(direction) == True:
    b.move_blank(direction)     # no! this moves the blank again!
    s = State(b, ...)
    ...
```
Rather, you should do this instead:
```
# do this instead!
if b.move_blank(direction) == True:
    s = State(b, ...)
    ...
```

Part III

My should_add method doesn’t seem to work correctly for the case in which the input state would create a cycle. I don’t see any errors in my should_add. Is it possible that the provided creates_cycle method has a bug?

No! However, it is possible that the problem actually goes back to one of your Board methods. The creates_cycle method compares two Board objects to check for a cycle, so if one of your Board methods is making an improper change to a Board object, then it’s possible that two Board objects that should be considered equal are actually considered unequal.

Here’s one piece of test code that could help you to diagnose the problem:
```
>>> b = Board('012345678')
>>> b.tiles
[[0, 1, 2], [3, 4, 5], [6, 7, 8]]
>>> b.move_blank('right')
True
>>> b.tiles
[[1, 0, 2], [3, 4, 5], [6, 7, 8]]
```
Make sure that the 2-D lists that you get for b.tiles match the ones that you see above. In particular, make sure that all of the elements of the lists are integers, not strings. If your results for b.tiles are not correct, check your __init__ and move_blank methods.

Other possible sources of the problem are: (1) the __eq__, copy, and digit_string methods in the Board class, and (2) the __init__ and generate_successors methods in the State class, which might be failing to set up an appropriate connection between a State object and its predecessor. Here is some additional test code that may help you to diagnose the problem:
```
>>> b = Board('012345678')
>>> b.tiles
[[0, 1, 2], [3, 4, 5], [6, 7, 8]]
>>> b.digit_string()
'012345678'
>>> b.tiles
[[0, 1, 2], [3, 4, 5], [6, 7, 8]]
>>> b2 = b.copy()
>>> b2.tiles
[[0, 1, 2], [3, 4, 5], [6, 7, 8]]
>>> b.tiles
[[0, 1, 2], [3, 4, 5], [6, 7, 8]]
>>> s = State(b, None, 'init')
>>> s.predecessor == None
True
>>> succ = s.generate_successors()
>>> succ
[312045678-down-1, 102345678-right-1]
>>> succ[0].predecessor
012345678-init-0
>>> succ[1].predecessor
012345678-init-0
```

Part IV

How can we determine which state has been in the list the longest?

Try tracing through some examples on paper of adding states–one at a time–to the list, and think about which of them should be removed if you want the one that has been in the list the longest.
Our DFSearcher works for all the tests cases except the one that imposes a depth limit (the third test case). How can I figure out what is going wrong?

Here are a few things to check:
1. Is your DFSearcher‘s depth limit being set properly? Try this from the Shell:
```
>>> d = DFSearcher(25)
>>> d.depth_limit
25
```
  If you don’t see 25, then you should take a look at how you are constructing a DFSearcher. If your class is simply using the constructor inherited from Searcher, then check to ensure that the Searcher constructor is properly initializing the depth_limit attribute.
2. Is the should_add() method that you defined in the Searcher class—and that your DFSearcher should simply inherit – dealing appropriately with states that are beyond the depth limit? Here’s some test code:
```
>>> d = DFSearcher(25)
>>> s = State(Board('012345678'), None, 'init')
>>> s.num_moves = 26    # artificially change the number of moves
>>> d.should_add(s)
False
```
  If you don’t see False, then fix your should_add() method in Searcher and/or make sure that DFSearcher is simply using the inherited version of should_add() and not defining its own version.
3. Is should_add() being properly called in the context of a DFSearcher‘s execution of find_solution()? In Part III, we indicated that add_states() in Searcher should use should_add() to decide whether to add a state. Is your add_states() doing that? Is your DFSearcher simply using the inherited add_states() as it should?
When I try to use the eight_puzzle driver function to test my Greedy and A* searchers, I receive an error that says TypeError: 'int' object is not callable. How can I fix this?

When you use eight_puzzle() to test Greedy or A*, you need to make sure to pass in the heuristic function as the third input, rather than a depth limit. For example:
```
>>> eight_puzzle('142358607', 'A*', h1)
```
We recently updated the assignment to emphasize this fact.
My GreedySearcher class passes the tests that are given in task 4 of Part IV, but when I try to use Greedy Search in the context of the eight_puzzle driver function in task 6, I’m getting an error that says that a ‘State’ object does not support indexing. What I am doing wrong?

The problem may actually be in your Searcher class, since GreedySearcher inherits from Searcher. In particular, make sure that the add_states method in Searcher calls the add_state method to add each new state to self.states. It should not add the individual states on its own (e.g., by performing list concatenation).

The reason that this matters is that GreedySearcher overrides the version of add_state() that it inherits from Searcher, but it doesn’t override the inherited version of add_states. As a result, if add_states() doesn’t call add_state() as it should, the GreedySearcher version of add_state() won’t get called, and thus the list of states won’t include the priorities as required.

Part V

How do I read from a file?

In lecture, we presented two different ways to read the contents of a file. You can consult the lecture notes from a couple weeks ago or check out the example code online. For the project, we recommend reading in the file one line at a time using a for loop.
I’ve completed my process_file function, and I’m performing the initial tests that you recommend using the 10_moves.txt file. Although my earlier tests of BFS all went fine, I’m getting non-optimal solutions when I perform BFS using process_file. Do you have any suggestions for how to find the problem?

Yes! Make sure that you create a new searcher object for each puzzle (i.e., for each line of the file). Otherwise, the searcher will still have information inside it from previous searches when it starts to solve a new puzzle.
When I test the process_file function using the 10_moves.txt file. I’m able to reproduce the results for BFS, but I don’t get the same results for Greedy. Is that a problem?

Probably. When you first implemented the GreedySearcher class in Part IV, task 4, if you got the same results as we did for the examples that we provided, then you should get more or less the same results here as well. The only possible exception is the number of searches that you choose to terminate.

If your results don’t match ours, one thing to double check is your num_misplaced method in the Board class. Here are some additional test cases for that method that should help you to ensure that it’s working correctly in all cases:
```
>>> b = Board('012345678')
>>> b.num_misplaced()
0
>>> b.move_blank('right')
True
>>> b.num_misplaced()
1    
>>> b.move_blank('down')
True
>>> b.num_misplaced()
2    
>>> b.move_blank('left')
True
>>> b.num_misplaced()
3    
>>> b.move_blank('up')
True
>>> b.num_misplaced()
3
```
My h2 heuristic function still doesn’t allow A* to solve the 24-move or 27-move puzzles in a reasonable amount of time. Is that okay?

Probably. To ensure that your h2 heuristic is good enough, try comparing it to h1 in the context of puzzles that require fewer moves. For example:
```
>>> process_file('15_moves.txt', 'A*', h1)
>>> process_file('15_moves.txt', 'A*', h2)
```
When you look at the results of these two calls, you should see that:
- using h2 allows A* to test fewer states than it does when it uses h1
- the h2 solutions are still optimal (i.e., they require the specified number of moves).
If both of these things are true, then your h2 is good enough!