N-皇后函数

Question

我试图更好地掌握Java 8的新功能可能性。

举个例子，我以这个非常优雅的Haskell片段为例：

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)

我把它翻译成Scala，非常满意：

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"))
}

但是我认为我的Java翻译很糟糕，而且我觉得它仍然太迭代了：

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);
        }
    }
}

即使忽略了Pos类的开销，代码似乎过于冗长，更糟糕的是，在命令式和函数式之间不断地跳来跳去。

我还在用很多的循环。尤其是我找不到一个很好的替代foldRight。此外，我没有发现利用IntStream的好方法，因为它的range或rangeClosed方法似乎太不方便了。

我正在寻找一些提示，如何在不偏离原始代码段的情况下，以功能方式改进我的代码。

更新

感谢两个答案和一些API跳水，我想出了以下内容，这是IMHO在简洁性和可读性之间的一个很好的折衷：

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

如果你的意图是找到一个“尽可能发挥作用”的解决方案，当然也有实现这一目标的选择。但是，如果您真的在寻找一个与Haskell类似的纯功能解决方案，那么最终您将得到一个看起来有点神秘的解决方案(类似于Haskell中的解决方案；-)。

通过将一些循环替换为简化以模拟foldRight，并使用与rangeClosed方法相关的一些难看的解决方案，您可能最终得到一个只提供解决方案的函数：

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);
        }
    }
}

然而，这样的代码可能会对函数式编程产生不良影响。根据对语言的支持，有些事情最好是迭代解决。更重要的是:函数编程并不意味着函数可能没有名称。可以从几个功能构建块创建一个与您最初建议的实现类似的实现，但它是纯功能的、紧凑的、可读性更强的：

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

多么有趣的挑战啊。学习Java8在我的名单上，所以我有一些建议，但请记住，我也在学习.

首先，让我们为我们拥有的函数使用函数。从安全功能开始：

私有静态布尔保险箱( Pos p，Pos q) {返回p.x != q.x & p.y != q.y &abs(P.X-q.x) != abs(P.Y-q.y)}；

出于稍后会变得清楚的原因，我想推翻这种逻辑，称之为“冲突”，这是不安全的。这方面的一个实用版本是：

// 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);

请注意，我选择使用实变量名称，而不是'a‘和'b’。我发现这对我有帮助，甚至在函数声明中也是如此。

好的，所以conflict是一个lambda表达式，在两个位置相对不安全的情况下返回true。

在我们讨论函数时，这里有一部分scala需要在Java中有一个匹配的概念：

产量((j，k) :：qs)

这是一个立场，并将其附加到先前的位置列表中.Java函数的等效值是：

// 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;
        };

好的，这里有两个助手函数。怎么才能使用呢？

NQueens问题的部分逻辑是采取一个部分解决方案(不是所有行)，对于下一行，确定哪些位置是安全的。对于所有的安全解决方案，“生产”作为一个新的部分解决方案的集合。

在您的代码中，qu函数中有这样的内容：

私有静态List> qu(int k，int n，List> qss) { List>结果=新ArrayList<>()；for(List qs : qss) { for(int j= 1；j <= n；j++) { Pos newPos =新Pos(j，k)；if (qs.stream().allMatch(pos -> safe(pos，newPos){ List partialResult =新ArrayList<>(qs)；partialResult.add(newPos)；result.add(partialResult)；}}返回结果；

qu函数也循环了所有的部分解，所以，我真正谈论的部分是在外部循环中.本部分：

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); } }

让它更加实用，我会有这样的东西：

// 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());
}

该函数(不是lambda)接受部分解决方案，它生成下一行中的所有位置，如果该位置没有冲突，它将添加一个新的(扩展的)部分解决方案，并将其输出。

到目前为止，qu方法的外部循环遍历部分解，然后“调用”内部部分。作为外部的一部分，并使它发挥作用，我想出了：

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

这意味着，以我们目前所有的部分解决方案为例，对于每个部分，生成一个更完整的列表。然后，将它们平面图到一个扩展的列表中，并收集它们。

现在，这种逻辑需要嵌入到左折叠操作中，而且您是对的，Java中不存在这样的逻辑。所以我造了一个。

左折叠接受两个输入，并返回与第一个输入相同类型的结果。要使它工作，我需要保持一个‘状态’，以便‘积累’的价值观。以下是我的实现：

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;
    }
}

一个类，它接受一个函数和一个初始状态。该函数用于将当前状态和新值转换为新状态。

考虑部分解的初始种子状态.这将是一个空的解决方案：

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

因此，如果我们有一个折叠函数，这需要一个新的行来求解，并且有一个已经解决的部分解的集合，我们可以有一个折叠函数，比如：

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

获取现有状态和要计算的行，并返回新状态。

完整的LeftFold实例是：

    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);

这是一个具有折叠功能的LeftFolder，还有一个初始种子。

使用该LeftFold，您可以使用以下方法创建实际的NQueen解决程序：

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

注意，上面的流在技术上是有副作用的文件夹，因为文件夹是有状态的。

以下是我对上述解决方案的完整代码。您应该能够复制/粘贴并运行它：

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());
    }

}