N-Queens functional

I'm trying to get a better grip on the new functional possibilities of Java 8.

As an example, I took this very elegant Haskell snippet:

nqueens :: Int -> [[(Int,Int)]] 
nqueens n = foldr qu [[]] [1..n]
    where qu k qss = [ ((j,k):qs) | qs <- qss, j <- [1..n], all (safe (j,k)) qs ]
          safe (j,k) (l,m) = j /= l && k /= m && abs (j-l) /= abs (k-m)

I translated it to Scala, and was quite satisfied:

object queens {
   def nqueens(n: Int) = {
      import math.abs
      type Pos = (Int, Int)
      def safe(p:Pos, q:Pos) = p._1 != q._1 && p._2 != q._2 && abs(p._1 - q._1) != abs(p._2 - q._2)
      def qu(k: Int, qss:List[List[Pos]]) =
        for(qs <- qss; j <- (1 to n) if qs.forall(safe(_ ,(j,k)))) yield ((j,k) :: qs)
      (1 to n).foldRight(List(List[Pos]()))(qu)
   }
   def main(args:Array[String]) = println(nqueens(8).mkString("\n"))
}

But I think my Java translation is terrible, and I have the feeling it's still way too iterative:

```
import static java.lang.Math.*;
import java.util.*;

public class Queens {

private static boolean safe(Pos p, Pos q) {
return p.x != q.x && p.y != q.y && abs(p.x - q.x) != abs(p.y - q.y);
}

private static List> qu(int k, int n, List> qss) {
List> result = new ArrayList<>();
for(List qs : qss) {
for(int j = 1; j safe(pos, newPos))) {
List partialResult = new ArrayList<>(qs);
partialResult.add(newPos);
result.add(partialResult);
}
}
}
return result;
}

public static List> nqueens(int n) {
List> result = Collections.singletonList(new ArrayList<>());
for(int i = n; i > 0; i--) {
result = qu(i,n,result);
}
return result;
}

public static void main(String[] args) {
nqueens(8).forEach(System.out::println);
}

public static class Pos {
public final int x;
public final int y;

What an interesting challenge. Learning Java8 is on my list, so here's some suggestions I have, but bear in mind that I am learning too....

First up, lets use functions for the functions we have. Starting with the safe function:

private static boolean safe(Pos p, Pos q) {
    return p.x != q.x && p.y != q.y && abs(p.x - q.x) != abs(p.y - q.y);
}

For reasons that will become clear later, I want to invert that logic and call it a 'conflict', something that is not safe. A functional version of this would be:

// If there's a conflict between two positions,  return true.
private static final BiPredicate conflict = 
        (prev, pos) -> prev.x == pos.x || prev.y == pos.y
                    || Math.abs(prev.x - pos.x) == Math.abs(prev.y - pos.y);

Note that I have chosen to use real variable names, instead of 'a' and 'b'. I find this helps me, even in functional declarations.

OK, so conflict is a lambda expression that returns true in the event that two positions are unsafe relative to each other.

While we are talking functions, here's a part of the scala that needs to have a matching concept in Java:

yield ((j,k) :: qs)

That takes a position, and appends it to a previous list of positions.... A Java functional equivalent is:

// create a new list containing the base list contents, and the new position
private static final BiFunction, Position, List> append = 
        (base, pos) -> {
            List result = new ArrayList<>(base.size() + 1);
            result.addAll(base);
            result.add(pos);
            return result;
        };

OK, so we have two helper functions here. How can they be used?

Part of the logic in the NQueens problem, is to take one partial solution (not all the rows), and for the next row, identify which positions are safe. For all the safe solutions, 'yield' them as a new collection of partial solutions.

In your code you have this in the qu function:

private static List> qu(int k, int n, List> qss) {
   List> result = new ArrayList<>();
   for(List qs : qss) {
       for(int j = 1; j  safe(pos, newPos))) {
              List partialResult = new ArrayList<>(qs);
              partialResult.add(newPos);
              result.add(partialResult);
          }
       }
   }
   return result;
}

The qu function also loops over all partial solutions, so, the part I am really talking about is inside the outer loop... this part:

for(int j = 1; j  safe(pos, newPos))) {
              List partialResult = new ArrayList<>(qs);
              partialResult.add(newPos);
              result.add(partialResult);
          }
       }

Making that more functional, I would have something like this:

// compute all valid solutions from a given partial base solution.
private static final List> descend(final List partial, final int row, final int size) {
    return IntStream.rangeClosed(1, size)
        .mapToObj(column -> new Position(column, row))
        .filter(pos -> !partial.stream().anyMatch(prev -> conflict.test(prev, pos)))
        .map(pos -> append.apply(base, pos))
        .collect(Collectors.toList());
}

That function (not a lambda) takes a partial solution, it generates all positions on the next row, and, if the position has no conflicts, it adds a new (extended) partial solution, and outputs that.

The outer part of your qu method loops through the partial solutions so far, and then 'calls' the inner part. Taking the outside part, and making it functional, I came up with:

current.stream()
     .map(partial -> descend(partial, row.intValue(), size))
     .flatMap(result -> result.stream())
     .collect(Collectors.toList())

This says, take all our current partial solutions, for each partial one, generate a list of more complete ones. Then, flatmap those to an extended list, and collect them.

Now, that logic needs to be embedded in a left-fold operation, and you're right, one does not exist in Java. So, I built one.

A left-fold takes two inputs, and returns a result of the same type as the first. To make it work I need to keep a 'state' in order to 'accumulate' values in to. Here's my implementation:

private static final class FoldLeft {
    private final BiFunction folder;
    private T state;

    public FoldLeft(BiFunction folder, T state) {
        super();
        this.folder = folder;
        this.state = state;
    }

    public void fold(U delta) {
        state = folder.apply(state, delta);
    }

    public T getResult() {
        return state;
    }
}

A class, that takes a function, and an initial state. The function is used to convert the current state, and a new value, to a new state.

Consider an initial seed state for the partial solutions... this would be an empty solution:

List> seed  = new ArrayList<>();
    seed.add(new ArrayList<>());

So, if we have a folding function, that takes a new row to solve, and a collection of partial solutions that have been solved so far, we

StackExchange Code Review Q#78963, answer score: 8