Programming Interview Question: Eight Queens(jetheis.com)

   #include <stdio.h>

   int main(void)
   {
       unsigned long pos;

       for (pos = 0; pos <= 077777777; ++pos)
       {
           unsigned long tmppos = pos;
           unsigned long taken = 0;
           int rank;
           int file;

           for (file = 0; file < 8; ++file)
           {
               unsigned long mask;

               rank = tmppos & 07;

               mask = (1L << file) |       /* file */
                       (1L << (rank + 8)) |    /* rank */
                       (1L << (23 + file - rank))  /* diagonal */
                       | (1L << (45 - file - rank)); /* other diagonal */
               if (taken & mask)
                   goto fail;
               taken |= mask;
               tmppos >>= 3;
           }
           printf("%lo\n", pos);
   fail:   ;
       }
       return 0;
   }

  def complete_board(board, l):
    """If possible, completes a board (whose first l rows
    have been filled with 1 queen per row).  Returns
    true if this is possible, false otherwise

    board is a list of ints representing the position
    (0-based) of each queen"""

    N = len(board)

    if l == N:
      return True

    # determine the valid positions for a queen in the r'th row
    valid = [True] * N
    for row, col in enumerate(board[:l]):
      valid[col] = False
      s = l - row
      if col + s < N:
        valid[col + s] = False
      if col - s >= 0:
        valid[col - s] = False

    for col, v in enumerate(valid):
      if v:
        board[l] = col
        if complete_board(board, l + 1):
          return True
    return False

    newtype Board = Board [Int] deriving ( Eq, Show )
    emptySolution = Board []

    attempts :: Int -> Board -> [Board]
    attempts n (Board queens) = 
      map (\r -> Board (r : queens)) ([0 .. n - 1] \\ queens)

    valid :: Board -> Bool
    valid (Board []) = True
    valid (Board (q:cols)) = 
      and $ map (\(n, c) -> abs (q - c) /= n) (zip [1..] cols)

      -- this is a bit clever, as we walk back through
      -- the previous columns, if the absolute difference
      -- between the row position of the new queen and
      -- an old queen is ever the count of the column 
      -- we're in, then it must be in a diagonal line
      -- from the new queen

    queens :: Int -> [Board]
    queens n = search n [emptySolution] where
      search 0 boards = boards -- no more queens to add
      search k boards = do
        board <- search (k - 1) boards -- find a smaller solution
        filter valid (attempts board)  -- try all possible extensions,
                                       -- remove the bad ones

    >>> length (queens 8)
    92

    iterateM :: Monad m => (a -> m a) -> a -> [m a]
    iterateM f x = iterate (f =<<) (return x)

    queens n = iterateM (filter valid . attempts n) emptySolution !! n

    -- this is the list monad definition
    instance Monad [] where
      return a = [a]
      xs >>= f = concat (map f xs)

    iterateList :: (a -> [a]) -> a -> [[a]]
    iterateList f x = iterate (concat . map f) [x]