## Wednesday, September 14, 2011

### N Queens Join the Party

We are continuing to work on the ParaSail compiler. Our latest program to compile and run is a parallel but non-recursive version of a solution to the "N Queens" problem. There is an N_Queens module, with a nested Solution_State module used to represent a partial solution. The algorithm starts at column 1 and works toward column N, branching into parallel threads to evaluate each possibility for the next row, and when finding an acceptable one, circling back to the outer loop to march onto the next column. There is a simple Test_N_Queens func at the bottom.  Below that is the result of running the program.

Enjoy!

```interface N_Queens <N : Univ_Integer := 8> is
// Place N queens on an NxN checkerboard so that none of them can
// "take" each other.
type Chess_Unit is new Integer_Range<-100 .. 100>;
// An integer type sufficiently big to represent values -100 to +100
const Rows : Range<Chess_Unit> := 1..N;
const Columns : Range<Chess_Unit> := 1..N;
type Row is Chess_Unit {Row in Rows};  // A subrange in 1..N
type Column is Chess_Unit {Column in Columns};  // A subrange in 1..N
type Solution is Array<optional Column, Row>;
// A "solution" is an array of Column's, indexed by "Row."
// It indicates in which Column a queen of the given Row is located
// An example solution would be:  2 8 6 1 3 5 7 4
//   meaning that the queen in row 1 is at column 2,
//   the queen in row 2 is at column 8, the queen in
//   row 3 is at column 6, and so on.

func Place_Queens() -> Vector<Solution>
{for all Sol of Place_Queens => for all Col of Sol => Col not null};
// Produce a vector of solutions, with the requirement
// that for each solution, there are non-null column numbers
// specified for each row of the checkerboard.
end interface N_Queens;

class N_Queens is
type Sum_Range is Chess_Unit {Sum_Range in 2..2*N};
// Sum_Range is used for diagonals where the row+column is the
// same throughout the diagonal.
type Diff_Range is Chess_Unit {Diff_Range in (1-N) .. (N-1)};
// Diff_Range is used for diagonals where row-column is the
// same throughout the diagonal.
type Sum is Countable_Set<Sum_Range>;
// This type of set keeps track of which Sum_Range diagonals
// have a queen on them already.
type Diff is Countable_Set<Diff_Range>;
// This type of set keeps track of which Diff_Range diagonals
// have a queen on them already.

interface Solution_State<> is
// We build up a solution state progressively as we move
// across the checkerboard, one column at a time.
func Initial_State() -> Solution_State;
func Is_Acceptable(S : Solution_State; R : Row) -> Boolean;
// Is_Acceptable returns True if the next queen could be
// place in row R.
func Current_Column(S : Solution_State) -> Column;
// Current_Column indicates which column we are working on.
func Next_State(S : Solution_State; R : Row) -> Solution_State;
// Next_State returns a Solution_State produced by
// adding a queen at (Current_Column(S), R).
func Final_Result(S : Solution_State; R : Row) -> Solution;
// Final_Result returns a result produced by adding a queen
// at (Columns.Last, R) to a solution with all other columns
// placed.
end interface Solution_State;

class Solution_State is
const C : Column;    // Current column
const Trial : Solution;  // Trial solution, some col#s still null
const Diag_Sum : Sum;   // Set of "sum" diagonals in use
const Diag_Diff : Diff; // Set of "diff" diagnoals in use
exports
func Initial_State() -> Solution_State is
return (C => 1, Trial => Create(Rows, null),
Diag_Sum => [], Diag_Diff => []);
end func Initial_State;

func Is_Acceptable(S : Solution_State; R : Row) -> Boolean is
// Is_Acceptable returns True if the next queen could be
// place in row R.
return S.Trial[R] is null and then
(R+S.C) not in S.Diag_Sum and then
(R-S.C) not in S.Diag_Diff;
end func Is_Acceptable;

func Current_Column(S : Solution_State) -> Column is
// Current_Column indicates which column we are working on.
return S.C;
end func Current_Column;

func Next_State(S : Solution_State; R : Row) -> Solution_State is
// Next_State returns a Solution_State produced by
// adding a queen at (Current_Column(S), R).
return (C => S.C+1,
Trial     => S.Trial | [R => S.C],
Diag_Sum  => S.Diag_Sum | (R+S.C),
Diag_Diff => S.Diag_Diff | (R-S.C));
end func Next_State;

func Final_Result(S : Solution_State; R : Row) -> Solution is
// Final_Result returns a result produced by adding a queen
// at (Columns.Last, R) to a solution with all other columns
// placed.
return S.Trial | [R => S.C];
end func Final_Result;

end class Solution_State;

exports
func Place_Queens() -> Vector<Solution>
{for all Sol of Place_Queens => for all Col of Sol => Col not null}
// Produce a vector of solutions, with the requirement
// that for each solution, there are non-null column numbers
// specified for each row of the checkerboard.
is
var Solutions : concurrent Vector<Solution> := [];

*Outer_Loop*
for State : Solution_State := Initial_State() loop
// Iterate over the columns

for R in Rows concurrent loop
// Iterate over the rows
if Is_Acceptable(State, R) then
// Found a Row/Column combination that is not on any diagonal
if Current_Column(State) < N then
// Keep going since haven't reached Nth column.
continue loop Outer_Loop with Next_State(State, R);
else
// All done, remember trial result with last queen placed
Solutions |= Final_Result(State, R);
end if;
end if;
end loop;
end loop Outer_Loop;
return Solutions;

end func Place_Queens;
end class N_Queens;

func Test_N_Queens() is
type Eight_Queens is N_Queens<8>;
var Results := Eight_Queens::Place_Queens();
Println("Number of results = " | Length(Results));
for I in 1..Length(Results) forward loop
const Result := Results[I];
Print("Result #" | I);
for J in 1..Length(Result) forward loop
Print(" " | [[Result[J]]]);
end loop;
Print('\n');
end loop;
end func Test_N_Queens;
```

