I am making a program that is calculating the number of possible solutions of a chess game with only bishops and queens. The user can put in the maximal number of queens and bishops, as well as the size of the chess board.
I will call any set of positions for the bishops and the queens on the board a combination. A combination counts as a solution if all squares are attacked.
So for example, if the user wants to calculate the possible number of solutions with 2 queens and 1 bishop on a 3x3 chess board, two of the solutions could be:
B-- ---
-Q- -Q-
--- ---
And if the user chooses 9 queens instead of 2:
QQQ BQQ
QQQ QQQ
QQQ QQQ
I have managed to create an algorithm to check if a combination is a valid solution. The problem I got is the algorithm to find all the possible combinations there is. So what I need is an algorithm that loops through all possible combinations, and for each one check if the combination is a valid solution. I think a recursive solution would be the best for this.
There might be some smart way to solve this much faster, but I will sketch how to do a brute force using recursion. If you have a board with n squares in total, and your solution checking algorithm runs in F(n), this solution will be O(F(n)*3^n) - not very fast for larger boards in other words.
For a normal 8 by 8 chess board with many pieces this might be completely useless, since you run into the wheat and chessboard problem, only worse since your solution checker is expensive and it grows by the power of 3, not the power of 2. If you have fewer pieces, the problem is somewhat mitigated by the fact that you can stop branching once all the pieces are placed.
I will assume your solution checking function is named cheack_solution that takes a two dimensional array with the board, and returns a boolean (true if the board is a solution, otherwise 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;
}
I have not tried this, and my Java is a bit rusty, so don't expect this to run at the first try. You will need some debugging. I think the logic behind it should be allright, though.
EDIT: As requested in comments, I will try to explain why this works. You can imagine all possible board states as a tree. First there are three branches, one for each alternative (queen, bishop, empty) for the first square. Each of those three branches has three branches for the second square, and each of those three branches has three branches for the third square and so on.
The recursion traverse all these branches, since every time the function is called it calls itself three times. However the two if statements limits the traversion so that when the maximum number for a type of piece is reached, it does not try to place more of that piece.
So why do we need to put the "leave empty" option last of the three options? That is because all the function calls uses the same board array. It is not copied. Therefore when the function exit it must leave the board in the same state as it recieved it. Since there was nothing in square i when the function was called, there should be nothing in square i when the function returns.