8 Puzzle Problem using Manhattan Distance in Artificial Intelligence

The 8-puzzle problem is a puzzle invented and popularized by Noyes Palmer Chapman in the 1870s. It is played on a 3-by-3 grid with 8 square blocks labeled 1 through 8 and a blank square. Your goal is to rearrange the blocks so that they are in order. You are permitted to slide blocks horizontally or vertically into the blank square. We can use any one of the following Heuristic Functions: Hamming priority function: The number of blocks in the wrong position, plus the number of moves made so far to get to the state. Intuitively, a state with a small number of blocks in the wrong position is close to the goal state, and we prefer a state that has been reached using a small number of moves. Manhattan priority function: The sum of the distances (sum of the vertical and horizontal distance) from the blocks to their goal positions, plus the number of moves made so far to get to the state. A critical optimization: To prevent unnecessary exploration of states, when considering the neighbors of a state, don't explore the neighbor if its board position is the same as the previous state.🔗Important Playlists:
Artificial Intelligence: www.youtube.co... Learning: • Machine Learning
🌐Join our community:
Android App(Notes+Videos): play.google.co... Facebook: / thinkxacademy Twitter: / thinkxacademy Instagram: www.instagram.... #artificialintelligence #heuristics

[@josef-jayabiada221]

can i ask? what would i choose if i have the same M Values?

[@ThinkXAcademy]

If you get the same manhattan distance which is highest among all the paths, calculate the manhattan distance for the next state of the paths with same manhattan distance and then choose the minimum. Another way is to merge the paths of same manhattan value into one and proceed with the algo.

[@josef-jayabiada221]

@@ThinkXAcademy Thank You!

[@martinwilliams1308]

This really helped me when I was working on an assignment. Thanks!!

[@ThinkXAcademy]

That's great! Share our content with others to help this channel grow💯

[@piotres5373]

You save my day! THX bro

[@ThinkXAcademy]

Keep Learning 🌟

[@shehabalmughalles8017]

Thank you.

[@ThinkXAcademy]

Keep Learning 💯

[@caljohn1475]

brilliant explanation

[@ThinkXAcademy]

Thank you😄 Keep Learning ✔️

[@AnkitKumar-zy9pb]

What happen when all possible node value is equal the where to go?

[@nitsanbh]

slowest pace to the point I have ever seen in a video. consider using a heuristic to get to the goal point faster

[@alirezadoroudi9126]

Thank you so much

[@Bosco-sb5dc]

well explained !, thank you!

[@ThinkXAcademy]

Share with other students also💫

[@aleksandarpetrovic2632]

Awesome tutorial, thank you!

[@ThinkXAcademy]

Welcome sir😄

[@EasyCodingStudio]

nice explanation

[@sireeshagandavaram8469]

Nice explanation sir tq sir 👍 😊

[@Evan_411]

thanks a lot bro

[@marouenkadri8771]

Sear how we implement this algo , what can of data structure used ?

[@ThinkXAcademy]

Priority Queues

[@ChandaniGajera]

What should I do if I get same Manhattan value for next 2 steps... And not possible any other movement

[@johnmackenzie3871]

Good video, thank you.

[@ThinkXAcademy]

Thanks😃

[@andarithaneshafitri7306]

Thanks

[@ThinkXAcademy]

Keep Learning ✨

[@VedOfficial]

Made my task easy❤🎉

[@suhaibgbrtee4031]

thank u soo much but there is notice u have said that the first box has only 3 new possibility and the forth one will return us to the same original box so it should be eliminated but u forgot to do it for the remaining boxes , with the same implemented method there should be only one new possibility for each of the 2 remaining boxes

[@ThinkXAcademy]

yes we can avoid repititive boxes

[@satvikarya569]

ThankYou very much 👌👌

[@ThinkXAcademy]

Please share our videos to help this channel grow🌟

[@amirbaba9677]

thanks alot

[@ThinkXAcademy]

keep Learning 💯👍🏻

[@hit1599]

I used the same methods but just using the manhattan distance causes the program to go into infinite loops for certain cases. Will like to hear the solution for this.

[@ThinkXAcademy]

you will have to learn on how to write conditions that stops the loop and return the result

[@prajjwaltripathi2911]

Helpful

[@ThinkXAcademy]

Thanks😄

[@rodrigol.1869]

I have a doubt regarding the code implementation of this. What should I do when all the possible branches were already visited but the solution hasn't been found yet? Should I try a different heuristic?

[@ThinkXAcademy]

No, try a different source to start the algo.

[@FreeMayaTutorials]

Could you generalize this technique to play any game optimally that would lend itself well to various states where an m distance calculating function could be used?

[@ThinkXAcademy]

I will create a separate video for that soon✔️👍🏻

[@FreeMayaTutorials]

@@ThinkXAcademy That would be great, thank you very much!

[@guilhermedias6018]

thanks

[@ThinkXAcademy]

Share and Subscribe🌟

[@hananal6493]

Hello doctor, can I communicate with you?

[@ThinkXAcademy]

yes doctor

[@hdvlogs4485]

there is so much lag in is there in you tutorial try to avoid it

[@ThinkXAcademy]

I am sorry i didn't have a good smartphone back then so there was lag, i have upgraded now and content is also improving👍🏻

[@dimitrisz840]

Hey nice explanation there! Quick q, why is this heuristic preffered to the missing tiles one?

[@ThinkXAcademy]

manhattan distance

[@ratneshjha3229]

Suggestion - Go a bit faster, it's great but I had to watch it at 1.5x speed

[@AnkitKumar-zy9pb]

you are taking non solvable example bro

[@AnkitKumar-zy9pb]

This example can not have solution

[@TheClockmister]

Can you say "Pubg mobile" for me?

[@ThinkXAcademy]

Pubg Mobile