Click here to Skip to main content
15,936,887 members
Please Sign up or sign in to vote.
1.00/5 (3 votes)
See more:
How can you implement the A* algorithm in C++ to solve the 15 puzzle?

What I have tried:

I have been reading about the A* algorithm but do not know how implement it in C++
Posted
Comments
Richard Deeming 1-May-24 4:38am    
Step 1: Work out what your requirements are.
Step 2: Learn about the algorithm, and decide whether it is appropriate for the problem you are trying to solve.
Step 3: Write some code.

Nobody here is going to do your homework for you. If you genuinely don't know where to start, then talk to your teacher.
Richard MacCutchan 1-May-24 6:21am    
That's really a valid answer, Richard.

As others have said, it's important to start simple and then work your way to the solution step by step. Some knowledge of C++ is required, which can be acquired in this project using a practical example.

Here are some basic first steps:

1. find a data structure that represents the 15-puzzle. This could be a 4x4 matrix, for example. At the beginning, 15 cells are given a value and
the free field could be defined as 0. A flexible data structure in C++ for the data field, which also makes it acceptable to change the dimension, would be a vector. It could look something like this:

C++
// Data of the puzzle field
class PuzzleGrid {
public:
    // constructor that determines the size of the puzzle
    PuzzleGrid(int rows, int cols) : grid(rows, std::vector<int>(cols, 0)) {}
    void setValue(int row, int col, int value) { grid[row][col] = value; }
    int getValue(int row, int col) const { return grid[row][col]; }
private:
    std::vector<std::vector<int>> grid; // The puzzle field
};

struct Point {
    Point(int x, int y): x(x), y(y) {} // Constructor
    int x, y; // X,y position
};

// State of the puzzle
struct PuzzleState {
    // constructor 
    PuzzleState(const PuzzleGrid& data, const Point& emptyPos): puzzleData(data), emptyCellPos(emptyPos) {}
    // States
    PuzzleGrid puzzleData; // The assignment of the playing field
    Point emptyCellPos; // The position of the empty field
};
2. write an initial test program that uses the data structure. You would also need a function to display the field on the screen, as well as a function that shuffles the field. Functions are also needed to move the empty field in all directions (up, down, left, right), if possible.The border must of course be taken into account when moving.

3. a function is needed that can evaluate the current state of a field. Here you could use the distance as the sum of the horizontal and vertical distances of each puzzle piece from its final position.

4. after calculating the distances of each piece to the target position, you need to use the A* algorithm to find the optimal solution path.

Set up a workable framework up to this point and think about the implementation of the A*. If further questions arise, it is best to open a new question.
 
Share this answer
 
So it is time to Learn C++ to get the job done.

To kickstart your learning process you should profit from my 20+ year experience in How to start a Developer career. This will help you to avoid some common traps and give you some orientation.

Good luck.
 
Share this answer
 
Writing an A* algorithm is a hard thing to do if you don't have a decent amount of programming knowledge already. If you don't have a good grasp of C++, then writing a relatively complex algorithm such as A* is going to be beyond you right now. If you want to learn A* and how it applies to C++, start with a textbook or a good online tutorial about A* and work with that. Look at multiple implementations to decide what works for you, and what doesn't. For instance, you might see algorithms that use nodes to represent items in your path, while others might use simple arrays and integers.

Take the time to really understand what the code is doing and then, following Richard Deeming's advice, decide whether the algorithm is appropriate for you, and write your code to do it.

Once you have code, if you are stuck or having problems with a particular part, come back here and we will help you with the bits you are having a problem with.

Ultimately, if we write the code for you, you learn nothing. You haven't actually had to think it through so you haven't learned any lessons about it. By writing it yourself, you get both the satisfaction of doing it, and a deeper understanding of the algorithm.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900