文章/答案/技术大牛

发布

社区首页 >问答首页 >Java:如何实现implement？

问Java:如何实现implement？
EN

Stack Overflow用户

提问于 2016-12-07 08:14:06

回答 1查看 947关注 0票数 2

我正在学习N-Queens，以便自己实现它，并发现了下面的实现规则：

N皇后之谜是在n×n棋盘上放置n个皇后的问题，这样就不会有两个皇后互相攻击。给定整数n，返回n皇后谜题的所有不同解。每个解决方案都包含一个独立的n皇后布局板配置，其中'Q‘和’‘。两者都分别表示一个女王和一个空空间。

例如，对于4皇后之谜有两种不同的解决方案：

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

以及实现(其思想是记住繁忙的列和对角线，并递归地尝试将皇后放到下一行中)：

public class Solution {

    private void helper(int r, boolean[] cols, boolean[] d1, boolean[] d2, 
                        String[] board, List<String[]> res) {
        if (r == board.length) res.add(board.clone()); //HERE
        else {
            for (int c = 0; c < board.length; c++) {
                int id1 = r - c + board.length, id2 = 2*board.length - r - c - 1;//HERE
                if (!cols[c] && !d1[id1] && !d2[id2]) {
                    char[] row = new char[board.length];
                    Arrays.fill(row, '.'); row[c] = 'Q';
                    board[r] = new String(row);
                    cols[c] = true; d1[id1] = true; d2[id2] = true;
                    helper(r+1, cols, d1, d2, board, res);
                    cols[c] = false; d1[id1] = false; d2[id2] = false;
                }
            }
        }
    }

    public List<String[]> solveNQueens(int n) {
        List<String[]> res = new ArrayList<>();
        helper(0, new boolean[n], new boolean[2*n], new boolean[2*n], 
            new String[n], res);
        return res;
    }
}

我的问题是(位于注释的位置://这里)，初始化的原因是什么，以及下面的方法是如何工作的：id1 = r - c + board.length, id2 = 2*board.length - r - c - 1; ( r、id1和id2代表什么？)，下面的意思是：if (r == board.length) res.add(board.clone());？举个例子会很有帮助。

事先谢谢，并将接受答复/投票。

编辑

如果输入n为4，则希望以以下形式System.out.print答案：

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

我怎样才能做到呢？

java

algorithm

n-queens

回答 1

Stack Overflow用户

回答已采纳

发布于 2016-12-07 08:41:25

牢记

这样做的目的是记住繁忙的列和对角线，并递归地尝试将女王放到下一行。

r是当前行，从0 (helper(0, ...))开始，在每个递归(helper(r+1, ...))中递增。

id1和id2是标识\和/对角线的数字。例如，主0,0-1,1-2,2-...-7,7上的\对角线字段都具有相同的id1 of 8。

cols、d1和d2正在追踪到目前为止，哪些栏目和对角线受到皇后区的威胁。如果您在0,0放置皇后，则cols[0] (第0列)、d1[8] (第8 \对角线)和d2[15] (第15 /对角线)都是true.

这是一个递归函数(调用自身)。为了使函数既是递归的，又不是无用的，它总是需要有两种不同的情况:基本情况(也称为终止情况)和一般情况(也称为递归情况)。第一个告诉你什么时候停止；第二个告诉你如何继续前进。第一个告诉您最简单的情况；第二个告诉您如何将复杂的情况分解为更简单的情况。

if (r == board.length) res.add(board.clone());是这里的终结案例。它说：“如果我们已经到达了过去的最后一行，这个板现在是一个解决方案；将它添加到结果列表中(而不是处理下一行，而下一行根本不存在)”。

使用clone可以添加当前板的快照，而不是对当前板本身的引用(否则，您将得到一堆对最后一块板的引用)。

编辑:对我来说，id1和id2的派生是一种直觉，所以我不确定我是否能解释它。只需对不同的字段进行计算，您就会看到它们都给出了从1到15的版面大小8的数字。下面是它们的样子(在JavaScript中，我可以在这里显示；单击蓝色的“运行代码片段”按钮)：

function drawTable(id, size, cb) {
  var $table = $('#' + id);
  var $tr = $('<tr>').appendTo($table);
  $('<th>').text(id).appendTo($tr);
  for (var c = 0; c < size; c++) {
    $('<th>').text(c).appendTo($tr);
  }
  for (var r = 0; r < size; r++) {
    var $tr = $('<tr>').appendTo($table);
    $('<th>').text(r).appendTo($tr);
    for (var c = 0; c < size; c++) {
      var n = cb(r, c, size);
      var $td = $('<td>').text(n).attr('data-d', n).appendTo($tr);
    }
  }
}

var size = 8
drawTable('id1', size, function(r, c, size) { return r - c + size; });
drawTable('id2', size, function(r, c, size) { return 2 * size - r - c - 1; });

th, td {
  text-align: center;
  border: 1px solid black;
  width: 2em;
}
table {
  border-collapse: collapse;
}
#id1 td[data-d="8"] {
  background-color: yellow;
}
#id2 td[data-d="15"] {
  background-color: yellow;
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<table id="id1"></table>
<br>
<table id="id2"></table>

黄色细胞显示8 id1和15 id2 -场0,0的对角线。您不需要检查行，因为程序只在每一行中放置一个皇后，然后继续到下一行。

票数 3

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/41012364

复制

相似问题

问Java:如何实现implement？
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Java:如何实现implement？EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Java:如何实现implement？
EN