The A* algorithm can be used to shortest path distances in a geometric framework. But the A* algorithm is not limited to this. SLIDING NUMBER PUZZLE 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ^^^^^^^^^^^^ Final Solution So starting the squares in "any" position. "Any" is in quotes because not all positions are solveable. If you put the squares in a random position, then you can either the puzzle, or solve the puzzles except for the bottom row being 13-15-14. So half of all potential starting positions actually lead to a solution. So, the idea is not to solve the puzzle, but to solve the puzzle in the smallest possible number of moves. And a move is moving one square into the blank. So, you can treat this like a distance problem. You imagine the "adjacent cities" to a particular position are the ones one move away from it. So, the distances between "adjacent cities" are always 1. The tiles themselves aren't the cities. The "state of the puzzle" is a city. There 16!/2 states of the puzzle, so that's how many cities there are. And adjacent cities are one apart. When you find the shortest path from the start city to the destination, you now have the smallest number of moves needed to solve the puzzle. The uniform-cost algorithm (Dijkstra's) turns into breadth-first-search when the distance between adjacent states is always 1. This turns out to be very impractical for breadth-first-search. So, we can try A* on this. The broad idea being that we're going to focus on moves likely to move us toward a solution rather than crudely trying all possible combinations. And so we need a heuristic. The heuristic should estimate the number of moves to the solution from where we are...but it cannot be an overestimate under any circumstances. The heuristic has to give us a number. We add the estimated distance to the solution to the number of moves that got us where we are now. That's what we add to the priority queue. Heuristic 1: Count the tiles that are not in the correct spot. (Screen example: 14). Never an overestimate. If a tile is in the wrong spot, it takes at least one move to put the right spot, and any move can only improve one tile. Heuristic 2: Count the number of moves to move each tile directly into position. (Manhattan distance. Adding the horizontal and vertical distance.) Find the sum of distances each tile is from its correct position. This is also never an overestimate. Heuristic 3: Compute (using BFS) how many moves it would make to PARTIALLY solve the puzzle. For example, what is the minimum number of moves to get the one tile into position. You can get an exact answer for this with a cruder algorithm, and this heuristic can then be used to find the Truly Best Move. This is called "relaxing the problem". A heuristic is chosen based on an "easier" version of the problem. Heuristic 3 is a "relaxation" because its based on the easier problem of only moving the lowest incorrect tile into place. Interestingly, Heuristics 1 and 2 are ALSO "relaxations;" they are ALSO based on earlier versions of the problem. Heuristic 2: What we're doing here is finding the solution of a version of the game where tiles are allowed to coexist in the same square. Heuristic 1: What we're doing here is finding the solution of a version of the game where you can put tiles on top of each other AND can move tiles to any square, not just an adjacent one. RUBIK'S CUBE: Using BFS to solve Rubik's Cube. Ha ha ha ha ha. Heuristic 1: Solving one side. "Relaxation" Heuristic 2: Number of cubes that are out of position (bad heuristic, why?) (Potential overestimate: might move as many 8 cubes out of place). Instead, Number of cubes that are out of position ... divided by 8. Heuristic 3: Number of stickers that are out of place ... divided by 20. Heuristic 4: Number of cubes that are out of position + number of cubes in position that are not oriented correctly ... divided by 8 Heuristics 2 3 4 turn out not to give you adequate information to make a difference. Heuristic 1 cannot be easily computed using BFS.