Problem Set 2

Assigned: Feb. 5:
Due: Feb. 19

Programming and experimental assignment

Programming

Implement the GSAT algorithm for the N-queens problem using the following three states spaces.

State space 1.

A state is any placement of queens on the board. An operator is either to add or to delete a queen. The error function is (the number of pairs that attack one another) + max(0,N-(the number of queens on the board)

State space 2

A state is any placement of 1 queen per column. An operation is to change the column of 1 queen. The error function is the number of pairs of queens that attack one another.

For example, for the 8-queens, one state would be [4,5,1,3,3,1,8,6] The error function would be 9: 1,4 attacks 2,5; 2,5 attacks 4,3; 2,5 attacks 6,1; 3,1 attacks 5,3; 3,1 attacks 6,1; 3,1 attacks 8,6; 4,3 attacks 5,3; 4,3 attacks 6,1; 5.3 attacks 8,6. One operator would be to move the queen in the 3rd column to 7, giving [4,5,7,3,3,1,8,6].

State space 3

A state is a placement of 1 queen per column and row; that is, a permutation of the columns into the rows. An operator would be to swap the row value for two columns. The error function is the number of pairs of queens that attack one another.

For example one state would be [4,6,8,1,3,5,7,2]. An operator would be to switch columns 4 and 8, giving [4,6,8,2,3,5,7,1].

Parameters:

Use an upper bound of 2000 for the inner loop of GSAT and an upper bound of 5 for the outer loop. Extra credit: Find a good tuning for these parameters as a function of the size of the various problems.

Coding

You may use any language you like, as long as it runs on the Sun system.

Experiment

Test each of the above state space searches with N=25, 50, 75, 100. Run twenty instances of each. For each state space and for each size, report:

You do not have to let any instance of an experiment run for more than 1 minute.

Submitting the assignment

Sean McLaughlin (seanmcl@cs.nyu.edu) is the TA for this course. You should mail him Email the report to me (davise@cs.nyu.edu) as well.

If you prefer, you may hand in the report in hard copy.

Late Assignments

Since I am not handing out solutions, I can be more flexible about accepting late assignments. There will be a late penalty of 0.5 out of 10 for each week late. (Round up to get the number of weeks late; e.g. an assignment handed in day after class is considered 1 week late.)