Write a program that solves the $8-$puzzle. Compare four different heuristics:

Manhattan distance, misplaced tiles, n $-$MaxSwap, and row$/$column misplacement.

The n$-$MaxSwap solves the relaxed game where any tile can be swapped with the

space. The row$/$column misplacement counts the number of tiles not in the

correct row plus the number of tiles not in the correct column. Compare the

performance of each heuristic. See the aima$-$python$/$search$.$ py$,$ aima$-$

python$/$search$.$ipynb, and aima$-$python$/$gui$/$eight$\_$puzzle.py for

help. The eight$\_$puzzle.py$,$ needs some corrections to work correctly.

add import sys

move

sys$.$ path.append$($os$.$ path.join$($os$.$path.dirname$(),$

$\text{'}..\text{'}))$ before from search import EightPuzzle,

astar$\_$search