8-Queens Problem in Artificial Intelligence

The 8-Queens Problem is a classical Toy Problem in Artificial Intelligence. It is used to understand problem formulation, state-space search, backtracking, constraint satisfaction, heuristic search, and optimization techniques.

The problem looks simple, but it demonstrates an important AI concept:

How can an intelligent system find a valid solution from a very large number of possible combinations while satisfying a set of constraints?

1. Definition

The 8-Queens Problem is the problem of placing 8 queens on an 8 × 8 chessboard such that no two queens attack each other.

In chess, a queen can attack another queen if they are in the same:

Row
Column
Diagonal

Therefore, the objective is:

Place 8 queens on the chessboard so that no two queens share the same row, column, or diagonal.

2. Example of a Solution

One valid solution is:

+---+---+---+---+---+---+---+---+
| Q |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   | Q |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   | Q |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   | Q |   |   |
+---+---+---+---+---+---+---+---+
|   |   | Q |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   | Q |   |
+---+---+---+---+---+---+---+---+
|   | Q |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   | Q |   |   |   |   |
+---+---+---+---+---+---+---+---+

Here, every row contains one queen, every column contains one queen, and no two queens share a diagonal.

3. Why is it an AI Problem?

The 8-Queens Problem is an AI problem because the computer must:

Represent the current board.
Generate possible positions.
Check constraints.
Reject invalid configurations.
Continue searching.
Backtrack when necessary.
Find a valid final configuration.

So the basic process is:

Initial State
      ↓
Place Queen
      ↓
Check Constraints
      ↓
Valid?
  ↙       ↘
Yes       No
 ↓         ↓
Continue  Reject
 ↓
Goal?
 ↓
Solution

4. Rules of the 8-Queens Problem

There are three major constraints.

Constraint 1 — No Same Row

Two queens cannot be placed in the same row.

Q
Q    ← Invalid

Constraint 2 — No Same Column

Two queens cannot be placed in the same column.

Q
|
Q    ← Invalid

Constraint 3 — No Same Diagonal

Two queens cannot share a diagonal.

Q
 \
  Q     ← Invalid

Therefore:

Final condition

No two queens can attack each other.

5. State Representation

There are different ways to represent a state.

A convenient representation is a one-dimensional array.

For example:

[1, 5, 8, 6, 3, 7, 2, 4]

Here:

Position = row number
Value = column number

So:

Row 1 → Column 1
Row 2 → Column 5
Row 3 → Column 8
Row 4 → Column 6
Row 5 → Column 3
Row 6 → Column 7
Row 7 → Column 2
Row 8 → Column 4

This represents:

Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . Q . . . . .
. . . . . . Q .
. Q . . . . . .
. . . Q . . . .

6. Problem Formulation

The 8-Queens problem can be formally defined as an AI search problem.

Component	8-Queens
Initial State	Empty chessboard
State	Partial placement of queens
Actions	Place a queen in a safe position
Transition	Add a queen to the board
Goal Test	8 queens placed safely
Path Cost	Number of placements or another defined cost

7. Initial State

The initial state is:

Empty Board

. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .

8. Goal State

The goal state is any configuration in which:

8 queens are placed
+
No two queens attack each other

There are 92 distinct solutions to the 8-Queens problem when board positions are treated as distinct, while considering rotations/reflections as separate solutions. If solutions equivalent under rotations and reflections are grouped together, there are 12 fundamental solutions.

9. State-Space Search

The AI can search through possible configurations.

Conceptually:

                    Empty Board
                         |
              ┌──────────┼──────────┐
              ↓          ↓          ↓
             Q1         Q2         Q3
              |
        Place next queen
              |
       ┌──────┼──────┐
       ↓      ↓      ↓
     Valid   Valid  Invalid
       |
    Continue
       |
     Goal?

The search continues until a valid configuration is found.

10. Backtracking

The most common classical technique for solving the 8-Queens Problem is Backtracking.

Basic idea

Place a queen, check whether the placement is safe. If it is safe, continue. If it leads to a dead end, go back and change the previous placement.

This is called backtracking.

11. Backtracking Example

Suppose the AI starts placing queens:

Row 1 → Column 1

Then:

Row 2 → Column 3

But suppose a later placement causes a conflict.

The AI does not start from the beginning.

Instead:

Current path
     ↓
Conflict
     ↓
Go back
     ↓
Change previous choice
     ↓
Try another position

This saves considerable search effort.

12. Backtracking Algorithm

The basic algorithm is:

PlaceQueen(row):

    if row > 8:
        solution found

    for each column:
        if position is safe:
            place queen
            PlaceQueen(row + 1)
            remove queen

The important operation is:

