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

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]

        foo[i].[]       <# row i]
        foo[i,]         <# row i>
        foo[,j]         <# column j>
        foo[].a         <# column labelled a>

        $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>

        $rsize = $rlast - $rfirst + 1
        $csize = $clast - $cfirst + 1

Fill assignment and scatter assignment

        board[,cand.col] := red

        board[,] := white

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

        i,j -> m,n

        a[], x -> b, c[]

Visibility, defaults, and cloning

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

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.