1、什么是剪枝（Pruning）？
image.png
2、小技巧：从 0 开始的点坐标系，可以使用一维数组表示吗？（感觉是八皇后问题的小关键）
- 可以，数组的索引是 x，数组的值是 y
image.png
3、八皇后代码实现？
public class Queens {
public static void main(String[] args) {
// TODO Auto-generated method stub
new Queens().placeQueens(4);
}
/**
* 数组索引是行号，数组元素是列号
*/
int[] cols;
/**
* 一共有多少种摆法
*/
int ways;
void placeQueens(int n) {
if (n < 1) return;
cols = new int[n];
place(0);
System.out.println(n + "皇后一共有" + ways + "种摆法");
}
/**
* 从第row行开始摆放皇后
* @param row
*/
void place(int row) {
if (row == cols.length) {
ways++;
show();
return;
}
for (int col = 0; col < cols.length; col++) {
if (isValid(row, col)) {
// 在第row行第col列摆放皇后
cols[row] = col;
place(row + 1);
}
}
}
/**
* 判断第row行第col列是否可以摆放皇后
*/
boolean isValid(int row, int col) {
for (int i = 0; i < row; i++) {
// 第col列已经有皇后
if (cols[i] == col) {
return false;
}
// 第i行的皇后跟第row行第col列格子处在同一斜线上
if (row - i == Math.abs(col - cols[i])) {
return false;
}
}
return true;
}
void show() {
for (int row = 0; row < cols.length; row++) {
for (int col = 0; col < cols.length; col++) {
if (cols[row] == col) {
System.out.print("1 ");
} else {
System.out.print("0 ");
}
}
System.out.println();
}
System.out.println("------------------------------");
}
}
4、为什么会觉得八皇后中的 isValid 函数存在优化点？
- 因为 isValid 函数关心了过多的数据，记录了每一行皇后怎么办摆放。
- 如果一个函数关心的数据太多，那么就可能存在优化空间，优化的方向就是让它关心的数据
更聚集。 - 这个是优化思路的敏锐嗅觉
5、针对 isValid 优化思路？
image.png
public class Queens2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
new Queens2().placeQueens(4);
}
/**
* 数组索引是行号，数组元素是列号
*/
int[] queens;
/**
* 标记着某一列是否有皇后
*/
boolean[] cols;
/**
* 标记着某一斜线上是否有皇后（左上角 -> 右下角）
*/
boolean[] leftTop;
/**
* 标记着某一斜线上是否有皇后（右上角 -> 左下角）
*/
boolean[] rightTop;
/**
* 一共有多少种摆法
*/
int ways;
void placeQueens(int n) {
if (n < 1) return;
queens = new int[n];
cols = new boolean[n];
leftTop = new boolean[(n << 1) - 1];
rightTop = new boolean[leftTop.length];
place(0);
System.out.println(n + "皇后一共有" + ways + "种摆法");
}
/**
* 从第row行开始摆放皇后
* @param row
*/
void place(int row) {
if (row == cols.length) {
ways++;
show();
return;
}
for (int col = 0; col < cols.length; col++) {
if (cols[col]) continue;
int ltIndex = row - col + cols.length - 1;
if (leftTop[ltIndex]) continue;
int rtIndex = row +col;
if (rightTop[rtIndex]) continue;
queens[row] = col;
cols[col] = true;
leftTop[ltIndex] = true;
rightTop[rtIndex] = true;
place(row + 1);
cols[col] = false;
leftTop[ltIndex] = false;
rightTop[rtIndex] = false;
}
}
void show() {
for (int row = 0; row < cols.length; row++) {
for (int col = 0; col < cols.length; col++) {
if (queens[row] == col) {
System.out.print("1 ");
} else {
System.out.print("0 ");
}
}
System.out.println();
}
System.out.println("------------------------------");
}
}
6、看到上述代码中存在 boolean 类型的数组，敏感的人觉得可以如何优化？
- 可以用位运算优化，把数组转换成数据的每一个二进制位。
public class Queens3 {
public static void main(String[] args) {
// 01111101 n
//&11111011 ~00000100
// 01111001
//&00100000 v
// int n = 125;
// for (int i = 0; i < 8; i++) {
// int result = n & (1 << i);
// System.out.println(i + "_" + (result != 0));
// }
// int col = 7;
// int result = n & (1 << col);
// System.out.println(result != 0);
// System.out.println(Integer.toBinaryString(n));
// TODO Auto-generated method stub
new Queens3().place8Queens();
}
/**
* 数组索引是行号，数组元素是列号
*/
int[] queens;
/**
* 标记着某一列是否有皇后
*/
byte cols;
/**
* 标记着某一斜线上是否有皇后（左上角 -> 右下角）
*/
short leftTop;
/**
* 标记着某一斜线上是否有皇后（右上角 -> 左下角）
*/
short rightTop;
/**
* 一共有多少种摆法
*/
int ways;
void place8Queens() {
queens = new int[8];
place(0);
System.out.println("8皇后一共有" + ways + "种摆法");
}
/**
* 从第row行开始摆放皇后
* @param row
*/
void place(int row) {
if (row == 8) {
ways++;
show();
return;
}
for (int col = 0; col < 8; col++) {
int cv = 1 << col;
if ((cols & cv) != 0) continue;
int lv = 1 << (row - col + 7);
if ((leftTop & lv) != 0) continue;
int rv = 1 << (row + col);
if ((rightTop & rv) != 0) continue;
queens[row] = col;
cols |= cv;
leftTop |= lv;
rightTop |= rv;
place(row + 1);
cols &= ~cv;
leftTop &= ~lv;
rightTop &= ~rv;
}
}
void show() {
for (int row = 0; row < 8; row++) {
for (int col = 0; col < 8; col++) {
if (queens[row] == col) {
System.out.print("1 ");
} else {
System.out.print("0 ");
}
}
System.out.println();
}
System.out.println("------------------------------");
}
}
7、作业
image.png
