**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!

interfaceN_Queens <N : Univ_Integer := 8>is// Place N queens on an NxN checkerboard so that none of them can// "take" each other.typeChess_UnitisnewInteger_Range<-100 .. 100>;// An integer type sufficiently big to represent values -100 to +100constRows : Range<Chess_Unit> := 1..N;constColumns : Range<Chess_Unit> := 1..N;typeRowisChess_Unit {RowinRows};// A subrange in 1..NtypeColumnisChess_Unit {ColumninColumns};// A subrange in 1..NtypeSolutionisArray<optionalColumn, 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.funcPlace_Queens() -> Vector<Solution> {forallSolofPlace_Queens =>forallColofSol => Colnotnull};// 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.endinterfaceN_Queens;classN_QueensistypeSum_RangeisChess_Unit {Sum_Rangein2..2*N};// Sum_Range is used for diagonals where the row+column is the// same throughout the diagonal.typeDiff_RangeisChess_Unit {Diff_Rangein(1-N) .. (N-1)};// Diff_Range is used for diagonals where row-column is the// same throughout the diagonal.typeSumisCountable_Set<Sum_Range>;// This type of set keeps track of which Sum_Range diagonals// have a queen on them already.typeDiffisCountable_Set<Diff_Range>;// This type of set keeps track of which Diff_Range diagonals// have a queen on them already.interfaceSolution_State<>is// We build up a solution state progressively as we move// across the checkerboard, one column at a time.funcInitial_State() -> Solution_State;funcIs_Acceptable(S : Solution_State; R : Row) -> Boolean;// Is_Acceptable returns True if the next queen could be// place in row R.funcCurrent_Column(S : Solution_State) -> Column;// Current_Column indicates which column we are working on.funcNext_State(S : Solution_State; R : Row) -> Solution_State;// Next_State returns a Solution_State produced by// adding a queen at (Current_Column(S), R).funcFinal_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.endinterfaceSolution_State;classSolution_StateisconstC : Column;// Current columnconstTrial : Solution;// Trial solution, some col#s still nullconstDiag_Sum : Sum;// Set of "sum" diagonals in useconstDiag_Diff : Diff;// Set of "diff" diagnoals in useexportsfuncInitial_State() -> Solution_Stateisreturn(C => 1, Trial => Create(Rows,null), Diag_Sum => [], Diag_Diff => []);endfuncInitial_State;funcIs_Acceptable(S : Solution_State; R : Row) -> Booleanis// Is_Acceptable returns True if the next queen could be// place in row R.returnS.Trial[R]isnullandthen(R+S.C)notinS.Diag_Sumandthen(R-S.C)notinS.Diag_Diff;endfuncIs_Acceptable;funcCurrent_Column(S : Solution_State) -> Columnis// Current_Column indicates which column we are working on.returnS.C;endfuncCurrent_Column;funcNext_State(S : Solution_State; R : Row) -> Solution_Stateis// 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));endfuncNext_State;funcFinal_Result(S : Solution_State; R : Row) -> Solutionis// Final_Result returns a result produced by adding a queen// at (Columns.Last, R) to a solution with all other columns// placed.returnS.Trial | [R => S.C];endfuncFinal_Result;endclassSolution_State;exportsfuncPlace_Queens() -> Vector<Solution> {forallSolofPlace_Queens =>forallColofSol => Colnotnull}// 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.isvarSolutions :concurrentVector<Solution> := []; *Outer_Loop*forState : Solution_State := Initial_State()loop// Iterate over the columnsforRinRowsconcurrentloop// Iterate over the rowsifIs_Acceptable(State, R)then// Found a Row/Column combination that is not on any diagonal// already occupied.ifCurrent_Column(State) < Nthen// Keep going since haven't reached Nth column.continueloopOuter_LoopwithNext_State(State, R);else// All done, remember trial result with last queen placedSolutions |= Final_Result(State, R);endif;endif;endloop;endloopOuter_Loop;returnSolutions;endfuncPlace_Queens;endclassN_Queens;funcTest_N_Queens()istypeEight_QueensisN_Queens<8>;varResults := Eight_Queens::Place_Queens(); Println("Number of results = " | Length(Results));forIin1..Length(Results)forwardloopconstResult := Results[I]; Print("Result #" | I);forJin1..Length(Result)forwardloopPrint(" " | [[Result[J]]]);endloop; Print('\n');endloop;endfuncTest_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