1
$\begingroup$

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?

Many thanks

$\endgroup$
  • $\begingroup$ I don't understand what you are asking. Can you clarify? An open/closed set contains a list of states; I'm not sure what you mean by asking about the "representation of the game moves for that state" or the relationship of that to the open and closed sets. Are you perhaps asking, once A* finds the shortest path to the target state, how do we recover what that path was? If so, please edit the question to clarify that this is what you are asking and remove the other questions. There's lots written on A* online; have you checked the resources available to you before asking here? $\endgroup$ – D.W. Jan 25 '17 at 21:56
2
$\begingroup$

First of all, the $N$-puzzle is hard to solve with A$^*$ using the Manhattan distance. Instead, we use IDA$^*$. To see the technical details involved in the design of IDA$^*$ specifically for solving the 15-Puzzle see Korf, Richard E. Depth-First Iterative-Deepening: An Optimal Admissible Tree Search, 27 (1985), 97-109. Artificial Intelligence. As a matter of fact, Richard Korf provided a wonderful implementation of his algorithm where he used various tricks to make his solver really fast: a pre-computed table stores the results of all operators to all states; another table stores the variation in the value of the Manhattan distance for each operator, and such. His implementation is publicly available here and you are very welcome to use it provided that you preserve the name of its author, Richard Korf, along with the copyright notice.

If you insist in using A$^*$ for solving the $N$-puzzle then see Matthew Hatem, Ethan Burns, and Wheeler Ruml, Problem Solving with Heuristic Search and Java, IBM developerWorks, July, 2013. The source code is publicly available here. True, their implementation is in Java and their solution considers various issues which are not straight forward in C such as templates. However, most of the ideas are generically discussed (and, indeed, various issues regarding the open and closed lists are considered to a large extent) so that an implementation in C should not be hard.

Finally, let me stress that Manhattan distance is a rather poor heuristic for this domain. On one hand, it can be significantly enhanced with the so called conflict-based heuristic. On the other hand, Pattern Databases are a wonderful means for efficiently solving even the 25-Puzzle (even if some instances can take hours to be optimally solved).

Hope this helps,

$\endgroup$
  • $\begingroup$ Thanks a lot @olliejday for closing this question! Very much appreciated. $\endgroup$ – Carlos Linares López Jan 27 '17 at 9:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.