java - 斜查n皇后JAVA

Question

我在理解网上获得的代码时遇到了问题。这是皇后检查是否与其他皇后发生碰撞。有人可以向我解释一下这是做什么的吗？第一个条件，我知道是检查同一行，但是绝对数呢？

if ((board[i] == board[row]) || Math.abs(board[row] - board[i]) == (row - i)) 
{
     return false;
}

完整代码如下:

class NQueen {

private int[] board;
private int size;
private ArrayList allSolutions = null;

public int[] getBoard() {
    return board;
}
public ArrayList getAllSolutions() {
    return this.allSolutions;
}
public NQueen(int size) {
    this.size = size;
    board = new int[this.size];
    this.allSolutions = new ArrayList();
}
public void place(int row) {
            // base case
    if (row == size) {
        int[] temp = new int[size];
                    // copy in temp array
        System.arraycopy(board, 0, temp, 0, size);
                    // add to the list of solution
        allSolutions.add(new Solution(temp));
        return ;
    } else {
        for (int i = 0; i < size; i++) {

            board[row] = i;
                            /* when you place a new queen
                             * check if the row you add it in, isn't 
                             * already in the array. since the value of arrray is
                             * the row, so we only need to check the diagonals no need to check for collisions on the left or right. 
                             * As long as there is no duplicate values in the array.*/
            if (valid(row)){
                               place(row + 1);
                            }

        }
    }
}
public boolean valid(int row) {
    for (int i = 0; i < row; i++) {
                    // if same row  or same diagonal
        if ((board[i] == board[row]) || Math.abs(board[row] - board[i]) == (row - i)) 
                    {
                        return false;
        }
    }
    return true;
}

}

Answer 1

如果你有一个二维数组，并且棋盘上的每个位置都是数组中的“单元格”，那么为了处于同一对角线上，棋子必须具有相同的水平和垂直距离。

Math.abs(board[row] - board[i]) == (row - i)

确实检查了这一点。 Math.abs 是因为第二 block 可以是左上、右上、右下和左下。不确定您的算法到底是如何实现的，但也采用第二个操作数的绝对值可能是个好主意。

小板示例:

  1 2 3 4
1
2 x
3
4     y

所以这里我们的水平距离为 2 (abs(1-3))，垂直距离也为 2 (abs(2-4))

示例2:

  1 2 3 4
1       x
2     y
3 
4 

这里我们的水平和垂直距离只有1(abs(4-3)和abs(1-2))

跟进

您的数组在每个元素中存储皇后在该行中的位置。所以它只是一个一维数组(不是我最初建议的二维数组)。

因此，对于我的第一个示例，您的数组将包含:

[ 0, 1, 0, 3 ]

(我认为OP中的代码假设从0开始的位置，但用0(new int[size])初始化数组元素。这可能是一个 bug，因为 0 是有效位置，可能与其他约束冲突，即，如果上一行或下一行的皇后未初始化(=位置 0)，则您将无法在索引 1 上放置皇后.)

回到示例(为了清晰起见，使用基于 1 的索引并避免上述错误):a[2] - a[4] == 1 - 3 (a [2] == 1，a[4] == 3)

如果“y” block 被移动到第 2 列，那么您将得到 a[2] - a[4] != 1 - 3，因为它们不共享对角线 ( a[2] == 1，a[4] == 3)