## Programming Assignment 1

Assigned: Feb. 5
Due: Feb. 26

### 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 row 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:
• For each size, the percentage that find a solution.
• The mean, the maximum, the minimum, and the standard deviation of the running times, in terms of total number of iterations of the internal loop, over the set of runs that find a solution.

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

### Submitting the assignment

Bing Sun(bingsun@cs.nyu.edu) is the TA for this course. You should mail her
• The source code for your program or programs