找到国际象棋游戏的所有组合
Find all combinations of Chess game
我正在编写一个程序,用于计算只有主教和皇后的国际象棋游戏的可能解决方案的数量。用户可以输入皇后和象的最大数量,以及棋盘的大小。
我将棋盘上象和皇后的任何一组位置称为组合。如果所有方格都被攻击,则组合算作解决方案。
因此,例如,如果用户想要计算在 3x3 棋盘上有 2 个皇后和 1 个主教的可能解决方案的数量,其中两个解决方案可以是:
B-- ---
-Q- -Q-
--- ---
如果用户选择 9 个皇后而不是 2 个:
QQQ BQQ
QQQ QQQ
QQQ QQQ
我已经设法创建了一种算法来检查组合是否是有效的解决方案。我遇到的问题是找到所有可能组合的算法。所以我需要的是一种算法,它遍历所有可能的组合,并针对每个组合检查组合是否是有效的解决方案。我认为递归解决方案是最好的。
可能有一些聪明的方法可以更快地解决这个问题,但我将概述如何使用递归进行暴力破解。如果您的电路板总共有 n
个正方形,并且您的解决方案检查算法 F(n)
中的 运行s,则此解决方案将为 O(F(n)*3^n)
- 对于较大的电路板来说速度不是很快换句话说。
对于一个有很多棋子的普通 8 x 8 棋盘,这可能完全没用,因为您 运行 进入了 wheat and chessboard problem,更糟的是因为您的解决方案检查器很昂贵并且它增长了3 的次方,而不是 2 的次方。如果您的棋子较少,那么问题会有所缓解,因为您可以在所有棋子都放置好后停止分支。
我假设你的解决方案检查函数被命名为 cheack_solution
,它采用带有电路板的二维数组,returns 一个布尔值(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 语句限制了遍历,因此当达到一种类型的最大数量时,它不会尝试放置更多的那种。
那么为什么我们需要将 "leave empty" 选项放在三个选项的最后?这是因为所有函数调用都使用相同的 board
数组。它没有被复制。因此,当函数退出时,它必须使板保持与接收时相同的状态。由于函数调用时i
中没有任何内容,所以函数returns.
i
中应该没有内容