home
table of contents
Comp Sci
October 2003
email

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.


This page was last updated October 1, 2003.

home
table of contents
Comp Sci
October 2003
email