java查找棋类游戏的所有组合

Question

我正在制作一个程序，计算一个只有主教和皇后的国际象棋游戏可能解的数目。用户可以输入皇后和主教的最大数量，以及棋盘的大小

我将把董事会中主教和皇后的任何职位称为组合。如果所有方块都受到攻击，则组合算作解

例如，如果用户想要计算3x3棋盘上2个皇后和1个主教的可能解数，其中两个解可以是：

B--   ---
-Q-   -Q-
---   ---

如果用户选择9个皇后而不是2个：

QQQ   BQQ
QQQ   QQQ
QQQ   QQQ

我已经设法创建了一个算法来检查组合是否是有效的解决方案。我遇到的问题是找到所有可能组合的算法。所以我需要的是一个算法，它循环遍历所有可能的组合，并检查每个组合是否是有效的解决方案。我认为递归解决方案是最好的

Answer 1

也许有一些聪明的方法可以更快地解决这个问题，但我将简要介绍如何使用递归实现蛮力。如果你的电路板上总共有n个方块，并且你的解决方案检查算法在F(n)中运行，那么这个解决方案将是O(F(n)*3^n)——换言之，对于较大的电路板来说不是很快

对于一个有很多棋子的8乘8的棋盘来说，这可能是完全没有用的，因为你遇到了wheat and chessboard problem，更糟糕的是，你的解决方案检查器很昂贵，而且它是以3的幂增长的，而不是2的幂增长的。如果你有更少的片段，那么问题会有所缓解，因为一旦所有片段都被放置好，你就可以停止分支

我将假设您的解决方案检查函数名为cheack_solution，它与电路板一起接受一个二维数组，并返回一个布尔值（true如果电路板是解决方案，否则false）

//Just to start it off.
int count_solutions(max_queens, max_bishops, a, b) {
    int[][] board= new int[a][b];
    return recurse(board, 0, a*b, max_queens, max_bishops, 0, 0);
}

//This is where the actual work is done.
//board is the board so far, represented by a two dimensional array where
//   -1 = Queen
//    0 = Empty
//    1 = Bishop
//i is the square we are currently on, and n is the total number of board.
//max_queens and max_bishops are the maximum allowed to place.
//queens and bishops are the number placed so far.
int recurse(board, i, n, max_queens, max_bishops, queens, bishops) {
    if(i == n || (max_queens == queens && max_bishops == bishops)) {
        //If we have placed all the pieces, it is time to check if it is a solution.
        //Return one if it is, otherwise zero.
        return (int) sheck_solution(board);
    }
    //We havent placed all the pieces yet. Time to do some recursion.
    //Get the two dimensional x and y coordinates for the one dimensional coordinate i.
    x = i / board.length;
    y = i % board.length);
    //Number of solutions = the sum of number of solutions for the alternatives.
    int solutions = 0;
    //Place a queen in the current spot.
    if(queens < max_queens) {
        board[x][y] = -1;
        solutions += recurse(board, i+1, n, max_queens, max_bishops, queens + 1, bishops);
    }
    //Place a bishop in the current spot.
    if(bishops < max_bishops) {
        board[x][y] = 1;
        solutions += recurse(board, i+1, n, max_queens, max_bishops, queens, bishops + 1);
    }
    //Place nothing in the current spot.
    board[x][y] = 0;
    solutions += recurse(board, i+1, n, max_queens, max_bishops, queens, bishops);
    return solutions;
}

我还没有尝试过这个，而且我的Java有点生疏，所以不要指望第一次尝试就能运行这个。你需要一些调试。不过，我认为背后的逻辑应该是正确的

编辑：根据评论中的要求，我将尝试解释为什么这样做有效。你可以把所有可能的董事会状态想象成一棵树。首先，第一个广场有三个分支，每个分支一个（女王、主教、空的）。这三个分支中的每一个都有三个分支用于第二个广场，这三个分支中的每一个都有三个分支用于第三个广场，依此类推

递归遍历所有这些分支，因为每次调用函数时，它都会调用自己三次。然而，这两个if语句限制了遍历，因此当一种类型的工件达到最大数量时，它不会尝试放置更多的工件

那么，为什么我们需要把“留空”选项放在三个选项中的最后一个呢？这是因为所有函数调用都使用相同的board数组。它不是复制的。因此，当函数退出时，它必须使电路板保持与接收它时相同的状态。因为调用函数时，squarei中没有任何内容，所以当函数返回时，squarei中应该没有内容