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
                  // already occupied.
                  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

Threading Statistics:
 Num_Initial_Thread_Servers : 10
 Num_Dynamically_Allocated_Thread_Servers : 0
 Max_Waiting_Threads (for server task): 74
 Max_Active : 118
 Max_Active_Masters : 133
 Max_Sub_Threads_Per_Master : 87
 Max_Waiting_For_Threads (to finish): 37171

No comments:

Post a Comment