Eight Queens

作者 QIFAN 日期 2016-10-01
Eight Queens

Write an algorithm to print all ways of arranging eight queens on an 8x8 chess board so that none of them share the same row, column, or diagonal. In this case, “diagonal” means all diagonals, not just the two that bisect the board.

思路

简单粗暴的方法是一层一层的放皇后,每一次都check是否valid。

解题

int GRID_SIZE = 8;
public void placeQueens(int row, Integer[] columns, ArrayList<Integer[]> results) {
if (row == GRID_SIZE) {
results.add(columns.clone());
} else {
for (int col = 0; col < GRID_SIZE; col++) {
if (checkValid(columns, row, col)) {
columns[row] = col;
placeQueens(row + 1, columns, results);
}
}
}
}
public boolean checkValid(Integer[] columns, int row1, int column1) {
for (int row2 = 0; row 2 < row 1; row2++) {
int column2 = columns[row2];
if (column1 == column2) {
return false;
}
int columnDistance = Math.abs(column2 - column1);
int rowDistance = row1 - row2;
if (columnDistace == columnDistance) {
return false;
}
}
return true;
}