Here is the result of running Test_N_Queens, which is set up to solve the 8-queens problem. It has also been verified to work with 4 queens (2 solutions), 5 queens (10 solutions), and 9 queens (352 solutions). After "quit"ing, a display of threading statistics is provided.

```Parsing aaa.psi
Parsing n_queens4.psl
---- Beginning semantic analysis ----
58 trees in library.
Done with First pass.
Done with Second pass.
Done with Pre codegen pass.
Done with Code gen.

Command to execute: Test_N_Queens

Number of results = 92
Result #1 4 2 5 8 6 1 3 7
Result #2 1 7 4 6 8 2 5 3
Result #3 4 2 8 5 7 1 3 6
Result #4 1 5 8 6 3 7 2 4
Result #5 4 1 5 8 6 3 7 2
Result #6 2 7 3 6 8 5 1 4
Result #7 7 1 3 8 6 4 2 5
Result #8 5 2 4 6 8 3 1 7
Result #9 5 7 1 3 8 6 4 2
Result #10 5 1 8 6 3 7 2 4
Result #11 1 6 8 3 7 4 2 5
Result #12 4 2 7 3 6 8 1 5
Result #13 3 1 7 5 8 2 4 6
Result #14 3 6 2 7 5 1 8 4
Result #15 5 1 4 6 8 2 7 3
Result #16 6 4 2 8 5 7 1 3
Result #17 3 6 2 5 8 1 7 4
Result #18 1 7 5 8 2 4 6 3
Result #19 3 7 2 8 5 1 4 6
Result #20 2 6 1 7 4 8 3 5
Result #21 3 7 2 8 6 4 1 5
Result #22 4 6 8 2 7 1 3 5
Result #23 4 1 5 8 2 7 3 6
Result #24 7 4 2 8 6 1 3 5
Result #25 3 6 8 2 4 1 7 5
Result #26 5 1 8 4 2 7 3 6
Result #27 7 4 2 5 8 1 3 6
Result #28 4 7 5 2 6 1 3 8
Result #29 7 3 8 2 5 1 6 4
Result #30 5 7 2 6 3 1 8 4
Result #31 5 7 2 4 8 1 3 6
Result #32 4 7 3 8 2 5 1 6
Result #33 4 7 1 8 5 2 6 3
Result #34 7 3 1 6 8 5 2 4
Result #35 6 3 7 2 8 5 1 4
Result #36 6 1 5 2 8 3 7 4
Result #37 4 8 1 5 7 2 6 3
Result #38 6 3 1 7 5 8 2 4
Result #39 6 3 7 2 4 8 1 5
Result #40 6 4 1 5 8 2 7 3
Result #41 5 7 2 6 3 1 4 8
Result #42 5 7 1 4 2 8 6 3
Result #43 3 5 2 8 1 7 4 6
Result #44 4 6 1 5 2 8 3 7
Result #45 2 7 5 8 1 4 6 3
Result #46 5 3 1 6 8 2 4 7
Result #47 4 2 7 5 1 8 6 3
Result #48 6 3 1 8 5 2 4 7
Result #49 3 8 4 7 1 6 2 5
Result #50 6 8 2 4 1 7 5 3
Result #51 5 3 1 7 2 8 6 4
Result #52 2 5 7 4 1 8 6 3
Result #53 3 6 2 7 1 4 8 5
Result #54 6 3 1 8 4 2 7 5
Result #55 4 2 8 6 1 3 5 7
Result #56 8 3 1 6 2 5 7 4
Result #57 3 5 8 4 1 7 2 6
Result #58 4 8 1 3 6 2 7 5
Result #59 6 3 5 8 1 4 2 7
Result #60 6 3 7 4 1 8 2 5
Result #61 8 4 1 3 6 2 7 5
Result #62 8 2 5 3 1 7 4 6
Result #63 6 3 5 7 1 4 2 8
Result #64 4 8 5 3 1 7 2 6
Result #65 7 2 6 3 1 4 8 5
Result #66 2 4 6 8 3 1 7 5
Result #67 5 2 4 7 3 8 6 1
Result #68 3 5 2 8 6 4 7 1
Result #69 4 6 8 3 1 7 5 2
Result #70 4 7 5 3 1 6 8 2
Result #71 3 6 4 2 8 5 7 1
Result #72 2 6 8 3 1 4 7 5
Result #73 5 7 4 1 3 8 6 2
Result #74 7 5 3 1 6 8 2 4
Result #75 4 2 7 3 6 8 5 1
Result #76 6 4 7 1 8 2 5 3
Result #77 5 2 6 1 7 4 8 3
Result #78 7 2 4 1 8 5 3 6
Result #79 6 2 7 1 3 5 8 4
Result #80 8 2 4 1 7 5 3 6
Result #81 3 6 8 1 5 7 2 4
Result #82 5 2 8 1 4 7 3 6
Result #83 5 3 8 4 7 1 6 2
Result #84 3 6 8 1 4 7 5 2
Result #85 5 8 4 1 7 2 6 3
Result #86 3 6 4 1 8 5 7 2
Result #87 3 5 7 1 4 2 8 6
Result #88 6 2 7 1 4 8 5 3
Result #89 6 4 7 1 3 5 2 8
Result #90 5 8 4 1 3 6 2 7
Result #91 2 5 7 1 3 8 6 4
Result #92 2 8 6 1 3 5 7 4

Command to execute: quit