- Run the program for Figure 5.3 (Download).
Modify
Figure 5.3 to determine if backtracking occurs (i.e. add some print
statements).
- Use Figure 5.3 to solve the 4-queens problem. Defining the CSP by hand is
possible since there are 4 variables (columns) each with a domain of 4 values
(rows). The constrains are identical, true when different column and row and
diagonals. The following determines if two queens are in conflict.
def
conflict(row1, col1, row2, col2): # Do queens in (row1, col1) and (row2, col2)
conflict?
return (row1 == row2 or col1 == col2 or row1-col1 == row2-col2 or row1+col1 ==
row2+col2) # same - or | or \ or / ?
- Use Figure 5.3 to solve the N-queens problem. Test using 4, 8 and 16
queens. Best to generate the CSP based on a value of n.
- Using Figure 5.3 program from class as a starting point, implement the arc
consistency algorithm of Figure 5.7. Call AC3 after assigning the variable as
suggested in Chapter 5
notes.
Determine if any inconsistencies are removed from variable's domain
and if backtracking occurs (i.e. add a print statement after the test for
failure). Test using the Australia() CSP.
Comment out the AC3 call. Restrict the domain of SA to ['R'] only and
verify that backtracking does indeed occur and that a solution is found.
- Use Figure 5.7 arc consistency algorithm to solve the N-queens problem.
Test using 4, 8 and 16 queens to compare time. You may want to remove the
print statements.
Comment out the parts related to the AC3 call and repeat for 16 queens. The
results are unexpected.
- Use MIN-CONFLICTS to solve the N-queens problem. Test using 4, 16 and 100
queens. (Download)