Description
Artificial Intelligence Page 1
Overview
The eight queens problem is a classic illustration of constraint satisfaction. The problem says that you should
place eight queens on an 8×8 chessboard such that no queen can capture another. When placed row-by-row, the
possible placements in the next rows are constrained by each placement. If you have a position to place a
queen in each row, you’ve found a solution. This problem is generalized as the n-queens problem.
Backtracking Code Exploration
Download the lab5.py file from the D2L dropbox. The code requires the following libraries:
1. os
2. random
3. sys
4. time
Backtracking Algorithm Understanding
1. Examine the code. Explain how the code is behaving within the context of this particular problem.
2. Now that you have investigated the code, specify the problem in terms of the following:
a. Variables
b. Domains
c. Constraints
3. Explain the idea of propagating constraints and unpropagating constraints in the n-Queens problem
provided. Why is unpropagating constraints necessary?
Consistency
4. Explain the following terms.
Node Consistency
Arc Consistency
Path Consistency
5. Does the provided code maintain arc consistency? If not, explain how you could maintain arc consistency
in the n-Queens problem.
CSCI 5260 – Artificial Intelligence Page 2
Submission
Create a Word Document named SurnameLab5.docx with your responses above.
Submit to the Lab 5 dropbox at or before Monday, February 22, by 11:59 PM.
Grading
A letter grade will be assigned for each response. The letter grades are based on both correctness and the
adequacy of answers. Points are assigned as follows:
A B C D F Zero
Excellent Above
Average Average Below
Average Poor No Attempt
10 8 6 4 2 0
Backtracking
Q1
Q2
Q3
Consistency Q4
Q5
