# Generate all possible solutions to the N queens problem.
# The board is represented by board[1:N], which records
# for each column whether there is a queen in that column,
# and if so, which row it occupies.  In particular,
#   board[j] = i if there is a queen in row i of column j
#            = 0 otherwise

resource EightQueens()
   var N : int := 8
   var solution : int := 0

   procedure safe(row, column: int; board[1:*]: int) returns answer: bool
   # Check whether it is safe to place a queen at row, column;
   #   i.e., is board[column]=row a safe configuration?
      fa j := 1 to column-1 ->
         if board[column-j] = row
               or board[column-j] = row-j
               or board[column-j] = row+j ->
            answer := false
            return
         fi
      af
      answer := true
   end safe

   procedure place(column: int; board[1:*]: int)
   # Place a queen in all safe positions of column c,
   # then try placing a queen in the next column.
   # If a position in column N is safe, print the board.
      fa row := 1 to N ->
         board[column] := row  # try placing a queen in (row,column)
         if safe(row, column, board) ->
            if column = N -> solution++   # we have a solution
            [] column<N -> place(column+1, board)  # try next column
            fi
         fi
         board[column] := 0   # unrecord that a queen was placed
      af
   end place

   getarg(1, N)
   var board[1:N]: int := ([N] 0)
   write("Solutions to the", N, "queens problem:")
   place(1, board)
   write("There are", solution, "solutions.")
end EightQueens

/* ............... Example compile and run(s)

% sr -o Nqueens Nqueens.sr
% ./Nqueens
Solutions to the 8 queens problem:
There are 92 solutions.
% time ./Nqueens 10
Solutions to the 10 queens problem:
There are 724 solutions.
68.5u 2.8s 1:50 64% 0+448k 7+0io 5pf+0w
                                              */