Place → Explore → If failure → Remove → Try next

13. Safety Test

Before placing a queen, the AI must check whether the position is safe.

Suppose a queen is being placed at:

(row, column)

The position is invalid if another queen already exists in:

Same column

\[ c_1=c_2 \]

Same diagonal

Two queens are on the same diagonal when:\[ |r_1-r_2|=|c_1-c_2| \]

This is an important formula for students.

14. Example of Diagonal Checking

Suppose:

Queen A = (2,3)
Queen B = (4,5)

Calculate:\[ |4-2|=2 \]

and\[ |5-3|=2 \]

Since:\[ |r_1-r_2|=|c_1-c_2| \]

the queens are on the same diagonal.

Therefore, the placement is invalid.

15. Constraint Satisfaction Problem

The 8-Queens problem can also be viewed as a Constraint Satisfaction Problem (CSP).

We have:

Variables

Q1, Q2, Q3, ..., Q8

Each variable represents a row.

Domain

Each queen can be placed in one of:

{1,2,3,4,5,6,7,8}

representing the possible columns.

Constraints

For every pair of queens:\[ Q_i \neq Q_j \]

This prevents the same column.

And:\[ |Q_i-Q_j| \neq |i-j| \]

This prevents diagonal conflicts.

Thus, the problem becomes:

Assign a column to every row while satisfying all constraints.

16. Why Use One Queen Per Row?

A useful simplification is to place exactly one queen in each row.

Then the row constraint is automatically satisfied.

The problem becomes:

Row 1 → Choose column
Row 2 → Choose column
Row 3 → Choose column
...
Row 8 → Choose column

The AI only needs to check:

Column conflicts
Diagonal conflicts

This dramatically simplifies the search.

17. Number of Possible Configurations

If we place one queen in each row and allow any of the 8 columns, the number of possible configurations is:\[ 8^8 \]\[ =16,777,216 \]

This is a large number.

But if we also ensure that no two queens occupy the same column, the possibilities become:\[ 8! \]\[ =40,320 \]

Backtracking further reduces the practical search because invalid partial solutions are rejected early.

18. 8-Queens Using DFS

Backtracking is closely related to Depth-First Search (DFS).

The search explores one branch deeply:

Row 1
 ↓
Row 2
 ↓
Row 3
 ↓
Row 4
 ↓
Conflict
 ↓
Backtrack

Then it tries another branch.

Therefore:

Backtracking can be viewed as a depth-first search with constraint checking and pruning.

This is an important connection to your syllabus.

19. Search Tree

Conceptually, the search tree looks like:

                 Empty
                   |
          ┌────────┼────────┐
          ↓        ↓        ↓
         C1       C2       C3
          |
     ┌────┼────┐
     ↓    ↓    ↓
    C1   C2   C3
     |
   Conflict
     |
 Backtrack
     |
 Try another

The AI does not need to explore branches that have already violated a constraint.

This process is called pruning.

20. Heuristic Approach

Although classical backtracking is common, heuristic techniques can also be used.

For example:

Minimum Conflicts

Select a queen position that minimizes the number of conflicts with other queens.

Suppose several positions are available:

Position	Conflicts
A	3
B	1
C	4
D	0

The AI selects:

because it has zero conflicts.

21. Hill Climbing and 8-Queens

The 8-Queens problem is also a classic example for Hill Climbing.

Instead of constructing the board row by row, we can start with a random arrangement.

For example:

[3, 1, 6, 8, 5, 2, 4, 7]

Then define a heuristic such as:

Number of pairs of queens attacking each other.

The objective is:\[ h(n)=\text{Number of conflicts} \]

The goal is:\[ h(n)=0 \]

The AI repeatedly makes changes that reduce the number of conflicts.

22. Genetic Algorithm and 8-Queens

The 8-Queens Problem can also demonstrate Genetic Algorithms.

A chromosome can represent a board:

[1,5,8,6,3,7,2,4]

The fitness function can reward configurations with fewer conflicts.

The process becomes:

Initial Population
       ↓
Fitness Evaluation
       ↓
Selection
       ↓
Crossover
       ↓
Mutation
       ↓
New Population
       ↓
Repeat
       ↓
Solution

This connects the 8-Queens problem with the Genetic Algorithm portion of your syllabus.

23. Comparison of Techniques

Technique	Approach	Main Idea
BFS	Uninformed Search	Explore level by level
DFS	Uninformed Search	Explore deeply
Backtracking	DFS + constraints	Reject invalid branches
Hill Climbing	Heuristic	Reduce conflicts
Genetic Algorithm	Evolutionary	Evolve better solutions
CSP	Constraint-based	Satisfy all constraints

For teaching the classical solution, Backtracking + CSP is the most important combination.

