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. 

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;

6 comments:

  1. Your interpretation of "concurrent" for the Vector> would overconstrain the solution, would it not? That data structure is "write-only" in your algorithm, the order of updates doesn't matter, and it is modified only by appending. You could use a lock-free data structure in that case.

    I don't think "continue"-type statements are hard to read by default, but this one seems awkward. Maybe it's because your "continue" syntax is so verbose?

    continue Outer_loop (C => C+1, Trial => Trial | R, ...)

    It could also be because the place where you name Outer_Loop doesn't have an immediate connection with the loop itself. Finally, it could be because there's only one loop variable (C) and so it would seem more natural to program with a traditional iterative syntax (or forget it and write recursively).

    I do like the idea of loop+continue as an alternate syntax for recursion. I think it's most useful when the algorithm really calls for iterative expression ("for all (key,value) in a hash table"), but has the occasional corner case where a recursive expression helps.

    ReplyDelete
  2. Thanks for your comment. I agree that a lock-free data structure could accommodate order-free appending. But that would require some amount of manual coding to correctly design the lock-free appending. I was playing around with the idea of being able to turn any data structure into a concurrent one without extra manual effort by falling back on locking, but I agree more interesting would be to be able to do the same thing with some kind of standard lock-free approach.

    ReplyDelete
  3. I just fixed one bug in the above, where "Sum" and "Diff" were declared as Integer types rather than as Vectors of Booleans indexed by the appropriate range of integer. The more elegant fix would be to declare Sum and Diff as Sets over the given range of integers. That would probably also be easier to understand. Hence:

    type Sum is Set<Integer<2, 2*N>>;
    type Diff is Set<Integer<1-N, N-1>>;
     ...
    for (... Diag1 : Sum := []; Diag2 : Diff := []) loop
     ...
     if (R+C) not in Diag1 and then
      (R-C) not in Diag2 then
      ...
      continue ... with (...
        Diag1 => Diag1 | (R+C),
        Diag2 => Diag2 | (R-C));

    ReplyDelete
  4. After reading my comment, i realize that the "continue Outer_loop" example might as well just be a (tail) recursive call. oh well ;-)

    ReplyDelete
  5. Thanks for sharing. I also tried using the lock-free data structure in that case and it works.

    ReplyDelete
  6. @Tuck It's both legit and good to have a fallback model for "concurrent," so that you can insert optimizations invisibly as they become available. My only concern is that a "concurrent vector" is more complicated than what the algorithm needs, but it should still result in correct code.

    ReplyDelete