N-Queens functional

Question

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<List<Pos>> qu(int k, int n, List<List<Pos>> qss) {
       List<List<Pos>> result = new ArrayList<>();
       for(List<Pos> qs : qss) {
           for(int j = 1; j <= n; j++) {
              Pos newPos = new Pos(j,k);
              if (qs.stream().allMatch(pos -> safe(pos, newPos))) {
                  List<Pos> partialResult = new ArrayList<>(qs);
                  partialResult.add(newPos);
                  result.add(partialResult);
              }
           }
       }
       return result;
    }

    public static List<List<Pos>> nqueens(int n) {
        List<List<Pos>> 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;

        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
        public String toString() {
            return String.format("(%d,%d)",x,y);
        }
    }
}

Even ignoring the overhead of the Pos class the code seems to be way too verbose, and even worse, constantly jumping back and forth between imperative and functional style.

I'm still using a lot of for loops. Especially I couldn't find a good replacement for foldRight. Further, I found no good way to utilize IntStream, as its range or rangeClosed methods seemed just too inconvenient.

I'm looking for hints how to improve my code in a functional way without straying too far from the original snippets.

[Update]

Thanks to both answers and some API diving I came up with the following, which is IMHO a good compromise between conciseness and readability:

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 <T> List<T> snoc(List<T> ts, T t) {
        List<T> result = new LinkedList<>(ts);
        result.add(t);
        return result;
    }

    private static Stream<Integer> range(int fromInclusive, int toInclusive) {
        return IntStream.rangeClosed(fromInclusive, toInclusive).boxed();
    }

    private static Stream<List<Pos>> solveRow(int row, int boardSize, Stream<List<Pos>> solutions) {
        return solutions.flatMap(solution ->
                range(1, boardSize).flatMap(column ->
                        solution.stream().allMatch(pos ->
                                safe(pos, new Pos(row, column)))
                                ? Stream.of(snoc(solution, new Pos(row, column)))
                                : Stream.empty()));
    }

    public static Stream<List<Pos>> nqueens(int boardSize) {
        return range(1, boardSize).reduce(
                Stream.of(Collections.emptyList()),
                (solutions, row) -> solveRow(row, boardSize, solutions),
                Stream::concat);
    }

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

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

        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public String toString() {
            return String.format("(%d,%d)", x, y);
        }
    }
}

Answer 1

If your intention is to find a solution that is "as functional as possible", there are, of course, options to achieve this. However, if you are really looking for a purely functional solution, similar to that in Haskell, then you'll end up with a solution that looks somewhat cryptic (similar to that in Haskell ;-)).

By replacing some loops with reductions in order to emulate the foldRight, and using some ugly workarounds related to the rangeClosed method, you could end up with a single function that just provides the solution:

import static java.lang.Math.abs;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class Queens
{
    public static Stream<List<Pos>> nqueens(int n)
    {
        return IntStream.rangeClosed(1, n).mapToObj(i -> i).sorted(Comparator.reverseOrder()).reduce(
            Stream.of(new ArrayList<Pos>()), (r, i) -> r.flatMap(qs -> IntStream.rangeClosed(1, n).mapToObj(
                j -> new Pos(j, i)).flatMap(p -> (qs.stream().allMatch(
                    q -> (q.x != p.x && q.y != p.y && abs(q.x -p.x) != abs(q.y - p.y))) ? 
                        Stream.of(Stream.concat(qs.stream(), Stream.of(p)).collect(Collectors.toList())) : 
                        Stream.<List<Pos>> empty()))), Stream::concat);
    }

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

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

        public Pos(int x, int y)
        {
            this.x = x;
            this.y = y;
        }

        public String toString()
        {
            return String.format("(%d,%d)", x, y);
        }
    }
}

---

However, code like this may shed a bad light on functional programming. Depending on the language support, some things should better be solved iteratively. And more importantly: Functional programming does not mean that the functions may not have names. An implementation that is similar to what you originally proposed, but purely functional, compact, and much more readable, could be created from several functional building blocks:

