interface N_Queens <N : Univ_Integer := 8> is
// Place N queens on a checkerboard so that none of them can
// "take" each other.
type Row is new Integer<1, N>;
function Place_Queens() -> Vector<Vector<Row>>
{for all I in Place_Queens#range : Length(Place_Queens[I]) == N};
end interface N_Queens;
class N_Queens <N : Univ_Integer := 8> is
type Column is new Integer<1, N>;
type Sum is Vector<Boolean, Index => Integer<2, 2*N>>;
type Diff is Vector<Boolean, Index => Integer<1-N, N-1>>;
exports
function Place_Queens() -> Vector<Vector<Row>>
{for all I in Place_Queens#range : Length(Place_Queens[I]) == N} is
// Place N queens on checkerboard so that none of them can "take" each other
var Solutions : concurrent Vector<Vector<Row>> := [];
*Outer_Loop*
for (C : Column := 1; Trial : Vector<Row> := [];
Diag1 : SSum := [.. => #false]; Diag2 : Diff := [.. => #false]) loop
// Iterate over the columns
for R in Row concurrent loop
// Iterate over the rows
if not Diag1[R + C] and then not Diag2[R - C] then
// Found a Row/Column combination that is not on any diagonal
// already occupied.
if C < N then
// Keep going since haven't reached Nth column.
continue loop Outer_Loop with (C => C+1, Trial => Trial | R,
Diag1 => Diag1 | [(R+C) => #true],
Diag2 => Diag2 | [(R-C) => #true]);
else
// All done, remember trial result.
Solutions |= Trial;
end if;
end if;
end loop;
end loop Outer_Loop;
return Solutions;
end function Place_Queens;
end class N_Queens;
Saturday, July 17, 2010
N Queens Problem in ParaSail
Here is a (parallel) solution to the "N Queens" problem in ParaSail, where we try to place N queens on an NxN chess board such that none of them can take each other. This takes the idea of using the "continue" statement as a kind of implicit recursion to its natural conclusion. This presumes you can turn a "normal" data structure like Vector<> into a concurrent data structure by using the keyword "concurrent," which presumably means that locking is used on all operations to support concurrency. It is debatable whether this use of a "continue" statement to effectively start the next iteration of a loop almost like a recursive call is easier or harder to understand than true recursion.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment