The 24-puzzle is an extension of the 8-puzzle, where there are 24 pieces, labeled with the numbers from 1 to 24, placed on a 5x5 grid. At each move, a tile can move up, down, left, or right, but only if the destination location is currently empty. For example, in the start state shown above, there are three legal moves: the 12 can move down, the 22 can move left, or the 19 can move right. The goal is to achieve the goal state shown above. The cost of a solution is the number of moves it takes to achieve that solution.

For some initial states, the shortest solution is longer than 100 moves. For all initial states, the shortest solution is at most 208 moves.

An additional constraint is that, in any implementation, storing a search node takes 1000 bytes, i.e., 1KB of memory.

Consider breadth-first search, depth-first search, iterative deepening search, uniform cost search, A*, and IDA*.

(a): Which (if any), among those methods, can guarantee that you will never need more than 50KB of memory to store search nodes? Briefly justify your answer.

(b): Which (if any), among those methods, can guarantee that you will never need more than 1200KB of memory to store search nodes? Briefly justify your answer.

15 16 1724 18 6 7910 10 1112131415 23 1112 1314 1617 18 1920 21 22 1920 21 2223 24