Yashoda Shikshan Prasarak Mandal’s

YASHODA TECHNICAL CAMPUS, SATARA

FACULTY OF ENGINEERING
NH-4, Wadhe Phata, Satara., Tele Fax- 02162-271238/39/40
Website- [Link] Email-admin@[Link]
Approved by AICTE- New Delhi, Govt. of Maharashtra (DTE, Mumbai)
Affiliated to DBATU Lonere.

DEPARTEMENT OF COMPUTER SCIENCE AND ENGINEERING

Name: Rukkaiya Jamadar PRN: 2267571242070

Class: Final Year Div: A
Roll No: 69 Subject : AI

CAS ACTIVITY 1
Backtracking Search for Constraint Satisfaction Problems (CSPs)
1. Introduction

Constraint Satisfaction Problems (CSPs) form the foundation of many real-world applications,
including Sudoku, scheduling, map coloring, and the N-Queens problem. A CSP is defined by
a set of variables, their domains (possible values), and constraints that restrict combinations
ofvalues.
To solve CSPs, backtracking search is one of the most fundamental and widely used
algorithms. It incrementally builds partial solutions and abandons paths that cannot lead to
valid outcomes, thus systematically exploring the solution space.

2. Backtracking Search: Definition and Process

Backtracking search is essentially a depth-first search algorithm adapted for CSPs. Unlike
brute force approaches, it prunes infeasible branches early, reducing unnecessary
exploration.

The key steps include:

1. Variable Selection – Choose an unassigned variable from the problem.

2. Value Assignment – Assign a value to the chosen variable from its domain.
3. Constraint Checking – Verify whether the assignment is consistent with all constraints.

Vision of department: To lead in technical, quality education, innovation, research for development of sustainable & inclusive technology
for the society.
Mission of department: 1. To create ambience of academic excellence through state of art infrastructure. 2. To create student-centric
pedagogy that will lead to employability.3. To create a software engineering professional with knowledge of multidisciplinary fields, can
provide innovative products & service to society.4. To train and motivate the students for lifelong learning, employability, and
entrepreneurship
 Yashoda Shikshan Prasarak Mandal’s
YASHODA TECHNICAL CAMPUS, SATARA
FACULTY OF ENGINEERING
NH-4, Wadhe Phata, Satara., Tele Fax- 02162-271238/39/40
Website- [Link] Email-admin@[Link]
Approved by AICTE- New Delhi, Govt. of Maharashtra (DTE, Mumbai)
Affiliated to DBATU Lonere.

DEPARTEMENT OF COMPUTER SCIENCE AND ENGINEERING

4. Recursion – Move forward and attempt assignments for the next variables.
5. Backtracking – If an inconsistency is found, undo the last assignment and try a
different value.

This process continues until either a solution is found or the search space is fully explored.

3. Enhancements to Backtracking Search

Although backtracking is systematic, it can still be inefficient in large or complex CSPs. To

improve performance, the following enhancements are commonly used:

• Forward Checking
After assigning a value to a variable, eliminate inconsistent values from the domains
of unassigned variables. This reduces future conflicts and unnecessary exploration.
• Constraint Propagation
Techniques like Arc Consistency (AC-3) enforce consistency across variables, ensuring
that domains remain valid at every step. This significantly prunes the search space.
• Heuristics for Variable and Value Ordering
o Minimum Remaining Values (MRV) – Select the variable with the fewest
possible legal values.
o Degree Heuristic – Prefer the variable that is involved in the most constraints.
o Least Constraining Value – Choose the value that restricts the fewest options
for neighboring variables.

These enhancements help the algorithm explore more promising paths first and avoid
wasteful computation.

Vision of department: To lead in technical, quality education, innovation, research for development of sustainable & inclusive technology
for the society.
Mission of department: 1. To create ambience of academic excellence through state of art infrastructure. 2. To create student-centric
pedagogy that will lead to employability.3. To create a software engineering professional with knowledge of multidisciplinary fields, can
provide innovative products & service to society.4. To train and motivate the students for lifelong learning, employability, and
entrepreneurship
 Yashoda Shikshan Prasarak Mandal’s
YASHODA TECHNICAL CAMPUS, SATARA
FACULTY OF ENGINEERING
NH-4, Wadhe Phata, Satara., Tele Fax- 02162-271238/39/40
Website- [Link] Email-admin@[Link]
Approved by AICTE- New Delhi, Govt. of Maharashtra (DTE, Mumbai)
Affiliated to DBATU Lonere.

