ECE 566
Knowledge Systems Engineering

Home           Class

Project - Constraints

Clarification about what you need to provide for parts of the constraint propagation project:

Project tasks

• Your program needs to simply ask the user which position in the first row the user wants to place the 1st queen.
• The program computes ALL POSSIBLE SOLUTIONS WHICH HAVE THE USER SPECIFIED ASSIGNMENT for the first queen using 
• Chronological backtracking and 
• The look-ahead algorithm 
• Your program prints the solutions using the given convention for the queen positions. 
• It also PRINTS (for each of the two algorithms) the number of backtracks performed to assign values for each row.

Item 3.5:

• You assume that the first queen is placed in 1A, and compute all possible solutions with this assignment for the first queen.  
• Compare the number of backtracks by chronological backtracking versus that by the look-ahead algorithm by plotting the number of backtracks. The comparison of the two algorithms for each solution produces two graphs (or one graph with the plots for the two algorithms superimposed). 
• Do this comparison for all solutions with first queen in 1A.  If there are four solutions, you will get 8 graphs.

 

Q. Do the programs need to find all possible solutions given the starting position of the first queen or do they only need to find one? 

A. The program needs to find all solutions.

 

Q. How should the counting of backtracks occur?E.g.

node A

|

|

node B

|

|

node C

|

|

node D = no solution, go back to node C.

Is the backtrack count incremented for node C or node D?

A. In your example, you assign values to D. Each time you change a value assigned to D you are backtracking at that node. In addition, when you change a value assigned to C, you are backtracking to change that assignment.Therefore you need to count each backtrack appropriately. Your drawing does not have value assignments only variable names, it may be helpful for you to draw part of the search tree.

 

Q. I just want to be sure that I understand the correct way to count backtracks. In the following "board" an x represents a queen and an o represents an empty space. 

1 2 3 4 5 6 7 8

A x o o o o o o o

B o o x o o o o o

C o o o o x o o o

D o x o o o o o o

E o o o o o o o x

F o o o o o o o o ß no available position, backtrack to row E but there

Gis no more columns to try in Row E so backtrack to row D.

HDo the backtrack counts get incremented for F, E and D?

A. In your example, I see no assignment to row F, therefore no change of value and thus no backtrack, In row E, your example has assigned the last possible value (8), therefore, when 8 does not work, there is a backtrack to try another value, thus we increment the number of backtracks for E by one. Since there is no other value for E to try, we have to backtrack to previous variable (row D) and change it, thus the number of backtracks for D should be increased by 1, at the same time that the value for row D is changed. Once this is done, you now try the possible values in domain of E one by one, and each time an assignment to E is changed its backtrack value should be increased by one, etc.

 

Q. I originally thought that backtracking was (in our example) when I went back a row. But, if I understand, it is also when I go down a row also. I.e. once I have to go back up a row the first time, every time I then go down a row that is also a backtrack.But only if a queen is placed.If no queen is placed that is not a backtrack.

A. Here is the simplest way to consider backtracks: Whenever a previously assigned value for a variable is changed to a different value that is a backtrack.

 

Q. An additional question regarding counting the backtracking.

Let me state my understanding of the definition of backtrack: For a given row, a queen is placed in a column for that row. If that placement of the queen does not yield a solution, then a backtrack occurs and another position for the queen is chosen.

The assignment states: "The program should feature a counter to count the number of backtracks made in each row (i.e. How many changes were made to the Queens position in a particular row?) until the final solution is found."

Am I correct in my understanding that the goal of the counter is to tally all the times in which a queen is moved do to failure in a given row (thus not including the times when the queen is moved after a solution is found), and that the counters are never reset thus if row 8 was processed 10 times trying to place the queen and each time there was 6 backtracks the counter would read 60?

A. Your understanding is correct.The counters must keep track of all backtracks.

 

Q. I have question(s) regarding Arc Consistency in the project.

I have developed the AC3 algorithm similar (behaves the same, but the parameters are handled differently) to what is in the notes. If my board size is 4, it behaves as I would expect it to and reduces my backtracking to 0.But, with the board size set to 8, it only removes the values that are inconsistent with placement of the queen in row 1. Is this what is expected?

Since the algorithm is checking each domain value in each row to make sure that there is at least one consistent value in the row it is checking against, given that the domain is relatively large, it is always able to find at least one that is consistent.This means the only values that are removed from the search domain are those that are inconsistent with the placement of the first queen.

