Compare three CSP algorithms:
Backtracking, Forward Checking and MAC, all enhanced with MRV, Degree, and LCV heuristics
The N-Queens problem asks you to place N queens on an N×N chessboard so that no two queens share the same row, column, or diagonal. It is a classic combinatorial puzzle that grows rapidly in complexity as N increases.
We model it as a Constraint Satisfaction Problem (CSP): each row is a variable, each column position is a possible value, and the constraints rule out any placement that causes a conflict. Three algorithms — Backtracking, Forward Checking, and MAC — then search for a valid solution, each exploring the space differently.
Three algorithms. One problem. Compare their efficiency side by side.
Assigns queens row by row, undoing placements when a conflict is detected. The baseline CSP approach.
After each assignment, prunes conflicting values from future rows' domains to fail earlier.
Enforces arc-consistency after each assignment, propagating constraints across all remaining rows.
MRV selects the most constrained row. Degree breaks ties. LCV orders values to minimize eliminations.
Configure the board and run all three algorithms instantly.
Khalid Al Dosari
Zeyad bin Nazir