24. Pseudocode

A simple pseudocode version:

N-QUEENS(row):

    if row > N:
        print solution
        return

    for column = 1 to N:

        if SAFE(row, column):

            board[row] = column

            N-QUEENS(row + 1)

            board[row] = empty

The safety function:

SAFE(row, column):

    for every previously placed queen:

        if same column:
            return false

        if same diagonal:
            return false

    return true

For 8-Queens:

N = 8

25. Python Example

For MCA students, a simple Python implementation can help demonstrate the concept:

N = 8
board = [-1] * N

def is_safe(row, col):
    for previous_row in range(row):
        previous_col = board[previous_row]

        # Same column
        if previous_col == col:
            return False

        # Same diagonal
        if abs(previous_row - row) == abs(previous_col - col):
            return False

    return True


def solve(row):
    if row == N:
        print(board)
        return True

    for col in range(N):
        if is_safe(row, col):
            board[row] = col

            if solve(row + 1):
                return True

            # Backtracking
            board[row] = -1

    return False


solve(0)

The important part for students is not memorizing the code, but understanding:

Choose
 ↓
Check
 ↓
Place
 ↓
Recurse
 ↓
Failure?
 ↓
Backtrack

26. Backtracking in Simple Words

A very simple way to explain backtracking to students is:

“Try a choice. If the choice works, move forward. If it causes a problem, come back and try another choice.”

For example:

Try Column 1
     ↓
Works
     ↓
Try next row
     ↓
Conflict
     ↓
Go back
     ↓
Try Column 2

This is exactly how a human might solve the puzzle logically.

27. Applications of the Same Concept

The 8-Queens problem represents a broader class of constraint-based problems.

Similar techniques are used in:

Timetable scheduling
Exam scheduling
Job scheduling
Resource allocation
Employee assignment
Sudoku solving
Map coloring
Seating arrangements
Configuration problems

For example, in college timetable scheduling:

Courses
   ↓
Teachers
   ↓
Rooms
   ↓
Time slots
   ↓
Constraints
   ↓
Valid timetable

This is conceptually similar to:

Queens
   ↓
Rows
   ↓
Columns
   ↓
Diagonal constraints
   ↓
Valid board

28. Why 8-Queens is Important in AI

The problem teaches several important AI concepts:

1. State Representation

Represent the board efficiently.

2. Search

Explore possible configurations.

3. Constraints

Reject illegal configurations.

4. Backtracking

Return to an earlier decision when a branch fails.

5. Heuristics

Use information about the current state to make better decisions.

6. Optimization

Try to find a configuration with zero conflicts.

7. Constraint Satisfaction

Find an assignment satisfying all constraints.

29. Water Jug vs 8-Puzzle vs 8-Queens

This is useful for students because all three appear in your syllabus.

Feature	Water Jug	8-Puzzle	8-Queens
Type	Toy Problem	Toy Problem	Toy Problem
Main concept	State-space search	Search + heuristic	Constraints + search
State	`(x,y)`	Board arrangement	Queen positions
Actions	Fill/empty/pour	Move blank	Place queen
Goal	Desired quantity	Goal board	No conflicts
Important technique	BFS/DFS	A*	Backtracking/CSP
Heuristic	Less important	Very important	Conflicts/minimum conflicts
Main lesson	Problem formulation	Heuristic search	Constraint satisfaction

30. Exam-Oriented Answer

Definition

The 8-Queens Problem is a classical Artificial Intelligence problem in which eight queens must be placed on an 8 × 8 chessboard such that no two queens attack each other. No two queens can occupy the same row, column, or diagonal. The problem is commonly solved using backtracking and can also be formulated as a Constraint Satisfaction Problem.

Problem formulation:

Initial State → Empty chessboard

State → Partial placement of queens

Action → Place a queen in a safe position

Constraint →
No same row
No same column
No same diagonal

Goal Test →
All 8 queens placed safely

Important formulas:

Same column:\[ c_1=c_2 \]

Same diagonal:\[ |r_1-r_2|=|c_1-c_2| \]

Main algorithm:

Place Queen
     ↓
Check Safe Position
     ↓
Yes ──→ Place Queen
         ↓
      Next Row
         ↓
      Continue
         ↓
     Solution?

No ───→ Backtrack
          ↓
       Try Again

Key takeaway

The 8-Queens Problem demonstrates how AI can solve a complex combinatorial problem by representing states, applying constraints, searching through possible solutions, pruning invalid choices, and using backtracking to find a valid solution.

For your MCA syllabus, the most important connection is:

8-Queens → State Space → Constraints → DFS → Backtracking → CSP → Heuristics → Genetic Algorithm.