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