Admissible Heuristic for n-Queens Problem

Question

Given all queens are in their own columns, and a move is defined as picking up a queen and moving to any other row in the same column, what is an admissible heuristic for this problem?

[We note that by the structure of the problem, we always have a queen in each column.]

Answer 1

1. f(row): I count the number D of queens in each row. If D>1, then this row has conflicts and I record D-1 which means that D-1 queens have conflicts with the 1st queen in this row. If D<2, I record 0 which means that no conflict in this row. (I only consider the conflicts in the horizontal direction.)
2. Admissible heuristic: Add the records in each row from the 1st row to the nth row. 
   Sum(f(row)) for all 1<= row <= n

Answer 2

Amount of empty rows.

For example 4-queen problem.

1 0 0 0

0 1 1 1

0 0 0 0

0 0 0 0

Then h = 2;

Answer 3

To calculate the heuristic that considers both vertical, horizontal, and diagonal attacks, we need to sum up the counts of attacking pairs for each of these categories. Let's denote these counts as follows:

• V: Number of pairs of queens attacking each other vertically.

• H: Number of pairs of queens attacking each other horizontally.

• D: Number of pairs of queens attacking each other diagonally.

The final admissible heuristic would then be the sum of these counts:

Heuristic=V+H+D

This heuristic is admissible because it provides a lower bound on the number of moves required to reach the goal state. It's consistent because moving a queen to a different row in the same column, to a different column, or diagonally will either decrease the count of vertical, horizontal, or diagonal attacks, or leave it unchanged.