Lab 5 – Constraint Satisfaction with Eight Queens
Overview
The eight queens problem is a classic illustration of constraint satisfaction. The problem says that you should place eight queens on an 8x8 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:
os
random
sys
time
Backtracking Algorithm Understanding
Examine the code. Explain how the code is behaving within the context of this particular problem.
Now that you have investigated the code, specify the problem in terms of the following:
Variables
Domains
Constraints
Explain the idea of propagating constraints and unpropagating constraints in the n-Queens problem provided. Why is unpropagating constraints necessary?
Consistency
Explain the following terms.
Node Consistency
Arc Consistency
Path Consistency
Does the provided code maintain arc consistency? If not, explain how you could maintain arc consistency in the n-Queens problem.
