Saturday, 4 October 2014
15 Puzzle Problem - Check if solvable or not ?
Hi I am Sunish from Team MAST.
In this post I will tell you how to check if the given 15 puzzle problem can be solved or not. So here we go. As you can see in the given 15 puzzle problem the empty box is in second row’s 1st column.
The very first step is that , slide the given numbers in such a way that the very last box of the the given table is made empty. So according to the given problem shift the second row’s numbers to the left and we can see now the 2nd row’s last box is empty.
Now further move 4th column elements upwards to cover that empty space and finally we get last box empty.
Third step is to find the corresponding values of the above written numbers. Now how to find these corresponding values ?
Let’s start with number 2
Check all those numbers which are smaller than 2 and are placed to the right of 2 so count comes out to be one because 1 is the only number which is smaller than 2 and placed to the right of 2.
Similarly for next no 7
Check all those numbers which are smaller than 7 and are placed to the right of 7. So count comes out to be five as 5, 4, 6, 3 & 1 are the numbers.
Similarly mark for all other numbers and the given count for every no comes out to be as shown.
Now the final step is to sum all these numbers and the sum comes out to be 47 which is odd so we conclude that this 15 puzzle problem in not solvable.
Mark my words, if the sum had come out to be as even the 15 puzzle problem would have been solvable.
And that’s it. You are done.
You can also see the video for better understanding.
---------------------------------------------------------You can find us on Facebook - http://facebook.com/MavenScientists