I am trying to complete CS50's hacker edition pset3, where you have to make a program that will solve the game of eight or fifteen from its current state, this must be written in C. https://en.wikipedia.org/wiki/15_puzzle
I first tried an approach of straight going for the step that get's you closest to the goal, but found it got caught in a loop. So I added a condition of not repeating the last move which just led to a longer loop!
I am going to need a search algorithm, and have researched and now understand some of the main ones. I think breadth or depth first would be too computationally expensive on larger boards and so, as the specification recommends I am going to try A* search. Manhattan distance works easily for the heuristic as it is admissible and no. of moves from initial state for g(state).
However I am struggling mainly with the open and closed sets. So these must have the cost amount, but what representation of the game moves for that state? The whole board? But then how do you keep track of moves to get to that board for the final solution? I thought about having a massive array of like 200 to store the moves list, but for so many nodes this would be crazy. So how is the best way to represent the system and process of the game in a way that I can implement the search algorithm?