JNTU B.Tech IV ARTIFICIAL INTELLIGENCE Previous Question Paper (September - 2020 - R15)

The 8-queens problem can be formulated as a Constraint Satisfaction Problem (CSP) by defining variables, domains, and constraints as follows:

Variables: Let the variables be X = {X1, X2, ..., X8}, where each variable Xi represents the row position of the queen in the i-th column.

Domains: Each variable Xi has a domain D = {1, 2, 3, 4, 5, 6, 7, 8}, representing the possible row indices for a queen in that column.

Constraints: The constraints ensure that no two queens attack each other, which requires that no two queens share the same row, column, or diagonal:

1. Row Constraint: For all i ≠ j, Xi ≠ Xj. This ensures no two queens are in the same row.
2. Diagonal Constraint: For all i ≠ j, |Xi - Xj| ≠ |i - j|. This ensures no two queens are on the same diagonal, as the slope between any two queens must not be 1 or -1.

Since each variable is assigned a unique column index by definition, the column constraint is implicitly satisfied.

Heuristic search techniques are informed search strategies that use domain-specific knowledge to improve the efficiency of the search process. Unlike uninformed searches (like BFS or DFS) that explore the state space blindly, heuristic searches use a heuristic function, denoted as h(n), to estimate the cost from a current node n to the goal state.

Key aspects include:

• Efficiency: By prioritizing nodes that appear closer to the goal, the search space is pruned, significantly reducing time and memory consumption.
• Evaluation Function: Algorithms like A* search use an evaluation function f(n) = g(n) + h(n), where g(n) is the cost from the start node to n, and h(n) is the estimated cost from n to the goal.
• Admissibility: A heuristic is considered admissible if it never overestimates the actual cost to reach the goal, which guarantees that A* finds the optimal solution.

Common examples include Greedy Best-First Search, which expands the node that appears closest to the goal, and A* Search, which balances the path cost and the heuristic estimate.