对角查第n个皇后JAVA
Diagonally check the n queen JAVA
我在理解在线代码方面遇到了问题。如果与其他皇后发生碰撞,这是对皇后的检查。有人可以向我解释这是做什么的吗?第一个条件,我知道是检查同一行,但是绝对数呢?
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;
}
}
如果你有一个二维数组,棋盘上的每个位置 "cell" 在数组中,那么要在同一条对角线上,一块必须具有相同的水平和垂直距离。
Math.abs(board[row] - board[i]) == (row - i)
检查准确。 Math.abs
是因为第二块可以是左上角、右上角、右下角和左下角。不确定您的算法是如何实现的,但也可以采用第二个操作数的绝对值。
小板示例:
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]
)初始化数组元素。这可能是一个错误,因为 0 是一个有效位置并且可能与其他约束冲突,即如果上一行或下一行的皇后未初始化(=位置 0),您将无法将皇后放在索引 1 上。)
回到示例(为清楚起见使用基于 1 的索引并避免上述错误):a[2] - a[4] == 1 - 3
(a[2] == 1
, a[4] == 3
)
如果 "y" 块被移动到第 2 列,那么你会得到 a[2] - a[4] != 1 - 3
,因为它们不共享对角线(a[2] == 1
,a[4] == 3
)
我在理解在线代码方面遇到了问题。如果与其他皇后发生碰撞,这是对皇后的检查。有人可以向我解释这是做什么的吗?第一个条件,我知道是检查同一行,但是绝对数呢?
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;
}
}
如果你有一个二维数组,棋盘上的每个位置 "cell" 在数组中,那么要在同一条对角线上,一块必须具有相同的水平和垂直距离。
Math.abs(board[row] - board[i]) == (row - i)
检查准确。 Math.abs
是因为第二块可以是左上角、右上角、右下角和左下角。不确定您的算法是如何实现的,但也可以采用第二个操作数的绝对值。
小板示例:
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]
)初始化数组元素。这可能是一个错误,因为 0 是一个有效位置并且可能与其他约束冲突,即如果上一行或下一行的皇后未初始化(=位置 0),您将无法将皇后放在索引 1 上。)
回到示例(为清楚起见使用基于 1 的索引并避免上述错误):a[2] - a[4] == 1 - 3
(a[2] == 1
, a[4] == 3
)
如果 "y" 块被移动到第 2 列,那么你会得到 a[2] - a[4] != 1 - 3
,因为它们不共享对角线(a[2] == 1
,a[4] == 3
)