8-Puzzle problem in search.ipynb throws errors

[ad71]

@MrDupin I reran the search notebook. EightPuzzle doesn't seem to work. I presume this is because of PR #733 . The PR had quite a few errors which didn't get caught by pytest because tests for EightPuzzle were never written. I plan to fix the errors. Any help would be appreciated.

[antmarakis]

Adding tests and rewriting the notebook is the way I would go first. If that doesn't work, I would look into the code itself.

[ad71]

The code basically doesn't work. It has many semantic errors. For loops try to iterate over integers instead of iterables and (obviously) throw errors. The class assumes that astar_search can handle two-dimensional states, which it doesn't. I rewrote the class and tested it only to be reminded that the existing astar_search and a few other algorithms do not work when states are lists (as these algorithms require typecasting the states to sets and lists are unhashable). There are quite a few problems going on and I'm afraid a large part of the code needs a refactor.

[ad71]

Oh, and referring to #711 , astar_search and a few other algorithms do not work with NQueensProblem either. As per @norvig 's suggestion in #727 , problems should produce states that are hashable. We either need a refactor to the code or revert to the previous implementation of EightPuzzle as a temporary solution. I understand now why EightPuzzle has always been an outlier in terms of its implementation and incompatibility with all the algorithms in search.py. There are plenty of underlying problems.

[norvig]

Yes, the eight puzzle code is wrong in that it returns a nonhashable state. It could use either a tuple of tuples, or just a tuple of 9 positions. The code to deal with directions/moves is also inelegant. Other code that deals with grids in other problems does this better. I don't remember the history, and how it got this way.

[ad71]

Thanks for the pointers. I'll work on this today.