8-Queens Problem

The 8-Queens Problem

• The goal is to place 8 queens on a chessboard so that no queen attacks another.
• The problem remains a useful test for search algorithms despite efficient special-purpose algorithms existing for it.

Formulation of the 8-Queens Problem

• There are two main formulations: incremental and complete-state.
• Incremental formulation involves adding queens to an empty state, while complete-state formulation starts with all 8 queens on the board and moves them around.

Incremental Formulation

• States: Any arrangement of 0 to 8 queens on the board.
• Initial state: No queens on the board.
• Actions: Add a queen to any empty square.
• Transition model: Returns the board with a queen added to the specified square.
• Goal test: 8 queens are on the board, none attacked.

Searching for Solutions

• A solution is an action sequence, and search algorithms work by considering possible action sequences.
• The search tree has the initial state at the root, with branches representing actions and nodes representing states in the state space.
• A general tree-search algorithm considers all possible paths, whereas a graph-search algorithm avoids redundant paths.

Expanding the Search Tree

• Expanding the current state generates new states by applying legal actions.
• The search algorithm chooses which branch to consider further, following up one option and putting others aside for later.

The Frontier

• The set of all leaf nodes available for expansion at any given point is called the frontier.
• The process of expanding nodes on the frontier continues until a solution is found or there are no more states to expand.

Measuring Problem-Solving Performance

• Evaluating an algorithm's performance involves four criteria:
• Completeness: Guaranteed to find a solution when there is one?
• Optimality: Does the strategy find the optimal solution?
• Time complexity: How long does it take?
• Other criteria may also be considered.

Learn about the classic 8-queens problem where the goal is to place eight queens on a chessboard without attacking each other. Discover different formulations and algorithms used to solve this popular test problem for search algorithms.