When Two tiles tj and tk are in a linear conflict if tj and tk are in the same line, the goal positions of tj and tk are both in that line, tj is to the right of tk and goal position of tj is to the left of the goal position of tk.
The linear conflict adds at least two moves to the Manhattan Distance of the two conflicting tiles, by forcing them to surround one another. Therefore the heuristic function will add a cost of 2 moves for each pair of conflicting tiles.
The Linar Conflict Heuristic is admissible, but the algorithm I am using sometimes violates admissibility meaning it is pessimistic and will not necessarily find an optimal position.
Here is the code:
private int linearVerticalConflict(State s) {
int state[] = s.getState();
int dimension = (int) Math.sqrt(state.length);
int linearConflict = 0;
int count = 0;
for (int row = 0; row < dimension; row++) {
int max = -1;
for (int column = 0; column < dimension; column++) {
int cellValue = state[count];
count++;
//int cellValue = newState[row][column];
//is tile in its goal row ?
if (cellValue != 0 && (cellValue - 1) / dimension == row) {
if (cellValue > max) {
max = cellValue;
} else {
//linear conflict, one tile must move up or down to
// allow the other to pass by and then back up
//add two moves to the manhattan distance
linearConflict += 2;
}
}
}
}
return linearConflict;
}
private int linearHorizontalConflict(State s) {
int[] state = s.getState();
int dimension = (int) Math.sqrt(state.length);
int linearConflict = 0;
int count = 0;
for (int column = 0; column < dimension; column++) {
int max = -1;
for (int row = 0; row < dimension; row++) {
int cellValue = state[count];
count++;
//is tile in its goal row ?
if (cellValue != 0 && cellValue % dimension == column + 1) {
if (cellValue > max) {
max = cellValue;
} else {
//linear conflict, one tile must move left or right to allow the other to pass by and then back up
//add two moves to the manhattan distance
linearConflict += 2;
}
}
}
}
return linearConflict;
}
The algorithm violates admissibility when: Say we are focusing on one row which has the configuration [ 3, 1, 2 ]
Let's assume [ 1, 2, 3 ] is the goal configuration.
The summed manhattan distance for the problem is: 4 (3 moves 2 times, 1 moves 1 time and 2 moves 1 time) The linear conflict for the row is: 4 ( 1 and 2 are both less than 3 so +2+2 )
Which results in an overall heuristic estimate of 8. [ 3, 1, 2 ] can be solved in 6 moves,