-- Copyright 1993-1998, by the Cecil Project
-- Department of Computer Science and Engineering, University of Washington
-- See the LICENSE file for license information.


(--
    This program solves a generalization of the Eight Queens problem.
    It's another simple benchmark of Cecil performance.

    There are lots of ways to solve eight queens.
    This program uses the version from the "Stanford benchmarks."
    Credits in that source say that those benchmarks were
    "gathered by John Hennessy and modified by Peter Nye."

    The program looks for only one solution to the problem.
    The algorithm is greedy with backtracking.
    Given a board numbered <i,j> for row i, column j . . .
      - Start with i = 1 (attempt to place a queen in row 1)
      - For j = 1 to boardsize
      -  if square <i,j> is available
      -    place a queen on <i,j>
      -    recursively attempt to fill rest of board, minus this row
      -    if that fails, increment j and continue

    The data structures in this program are rather counterintuitive.
    They have been chosen to match those in the C version of the program,
    which seem to have been designed for efficiency, not clarity.
    Here are a few words of explanation:

    
	When the squares in a chessboard are numbered in standard matrix
	notation as follows:

	     11  12  13  14  15  16  17  18
	     21  22  23  24  25  26  27  28
	     31  32  33  34  35  36  37  38
	     41  42  43  44  45  46  47  48
	     51  52  53  54  55  56  57  58
	     61  62  63  64  65  66  67  68
	     71  72  73  74  75  76  77  78
	     81  82  83  84  85  86  87  88

	then the "upward" diagonals {11}, {21, 12}, {31, 22, 13}, etc.
	have constant values of i+j (from 2 to 16)
	while the "downward" diagonals {81}, {71, 82}, {61, 72, 83}, etc.
	have constant values of i-j (from 7 to -7).
	Each queen blocks off (at most) one row, one column, one upward
	diagonal, and one downward diagonal.  For example, a queen placed
	at 34 above means that no other queen can be placed in row 3,
	column 4, the upward diagonal {61, 62, 43, 34, 25, 16} (i+j == 7),
	or the downward diagonal {12, 23, 34, 45, 56, 67, 78} (i-j == -1).

    This board object thus uses three vectors to represent the effect
    of the queens that have already been placed.

      - column has one entry for each column of the board.
	column[i] is true if it's OK to place a queen in this column
	(i.e., if no queen has yet been placed in this column)
	There is no corresponding array for rows because the row
	information is maintained implicitly by starting with row 1,
	continuing to row 2, etc.  Failure to place a queen in a row
	already visited terminates the program with a failure message.

      - diag1 and diag2 play the same role for the diagonals of the board
	that column plays for columns.  Remember that when a queen is
	placed at <i,j>, the two diagonals it affects are determined
	by i+j and i-j.

      - ij is a vector of integers containing, for each row i, the
        index j of the column containing the ith queen.  Note that there
        can be at most one queen in a given row or column.  This vector
        is used only for checking solutions while debugging.  It mimics
        a vector maintained but not used by the C version of the benchmark.

    WARNING!!!  The C version of this benchmark in the Stanford suite
    solved the eight queens problem 50 times.  This program solves it
    (or the N queens problem with a little editing) _once_.
--)

template object board;
field size(@:board):int;
field column(@:board):m_vector[bool];
field diag1(@:board):m_vector[bool];
field diag2(@:board):m_vector[bool];
field ij(@:board):m_vector[int];

method create_board(boardsize:int):board {
    let col:m_vector[bool] := new_m_vector[bool](boardsize+1, true);
    let dg1:m_vector[bool] := new_m_vector[bool]((boardsize*2)+1, true);
    let dg2:m_vector[bool] := new_m_vector[bool](boardsize*2, true);
    let rc :m_vector[int]  := new_m_vector[int](boardsize+1, -1);
    concrete object isa board { size := boardsize,
				column := col,
				diag1 := dg1,
				diag2 := dg2,
				ij := rc } }

method try_next_row(b:board, row:int):bool {
    do (b.size, &(i) {
      let col:int := i+1;
      (--
      ("row = " || row.print_string).print;
      (", col = " || col.print_string).print_line;
      ("b.column = " || b.column.print_string).print_line;
      ("b.diag1 = " || b.diag1.print_string).print_line;
      ("b.diag2 = " || b.diag2.print_string).print_line;
      "---".print_line;
      --)
      if (b.column!col & { b.diag1!(row+col) & 
                 { b.diag2!(b.size + (row-col)) } }, { 
        b.ij!row := col;
        b.column!col := false;
        b.diag1!(row+col) := false;
        b.diag2!(b.size + (row-col)) := false;
        if (row < b.size, {
          if (try_next_row(b, row+1), {
            ^true
          }, {
            b.ij!row := -col;
            b.column!col := true;
	    b.diag1!(row+col) := true;
	    b.diag2!(b.size + (row-col)) := true;
          });
        },
	{
	  ^true
	});
      });
    });
    false
}

method queens(boardsize:int):bool {
    let b:board := create_board(boardsize);
    let success:bool := try_next_row(b, 1);
    (--
    " b.ij is ".print;
    b.ij.print;
    --)
    success
}

method solve_queens(size:int):void {
    "Starting queens with ".print;
    size.print;
    " queens on ".print;
    size.print;
    " by ".print;
    size.print;
    " board...".print;

    let var done:bool := false;

    garbage_collect();
    let time:int := time({
	done := queens(size);
    });
    if_false(done, { "Queens failed.  ".print_line; });
    "done. time: ".print;
    time.print;
    " ms.".print_line;
}