My understanding of AC3 is that it is intended to be used once to prune the search space.If I were to run AC3 then pick a value for row to and run AC3 again, I would be using directional arc consistency, which is not what is asked for and even though it would reduce the number of backtracks, it is just placing them in a part where they don't get counted.

Even though AC3 is causing the number of backtracks to go down, it seems to have an unpleasant side effect that if the variable domains are large enough that there is always one consistent value, it will not reduce the search space.Which implies that for the 8 queens problem, if one doesn't assign a value for row one, the search space is not reduced at all, because the variable domains are large enough that there is always at least one value in all the other rows that is consistent.

Am I misunderstanding how this is supposed to work? Because of this I don't know where to stop and say: "I have it working correctly."

A. Please note that the assignment does not ask for implementation of AC-3 specifically. It asks for implementing 

1. Look-ahead constraint propagation, and 

2. Chronological backtracking,

and comparing the performance of the two. For details on the two methods, please look at the references, and the lecture notes.

 

Q.  I don't have the understanding of arc-consistency I thought I had. This is my understanding of the problem.

1) For the n-queens problem:

I have defined the problem as:

Queen_positions(i) are the variables where i is the row.

The domain is any of the eight squares in a queens row.

A. The above formulation is correct.

2) The constraints between any two {queen_position(i), queen_position(j)} are

queen_position(i) != queen_position(j)

queen_position(i) != queen_position(j) +- (i-j)

A. The constraints must be such that no two queens threaten each other as we did in class examples.

3) Before any variable has been labeled is the constraint graph already arc-consistent? It seems to me that it is, because for any value in the domain of one node I can find a value in a connected node that is consistent.

A. This is correct

4) Then, once I assign a value to one variable, I look-ahead and delete from the domains of all variables the inconsistent values (i.e. the row, column, and diagonal of the position I just assigned). Now, don't I still have arc-consistency among the remaining unlabeled variables (unless a variable has an empty domain)?

A. This is correct, but you also have to propagate consistency between the remaining values for the unassigned variables. This can result in pruning additional values from variable domains.

5) As I continue to label variables and delete the now-inconsistent values, I either maintain arc-consistency or I have to back up and change the label because some variable now has an empty domain. It seems that once I have labeled all the variables, and have arc-consistency that I have the solution to the problem (for this particular problem) and I have pruned the search tree to nothing.

A. If you have assigned a value to every variable you have found one solution, assuming you have maintained consistency. In propagating, whenever there is a value for a variable for which none of the values for in the domain of one of the remaining unassigned variables does not work, you prune that value from the variable's domain (thus you reduce its domain)

6) That being so, for the project what do we call backtracking? Should my back_track counter count the times I have to back up in my labeling and arc consistency checking since I am no longer really going to "search"?

A. You will end up doing a lot less backtracking with the look-ahead algorithm. You should count a backtrack whenever you need to change an assigned value to a variable (row position).

7) I have actually coded the AC-3 and REVISE algorithm almost to completion, but am not really certain now that the arc checking is really explicitly required.

A. In order to implement the look-ahead algorithm, one needs to do arc-consistency checking. Please take a look at the steps required to perform the look-ahead constraint propagation algorithm.

 

Q. I know that we are supposed to program this as a CSP.I think I'm clear on how the algorithms work etc., but I'm more unclear on whether we have to stick to the defined variables etc. Let me try to be more specific:

1) My variables I've called C1, C2, C3... C8 (for "Column 1"… "Column 8"). Now the Domain of each variable is {A, B, C… H}. When I'm coding this (using C), I'd like to use just one array C[8] as the variables. And the Domain values I'd like to actually use numeric values 1-8.Is this acceptable?

A. This will be acceptable.

2) Now, how to represent the Constraints has really baffled me.I know that they are C1 != C2 etc., but do I actually make a data structure with these constraints or do I simply write a function to verify that the values selected don't violate them?That is, do I have to pass the Constraints into the function, or just write the function so that it checks them?

A. This will be up to you, either approach works. You can write a function that checks if two assignments violate the no threat constraints. Also you are asked to provide a constraint network formulation for the given problem, with the nodes, the edges, the constraints, the domains, etc.

 

Q.  What about Compound Labels etc.?I know the solutions are compound labels etc. But, do I use these in my program?

A. This is the part of the assignment that you are to determine.