# San code – the eight queens problem

The eight queens problem is a traditional programming task used to illustrate how programming languages work. The objective is discover and print out all arrangements of eight queens on the chess board such that no queen attacks another queen. There are various refinements, e.g., one can ask for n queens on an nxn board. Here is a solution in San, followed by programming notes.

```#       This is an implementation in San of the eight queens
#       problem, for which the requirement is to print all of
#       different ways that n queens can be placed on an nxn
#       such that no two queens attack each other.
#
#       This programming task has three major parts, the
#       generation of trials, the determination of which squares
#       are attacked, and the printing of the results using a
#       specified format.
#
#       In this implementation the generation of trials is done
#       by trying queen placements on all positions on the first
#       row, then for each placement trying all positions not
#       under attack in the next row, usw.  Colors are used to
#       keep track of which squares are under attack; squares not
#       under attack are white, those attacked by a previous
#       placement are colored red.
#
#       Each solution is printed on a separate line; the
#       positions are expressed in algebraic notation.  Bilateral
#       symmetry is not exploited.  Various features of the code
#       are discussed in the programming notes below.
begin segment type=module, label=eightqueens
begin defaults
red   := "red
white := "white
n     := 8
begin init board
\$rsize  := n
\$csize  := n
\$[,]    := white
end init
firsts.row := board\$rfirst
firsts.col := board\$cfirst
end defaults
begin agent eight-queens
cand.row := board\$rfirst
begin loop cand.col from [board\$cfirst ... board\$clast]
<try board, queens, cand>
end loop
end eight-queens
begin proc try
args: board, queens, cand
append cand to queens
cand.row lt? board\$rlast => begin
mark-attacked-squares board, cand
cand.row += 1
begin loop cand.col from [board\$cfirst ... board\$clast]
board[cand.row,cand.col] eq? red => <>
else <try board, queens, cand>
end loop
end
else display-queens queens
end try
begin proc mark-attacked-squares
args: board, cand
board[,cand.col] := red
board[cand.row,] := red
begin loop
init i := cand.row
init j := cand.col
i += 1; j -= 1
i gt? board\$rlast  => escape
j lt? board\$cfirst => escape
board[i,j] := red
end
end
begin loop
init i := cand.row
init j := cand.col
i += 1; j += 1
i gt? board\$rlast => escape
j gt? board\$clast => escape
board[i,j] := red
end
end mark-attacked-squares
begin display-queens
args: queens, col-first
init colmap[] <- [alphseq | keep n]
begin loop queen from queens[]
col :=  queen.col - firsts.col + colmap\$rfirst
row :=  queen.row - firsts.row + 1
sym :=  "{colmap[col]}{row}
append sym to outlist[]
end loop
print {[outlist[] | separate 2H, ]}
end display-queens
```

## Notes

### Morphs as tables

Every morph is (potentially) a table. Tables have two vectors associated with them, a vector of row labels, and a vector of column labels. If foo is a morph, the row vector for foo is foo[] and the column vector is foo.[] . If there are no columns the row vector can be used as an array.

Table elements can be referenced using any of several syntaxes, e.g.

```        foo[i].[j]      <# row i, column j>
foo[i].a        <# row i, column labelled a>
foo[i,j]        <# row i, column j]
```
Slices (whole rows or columns) can also be referenced, e.g.,
```        foo[i].[]       <# row i]
foo[i,]         <# row i>
foo[,j]         <# column j>
foo[].a         <# column labelled a>
```
there are six values associated with the dimensioning of a morph’s table. They are:
```        \$rsize          <# the number of rows>
\$rfirst         <# index of the first row>
\$rlast          <# index of the last row>
\$csize          <# the number of columns>
\$cfirst         <# index of the first column>
\$clast          <# index of the last column>
```
These values are constrained by the relationships
```        \$rsize = \$rlast - \$rfirst + 1
\$csize = \$clast - \$cfirst + 1
```
If either the first or the last index is altered the size is left unchanged and the other index is altered to fit. If the size is changed, either by an assignment to the size value or by an assignment to the label vector, the first index is left unchanged and the other two altered to fit.

### Fill assignment and scatter assignment

San supports fill assignment, i.e., a vector or an entire table can be set to a specified value. For example
```        board[,cand.col] := red
```
sets the cand.col column to be red. Similarly
```        board[,] := white
```
sets the entire board to be white.

San also supports scatter assignment with lists on each side of an assignment arrow. For example,

```        i,j -> m,n
```
sets m := i and n := j. If there are vectors or sequents on the source side there must be a terminal vector on the receiving side. For example in
```        a[], x -> b, c[]
```
the first element of a goes into b, and the remaining elements of a[] and x go into c[].

### Visibility, defaults, and cloning

All items defined within a module (for a suitable definition of defined :-)) are visible within the module; however they are not accessible for reading and writing. Instead they are available for cloning, i.e., within a local scope all morphs referenced only have a local scope.

A defaults block sets initial default values for items commonly used throughout the module. These can be over-ridden within individual execution frame, but the over-ride applies only within the frame.

### Sequent operators and sources

Alphseq is a semi-infinite source, generating the sequence a, b, …, z, aa, ab, …, zz, aaa, …

Keep and separate are built-in sequent operators. “Keep” truncates its input sequence to the first n items. In this instance, with n = 8, colmap[] is the letters a through h. “Separate” interpolates its argument between each pair of successive elements in its input.