Search code examples
algorithmcomputationhamming-distance

About Hamming and Manhattan priorities computation for 8 puzzle


http://coursera.cs.princeton.edu/algs4/assignments/8puzzle.html

Is this Hamming and Manhattan priorities computation from the above link correct?

For example, the Hamming and Manhattan priorities of the initial search node below are 5 and 10, respectively.

Note that we do not count the blank square when computing the Hamming or Manhattan priorities.


Solution

  • So, 3 of them are in the places and 5 not in the right places. This gives as 5 as Hamming distance, and some small manipulations needed to see that Manhattan priority is 10.

    enter image description here