# SICP Solutions

### Section - 2.2 - Hierarchical Data and the Closure Property

#### Exercise 2.42

There can be multiple ways to represent board. All we need to do is implement the procedures required in exercise such that they work correctly for our board representation.

Since at any point in the code, a column will contain only one queen. We can represent a solution by a simple list such that each element in the list corresponds to a row in board.

Thus the combination of position in this simple list and the value at this position gives us col-number and row-number of the place where queen is placed. For example:

(Taking row and col numbers to start from 1(not 0).)

For eg: Suppose one solution for 5 queens is: (4 2 5 3 1), then the corresponding board is:

0 0 0 0 1
0 1 0 0 0
0 0 0 1 0
1 0 0 0 0
0 0 1 0 0

Position containing queen is marked as 1.

Thus:
column: 1 contains queen in row = 4.
column: 2 contains queen in row = 2.
column: 3 contains queen in row = 5.
column: 4 contains queen in row = 3.
column: 5 contains queen in row = 1.

Another thing to note is that since we are filling the queens column by column while putting exactly one queen at a time in a column, it follows that we are not required to check if there are multiple queens in a column.

Thus we only need to check for duplicate/multiple queens in a row or in a diagonal.

Suppose we have already put k-1 queens in k-1 columns safely. The algorithm in exercise places the k-th queen by testing it while putting in each row of the column k.

The process for testing row-wise or diagonally is similar. So I created one procedure exists that can be used for both by passing the corresponding test condition.

I have also included procedures for displaying the board.

Here is the complete code:

Example/Output:

Example/Output: