CS 124
Fall 2023

Eight Puzzle FAQ

Eight Puzzle FAQ

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

  1. What parts of the Eight Puzzle should we submit for Problem Set 17?

    You should submit parts I and II (board) from the Eight Puzzle. Be sure to submit your work for these parts of the assignment in the Problem Set 17 section of Gradescope.

  2. 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

  1. 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.

  2. 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

  1. 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.

  2. 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

  3. 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.

  4. 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.

  5. 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

  1. 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

  1. 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. We actually did this in lecture, so you could also consult the notes from before the break.

  2. 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

  1. 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 assignment, we recommend reading in the file one line at a time using a for loop.

  2. I’ve completed my process_file function, and I’m performing the initial tests that you recommend 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