15,997,776 members
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
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.

## Solution 1

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.

## Solution 2

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.

## Solution 3

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.

Top Experts
Last 24hrsThis month
 Richard Deeming 50 Dave Kreskowiak 10 Manas Bhardwaj 5 Sergey Alexandrovich Kryukov 0
 OriginalGriff 431 Pete O'Hanlon 225 Richard Deeming 175 Dave Kreskowiak 123 CPallini 110

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