java - 8位主教占据整个董事会[回溯]

我有一个任务要编写一个程序，该程序在棋盘上设置8个主教，占据整个棋盘。它应该在找到第一个解决方案时结束并打印出所有内容。这是我用Java编写的代码，我努力使用回溯来完成它(该位置在代码中已注释)。

/*
 * 0 - not occupied square
 * 1 - bishop standing square
 * 2 - occupied square (diagonal)
 */
public class BishopsBT {
public int [][] solution;
final int N = 8; // number of squares in column and row (chess board)
final int solved = 120; //Sum of 1's and 2's in case of all occupied board
int sum; //current sum of board

public BishopsBT(){
    solution = new int [N][N] ;
}

public void solve() {
    if(placeBishops(0)){
        //print the result
        clear(); // clears all 2's
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(" " + solution[i][j]);
            }
            System.out.println();
        }
    } else{
        System.out.println("NO SOLUTION EXISTS");
    }
}

public boolean placeBishops (int bishop){

    for (int row = 0; row < N; row++) {
        // check if bishop can be placed
        if (canPlace(solution, row, bishop)) {
            // place the bishop
            solution[row][bishop] = 1;
            }
        }

    if (allSpaceOccupied()) {
        return true;
    } else {
        // SOME BACKTRACKING CODE HERE
        return false;
    }

    }

// check if bishop can be placed at matrix[row][column]
public boolean canPlace(int[][] matrix, int row, int column) {

    // we need to check all diagonals
    // whether no bishop is standing there

    for (int i = row, j = column; i >= 0 && j >= 0; i--, j--) {
        if (matrix[i][j] == 1) {
            return false;
        }
    }

    for (int i = row, j = column; i >= 0 && j < matrix.length; i--, j++) {
        if (matrix[i][j] == 1) {
            return false;
        }
    }

    for (int i = row, j = column; i < matrix.length && j >= 0; i++, j--) {
        if (matrix[i][j] == 1) {
            return false;
        }
    }

    for (int i = row, j = column; i < matrix.length && j < matrix.length; i++, j++) {
        if (matrix[i][j] == 1) {
            return false;
        }
    }
    // if we are here that means we are safe to place Bishop
    return true;
}

public boolean allSpaceOccupied() {

    // clears previously occupied space
    clear();

    // occupies new space
    for (int i = 0; i < solution.length; i++) {
        for ( int j = 0; j < solution.length; j++) {
    if (solution[i][j] == 1) diagonalOccupy(i,j);
        }
    }
    sum = 0;
    // counts sum of occupied space
    for (int i = 0; i < solution.length; i++) {
        for ( int j = 0; j < solution.length; j++) {
    sum += solution [i][j];
        }
    }

    if (sum == solved) return true;
    // else
    return false;
}

public void diagonalOccupy(int row, int column) {
    // writes 2 in each bishop's occupied square
    for (int i = row, j = column; i >= 0 && j >= 0; i--, j--) {
        if (solution[i][j] == 0) {
            solution[i][j] = 2;
        }
    }

    for (int i = row, j = column; i >= 0 && j < solution.length; i--, j++) {
        if (solution[i][j] == 0) {
            solution[i][j] = 2;
        }
    }

    for (int i = row, j = column; i < solution.length && j >= 0; i++, j--) {
        if (solution[i][j] == 0) {
            solution[i][j] = 2;
        }
    }

    for (int i = row, j = column; i < solution.length && j < solution.length; i++, j++) {
        if (solution[i][j] == 0) {
            solution[i][j] = 2;
        }
    }

}
 // clears all 2's on the board
public void clear() {
    for (int i = 0; i < solution.length; i++) {
        for ( int j = 0; j < solution.length; j++) {
            if (solution[i][j] == 2) solution[i][j] = 0;
        }
    }
}

public static void main(String[] args) {
    BishopsBT q = new BishopsBT();
    q.solve();
}
}

问题是，目前我的程序将主教放在第一栏中，并且这种布局并未占据所有空间。当然，我可以将所有内容都放在第三栏中，问题就可以解决。但是，我必须使用回溯并且不知道如何。如果您有任何想法或技巧，我将非常高兴听到他们的声音。

最佳答案

您的解决方案假定所有主教必须放在不同的行中。并非所有解决方案都是如此。 (有一个解决方案，所有主教都在第三或第四栏中。您并不是在寻找所有解决方案，但是如果您要寻找所有解决方案，那么基于此假设，您将错过许多解决方案。)

您也不需要canPlace检查:没有任何限制，主教不能互相威胁。 (这可能是一种有效的搜索方法，可以加快搜索速度，但是同样，应用搜索时，您会漏掉一些解决方案。如果要使用它，则无需检查所有对角单元是否已放置主教；它会足以检查当前单元格是否被标记为“已占用”或受到威胁。)

如果要在回溯中使用暴力破解方法，则可以测试主教的所有可能组合。那是C(64，8)或4,426,165,368组合。

您可以大幅度降低可能性，但不能假设主教必须排在不同的行中。相反，请注意您的解决方案由两个独立的解决方案组成。白色正方形上的主教只能威胁白色正方形，而黑色正方形上的主教只能威胁黑色正方形。因此，找到一种解决方案，将四位主教放在董事会上，这些主教威胁着所有白色正方形。然后

(如果要查找所有解决方案，请找到所有k个子解决方案并将其组合为k²个完整解决方案。)

案例之间的分离减少了测试C(32，8)或35,960的可能安排。您只考虑每行有一位主教的配置的策略会检查8 ^ 8(约1600万)种可能性。它错过了一些解决方案，并检查了猛烈的配置，其中没有四个主教在白色正方形上，没有四个主教在黑色正方形上。

在另一个答案中给出了回溯的原理。如果您这样标记32个白色方块:

01  02  03  04
  05  06  07  08
09  10  11  12
  13  14  15  16
17  18  19  20
  21  22  23  24
25  26  27  28
  29  30  31  32

您可以使用这种递归方法(在伪Java中):

bool place(int i, int start) {
    if (i == 8) {
        if (allOccupied()) {
           print();
           return true;
        }
    } else {
        for (int j = start, j < 32; j++) {
            int row = j / 4;
            int col = 2 * (j % 4) + row % 2;

            // add bishop at (col, row)
            // save occupancy matrix
            // add threat by (col, row) to matrix

            if (place(i + 1, j + 1)) return true;

            // revert matrix to saved matrix
            // remove bishop from (col, row)
       }
    }

    return false;
}

然后开始

place(0, 0);