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 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:
- 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.
