I need the algorithm with explanation in C to solve the well known 15 puzzle problem.If not possible to give the entire source code here please give me an idea how to device the solution to this problem.
branch and bound
I need the algorithm with explanation in C to solve the well known 15 puzzle problem.If not possible to give the entire source code here please give me an idea how to device the solution to this problem.
Wikipedia has a pretty good entry for many algorithms, along with the pseudo code for it (which is like C in many ways).Originally Posted by progmateur
I googled a site that had a 15 puzzle animation on it, and played it until I grokked a pattern I liked, and used that pattern for the program. As I recall, it's logic was to bring the tile up to the row below where it should go, and to the far right hand column. Tiles that didn't belong in the row just above it, were then removed, and the proper tile slid up, with the necessary adjustments. That worked fine for the first two rows. For the last two rows, I got quite explicit with it, which I shouldn't have*, but I wanted it to solve it VERY fast.
One big tip: You may know this already, but the puzzle has a "handedness" to it. About half the configurations for it, will have the wrong "hand", and can't be solved at all. For this reason, it's important to get only puzzle starting positions, that have the correct "hand" to them. Otherwise, you're up against a brick wall.
*With the explicit code for the last two rows, the whole program became very long and relatively "ugly", imo.
