每个NxN棋盘的最大主教数，我如何才能找到所有解决方案而不是一个

Question

我创建了一个算法，该算法将在NxN棋盘上放置最大数量的主教，但仅适用于1个解决方案。有没有可能升级这个算法，让它向我展示所有可能的解决方案？该算法的工作方式是对矩阵的对角线进行索引，并将其索引存储在HashSet中，如果当前索引不在HashSet的中，则bishop将被放置在该字段中。

索引对角线：

• 从左到右=I-J
• 从右到左=I+J

代码：

public static void maxBishop() {
HashSet<Integer> leftToRight = new HashSet<>();
HashSet<Integer> rightToLeft = new HashSet<>();
int[][] matrix = {
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};

for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
if (!rightToLeft.contains(i + j) && !leftToRight.contains(i - j)) {
matrix[i][j] = 1;
rightToLeft.add(i + j);
leftToRight.add(i - j);
}
}
}

}

Answer 1

HashSet在这方面做得太过火了。只需使用布尔值[]，因为索引是已知的。例如，对于i+j，rightToLeft[i+j]=true。对于负数，数组仍然使用固定偏移9，leftToRight[9+i-j]=true。主循环中不再有HashSet或方法调用。

至于一般的算法，您可以使用递归。你必须考虑，如果我不把第一个主教放在0,0怎么办？基本上，一旦你找到了一个解决方案，你就需要放弃上一个位置，并检查主教是否也适合这个位置(然后重复(。一旦你用尽了最后一个职位的所有可能性，那么就备份并尝试倒数第二个职位的不同可能性，等等。记住最大主教人数的董事会状态，并放弃任何低于你当前最大人数的董事局状态。

public class MaxBishop {
private static final int DIM = 10;
private static final int DIM_M_1 = DIM-1;
private static final int DIM_SQ = DIM*DIM;
static boolean[] leftToRight = new boolean[2*DIM];
static boolean[] rightToLeft = new boolean[2*DIM];
static boolean[] matrix = new boolean[DIM_SQ];
static int maxBishops = 0;
public static void main(String[] args) {
maxBishop(0,0);
}
public static void maxBishop(int start, int numPlaced) {
for (int p = start; p < DIM_SQ; p++) {
int i = p / DIM;
int j = p - i * DIM;
if (!rightToLeft[i + j] && !leftToRight[DIM_M_1 + i - j]) {
place(i,j);
maxBishop(p+1, numPlaced+1);
remove(i,j);
}
}
if (numPlaced >= maxBishops) {
maxBishops = numPlaced;
printBoard(matrix, numPlaced);
}
}
static void place(int i, int j) {
matrix[i*DIM+j] = true;
rightToLeft[i + j] = true;
leftToRight[DIM_M_1 + i - j] = true;
}
static void remove(int i, int j) {
matrix[i*DIM+j] = false;
rightToLeft[i + j] = false;
leftToRight[DIM_M_1 + i - j] = false;
}

static void printBoard(boolean[] matrix, int bishops) {
System.out.println("n"+bishops+" bishops:");
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
System.out.print(matrix[i*DIM+j] ? 'B' : '.');
}
System.out.println();
}
}
}

请注意，您必须考虑已找到的解决方案的镜像和旋转版本。