import static java.lang.Math.abs;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

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 <T> List<T> concat(List<T> list, T element)
    {
        return Stream.concat(list.stream(), Stream.of(element)).
            collect(Collectors.toList());
    }

    private static Stream<List<Pos>> createIfAllSafe(List<Pos> qs, Pos newPos)
    {
        return qs.stream().allMatch(pos -> safe(pos, newPos)) ?
            Stream.of(concat(qs, newPos)) : 
            Stream.<List<Pos>>empty();
    }

    private static Stream<Pos> createNewPositions(int n, int k)
    {
        return IntStream.rangeClosed(1, n).mapToObj(j -> new Pos(j, k));
    }

    private static Stream<List<Pos>> qu(int k, int n, Stream<List<Pos>> qss)
    {
        return qss.flatMap(
            qs -> createNewPositions(n,k).flatMap(
                newPos -> createIfAllSafe(qs, newPos)));
    }

    private static Stream<Integer> descendingIntegers(int n)
    {
        return IntStream.rangeClosed(1, n).mapToObj(i -> i).sorted(
            Comparator.reverseOrder());
    }

    public static Stream<List<Pos>> nqueens(int n)
    {
        return descendingIntegers(n).reduce(
            Stream.of(new ArrayList<Pos>()), 
            (r, i) -> qu(i, n, r), 
            Stream::concat);        
    }

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

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

        public Pos(int x, int y)
        {
            this.x = x;
            this.y = y;
        }

        public String toString()
        {
            return String.format("(%d,%d)", x, y);
        }
    }
}

Answer 2

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<Position, Position> 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<List<Position>, Position, List<Position>> append = 
        (base, pos) -> {
            List<Position> 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<List<Pos>> qu(int k, int n, List<List<Pos>> qss) {
   List<List<Pos>> result = new ArrayList<>();
   for(List<Pos> qs : qss) {
       for(int j = 1; j <= n; j++) {
          Pos newPos = new Pos(j,k);
          if (qs.stream().allMatch(pos -> safe(pos, newPos))) {
              List<Pos> 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 <= n; j++) {
          Pos newPos = new Pos(j,k);
          if (qs.stream().allMatch(pos -> safe(pos, newPos))) {
              List<Pos> 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<List<Position>> descend(final List<Position> 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<T, U> {
    private final BiFunction<T,U,T> folder;
    private T state;

    public FoldLeft(BiFunction<T, U, T> 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<List<Position>> 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 could have a folding function like:

(state, row) -> state.stream().map(partial -> descend() .... 

Takes an existing state, and the row to calculate, and returns a new state.

The complete LeftFold instance would be:

    FoldLeft<List<List<Position>>, Integer> folder = new FoldLeft<>(
            (state,row) -> state.stream()
                .map(partial -> descend(partial, row.intValue(), size))
                .flatMap(result -> result.stream())
                .collect(Collectors.toList()), seed);

That's a LeftFolder that has a folding function, and an initial seed.

Using that LeftFold, you can create your actual NQueen solver with:

    IntStream.rangeClosed(1, size).forEach(row -> folder.fold(row));
    return folder.getResult();

Note that the above stream technically has side-effects in the folder, as the folder is stateful.

Here's the complete code I have for the above solution. You should be able to copy/paste and run it:

import java.util.ArrayList;
import java.util.List;
import java.util.function.BiFunction;
import java.util.function.BiPredicate;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class NQueens {

    public static final class Position {
        public final int x, y;

        public Position(int x, int y) {
            super();
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return String.format("(%d,%d)", x, y);
        }

    }

    private static final class FoldLeft<T, U> {
        private final BiFunction<T, U, T> folder;
        private T state;

        public FoldLeft(BiFunction<T, U, T> 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;
        }
    }

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

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

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

    public static List<List<Position>> nqueens(final int size) {
        List<List<Position>> seed = new ArrayList<>();
        seed.add(new ArrayList<>());

        FoldLeft<List<List<Position>>, Integer> folder = new FoldLeft<>(
                (state,row) -> state.stream()
                    .map(partial -> descend(partial, row.intValue(), size))
                    .flatMap(result -> result.stream())
                    .collect(Collectors.toList()), seed);

        IntStream.rangeClosed(1, size).forEach(row -> folder.fold(row));
        return folder.getResult();
    }

    public static void main(String[] args) {
        List<List<Position>> solution = nqueens(8);
        solution.forEach(sol -> System.out.println(sol));
        System.out.printf("Found %d solutions\n", solution.size());
    }

}