8 位主教占据整个棋盘 [回溯]

Question

我有一个任务是编写一个程序，在棋盘中设置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();
}
}

问题是，目前我的程序将主教放在第一列，而这种布局并没有占据全部 space。当然，我可以简单地将所有内容放在第三列，问题就解决了。但是，我必须使用回溯并且不知道如何使用。如果您有任何想法或提示，我将非常高兴听到。

Answer 1

你应该这样做：

public boolean placeBishops (int bishop){
    if(bishop == 8){
        if(allSpaceOccupied()){
            //Print the board here, i.e found the solution
            //also check the indexing of the bishop,
            //i have assumed that they start from 0
            return true;
        }else{
            return false;
        }
    }
    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;
            boolean found = placeBishops(bishop+1);
            if(found == true) return true;
            solution[row][bishop] = 0;
        }
    }
    return false;
}

我们可以检查一个地方是否适合特定的主教，并相应地增加主教的数量，如果我们没有找到沿着这条路走下去的解决方案，我们会重置当前的 solution array主教索引和该主教的相应行，以便我们可以寻找另一种可能的解决方案。

Answer 2

您的解决方案假定所有象都必须放在不同的行中。并非所有解决方案都是如此。（有一个解决方案，其中所有主教都在第三列或第四列。您不是在寻找所有的解决方案，但如果您是，那么根据这个假设，您会错过很多解决方案。）

你也不需要canPlace检查：没有主教不能互相威胁的限制。（这可能是一种加快搜索速度的有效技术，但同样，当您应用它时，您会错过一些解决方案。如果您想使用它，则无需检查所有对角线单元格中已放置的主教；它足以检查当前单元格是否已被标记为 "occupied" 或被威胁。）

如果您要使用带回溯的蛮力方法，您可以测试所有可能的主教组合。那是 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);

8 位主教占据整个棋盘 [回溯]

8 Bishops to occupy whole board [Backtracking]

java

algorithm

backtracking