DEPARTEMENT OF COMPUTER SCIENCE AND ENGINEERING

4. Advantages of Backtracking Search

• Simplicity – Easy to understand and implement, making it a common choice in

introductory AI and algorithm design.
• Generality – Can be applied to a wide range of CSPs, from puzzles to scheduling
problems.
• Effectiveness – Efficiently prunes infeasible branches, often finding solutions more
quickly than naive brute force search.

5. Limitations of Backtracking Search

Despite its usefulness, backtracking has notable drawbacks:

• Inefficiency – For large-scale or highly constrained CSPs, the search may still require
significant time.
• Memory Usage – Requires storage of partial assignments, which can grow in size for
complex problems.
• Non-optimality – While it finds feasible solutions, it does not guarantee the optimal
one in cases where multiple solutions exist.

6. Example Application: The N-Queens Problem

The N-Queens problem is a classic application of backtracking search. The task is to place N
queens on an N×N chessboard such that no two queens threaten each other.

• Process – The algorithm places queens row by row. If a conflict arises (two queens
attacking each other), the algorithm backtracks and tries another position.

Vision of department: To lead in technical, quality education, innovation, research for development of sustainable & inclusive technology
for the society.
Mission of department: 1. To create ambience of academic excellence through state of art infrastructure. 2. To create student-centric
pedagogy that will lead to employability.3. To create a software engineering professional with knowledge of multidisciplinary fields, can
provide innovative products & service to society.4. To train and motivate the students for lifelong learning, employability, and
entrepreneurship
 Yashoda Shikshan Prasarak Mandal’s
YASHODA TECHNICAL CAMPUS, SATARA
FACULTY OF ENGINEERING
NH-4, Wadhe Phata, Satara., Tele Fax- 02162-271238/39/40
Website- [Link] Email-admin@[Link]
Approved by AICTE- New Delhi, Govt. of Maharashtra (DTE, Mumbai)
Affiliated to DBATU Lonere.

DEPARTEMENT OF COMPUTER SCIENCE AND ENGINEERING

• Efficiency – With enhancements like forward checking and heuristics, the search can
solve even large N-Queens instances effectively.

This problem demonstrates how backtracking can systematically explore possibilities while
avoiding invalid paths.

7. Conclusion

Backtracking search remains a cornerstone algorithm for solving CSPs. Its systematic
exploration, combined with pruning strategies, makes it highly effective for small to medium-
sized problems. With enhancements such as forward checking, constraint propagation, and
intelligent heuristics, backtracking becomes a practical approach to solving complex puzzles
and real-world tasks.

However, its inefficiency for large CSPs and lack of guaranteed optimality highlight the need
for more advanced techniques (e.g., local search, constraint optimization). Still, as a
fundamental method, backtracking provides an excellent foundation for understanding
problem-solving in artificial intelligence.

8. References

1. GeeksforGeeks: Backtracking Search for CSPs

2. Berkeley AI Project: Solving CSPs
3. AIMA Python Code Repository: Backtracking Search

Vision of department: To lead in technical, quality education, innovation, research for development of sustainable & inclusive technology
for the society.
Mission of department: 1. To create ambience of academic excellence through state of art infrastructure. 2. To create student-centric
pedagogy that will lead to employability.3. To create a software engineering professional with knowledge of multidisciplinary fields, can
provide innovative products & service to society.4. To train and motivate the students for lifelong learning, employability, and
entrepreneurship
 Yashoda Shikshan Prasarak Mandal’s
YASHODA TECHNICAL CAMPUS, SATARA
FACULTY OF ENGINEERING
NH-4, Wadhe Phata, Satara., Tele Fax- 02162-271238/39/40
Website- [Link] Email-admin@[Link]
Approved by AICTE- New Delhi, Govt. of Maharashtra (DTE, Mumbai)
Affiliated to DBATU Lonere.

DEPARTEMENT OF COMPUTER SCIENCE AND ENGINEERING

MINDMAP:

Vision of department: To lead in technical, quality education, innovation, research for development of sustainable & inclusive technology
for the society.
Mission of department: 1. To create ambience of academic excellence through state of art infrastructure. 2. To create student-centric
pedagogy that will lead to employability.3. To create a software engineering professional with knowledge of multidisciplinary fields, can
provide innovative products & service to society.4. To train and motivate the students for lifelong learning, employability, and
entrepreneurship