Reputation: 524
I am stuck solving a task requiring me to calculate the minimal number of steps required to go from point A to point B with different chess pieces on a n*m board that also has obstacles and also output the path taken.
I was looking at the A* algorithm, but it requires me to get a good heuristic estimate which I have no idea how to get for a chess piece like a knight
What I have been trying to do is first using Breadth-First Search to find the minimal number of steps required to get from point A to point B without obstacles and then use the A* algorithm
public void AllPaths(int[,] chessBoard, int startX, int startY, int dimension) {
// All the moves a knight can make
int[] movementX = new int[8]{-2, -2, -1, -1, 1, 1, 2, 2};
int[] movementY = new int[8]{-1, 1, -2, 2, -2, 2, -1, 1};
chessBoard[startX, startY] = 0;
for (int step = 0; step < dimension-1; step++) {
for (int x = 0; x < dimension; x++) {
for (int j = 0; j < dimension; j++) {
if (chessBoard[x, j] == step) {
for (int k = 0; k < 8; k++) {
if (movementY[k] + x>= 0 && movementY[k] + x < dimension && movementX[k] + j >= 0 && movementX[k]+j < dimension) {
if (chessBoard[movementY[k]+x,movementX[k]+j] == -1) {
chessBoard[movementY[k]+x,movementX[k]+j] = step + 1;
}
}
}
}
}
}
}
}
The input and output for a knight's moves are as follows:
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
- starting from the top left
0 3 2 3 2 3 4 5
3 4 1 2 3 4 3 4
2 1 4 3 2 3 4 5
3 2 3 2 3 4 3 4
2 3 2 3 4 3 4 5
3 4 3 4 3 4 5 4
4 3 4 3 4 5 4 5
5 4 5 4 5 4 5 6
This works for n*n boards, but I need it to work for n*m boards as well. Am I going in the right direction or should I use something else completely? What do I have to change for it to work for n*m boards? Thanks for any suggestions you may have about solving the problem I have.
Upvotes: 1
Views: 2098
Reputation: 700212
You need two parameters to describe the n*m board.
Instead of looping to the theoretical maximum number of steps, just loop until you have filled the board:
public void AllPaths(int[,] chessBoard, int startX, int startY, int dimensionX, int dimensionY) {
// All the moves a knight can make
int[] movementY = { -2, -2, -1, -1, 1, 1, 2, 2 };
int[] movementX = { -1, 1, -2, 2, -2, 2, -1, 1 };
chessBoard[startX, startY] = 0;
int cnt = dimensionX * dimensionY - 1:
int step = 0;
while (cnt > 0) {
for (int x = 0; x < dimension; x++) {
for (int y = 0; y < dimension; y++) {
if (chessBoard[x, y] == step) {
for (int k = 0; k < 8; k++) {
int dx = movementX[k] + x, dy = movementY[k] + y;
if (dx >= 0 && dx < dimensionX && dy >= 0 && dy < dimensionY) {
if (chessBoard[dx, dy] == -1) {
chessBoard[dx, dy] = step + 1;
cnt--;
}
}
}
}
}
}
step++;
}
}
Upvotes: 4