I have a problem: Given a chess-board n*n (the user inputs n). In the chess -board there are k black queens and k white queens (requirement: 2 queens with different color cannot beat each other. We don't care about 2 queens with the same color). Find k max? PHP: #include <iostream>using namespace std;struct Square{ char Queen; int BlackEnemies; int WhiteEnemies;};void AllocBoard(Square ** & board, int & n);void DelBoard(Square ** & board, int n);void ShowBoard(Square ** board, int n); void AddEnemies(Square ** & board, int n, char chess_piece, int row, int column);void ReduceEnemies(Square ** & board, int n, char chess_piece, int row, int column);int ArrangeQueen(Square ** & board, int n, int black, int white);void Release(Square ** & board, int n, int black, int white, int max);int main(){ Square ** board; int n, max; AllocBoard(board, n); max = ArrangeQueen(board, n, 0, 0); cout << "kmax is: " << max; cout << endl; Release(board, n, 0, 0, max); DelBoard(board, n); return 0;}void AllocBoard(Square ** & board, int & n){ cout << "Enter the size of the chess-board: "; cin >> n; // Allocate board = new Square * [n]; for (int i = 0; i < n; ++i) { board[i] = new Square [n]; } // Initialize for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { board[i][j].Queen = '*'; board[i][j].WhiteEnemies = 0; board[i][j].BlackEnemies = 0; } }}void DelBoard(Square ** & board, int n){ for (int i = 0; i < n; ++i) { delete [] board[i]; } delete [] board;}void ShowBoard(Square ** board, int n){ for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { cout << board[i][j].Queen << " "; } cout << endl; }}void AddEnemies(Square ** & board, int n, char chess_piece, int row, int column){ for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (row == i || column == j || row - column == i - j || row + column == i + j) { if ('W' == chess_piece) { ++board[i][j].WhiteEnemies; } else { ++board[i][j].BlackEnemies; } } } }}void ReduceEnemies(Square ** & board, int n, char chess_piece, int row, int column){ for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (row == i || column == j || row - column == i - j || row + column == i + j) { if ('W' == chess_piece) { --board[i][j].WhiteEnemies; } else { --board[i][j].BlackEnemies; } } } }}int ArrangeQueen(Square ** & board, int n, int black, int white){ static int max = 0; if (black == white && max < black) { max = black; } else { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (0 == board[i][j].WhiteEnemies && '*' == board[i][j].Queen) { board[i][j].Queen = 'B'; AddEnemies(board, n, 'B', i, j); ArrangeQueen(board, n, black + 1, white); ReduceEnemies(board, n, 'B', i, j); board[i][j].Queen = '*'; } if (0 == board[i][j].BlackEnemies && '*' == board[i][j].Queen) { board[i][j].Queen = 'W'; AddEnemies(board, n, 'W', i, j); ArrangeQueen(board, n, black, white + 1); ReduceEnemies(board, n, 'W', i, j); board[i][j].Queen = '*'; } } } } return max;}void Release(Square ** & board, int n, int black, int white, int max){ if (black == white && max == white) { cout << endl; ShowBoard(board, n); cout << endl; } else { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (0 == board[i][j].WhiteEnemies && '*' == board[i][j].Queen) { board[i][j].Queen = 'B'; AddEnemies(board, n, 'B', i, j); ArrangeQueen(board, n, black + 1, white); ReduceEnemies(board, n, 'B', i, j); board[i][j].Queen = '*'; } if (0 == board[i][j].BlackEnemies && '*' == board[i][j].Queen) { board[i][j].Queen = 'W'; AddEnemies(board, n, 'W', i, j); ArrangeQueen(board, n, black, white + 1); ReduceEnemies(board, n, 'W', i, j); board[i][j].Queen = '*'; } } } }} Is this ok?
I have changed the code, but I still cannot display it?? PHP: #include <iostream>using namespace std;struct Square{ char Queen; int BlackEnemies; int WhiteEnemies;};void AllocBoard(Square ** & board, int & n);void DelBoard(Square ** & board, int n);void ShowBoard(Square ** board, int n); void AddEnemies(Square ** & board, int n, char chess_piece, int row, int column);void ReduceEnemies(Square ** & board, int n, char chess_piece, int row, int column);int ArrangeQueen(int Next,Square ** & board, int n, int black, int white);int main(){ Square ** board; int n, max; AllocBoard(board, n); max = ArrangeQueen(0, board, n, 0, 0); cout << "kmax is " << max; cout << endl; DelBoard(board, n); return 0;}void AllocBoard(Square ** & board, int & n){ cout << "Enter the size of the chess-board: "; cin >> n; // Allocate board = new Square * [n]; for (int i = 0; i < n; ++i) { board[i] = new Square [n]; } // Initialize for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { board[i][j].Queen = '*'; board[i][j].WhiteEnemies = 0; board[i][j].BlackEnemies = 0; } }}void DelBoard(Square ** & board, int n){ for (int i = 0; i < n; ++i) { delete [] board[i]; } delete [] board;}void ShowBoard(Square ** board, int n){ for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { cout << board[i][j].Queen << " "; } cout << endl; }}void AddEnemies(Square ** & board, int n, char chess_piece, int row, int column){ for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (row == i || column == j || row - column == i - j || row + column == i + j) { if ('W' == chess_piece) { ++board[i][j].WhiteEnemies; } else { ++board[i][j].BlackEnemies; } } } }}void ReduceEnemies(Square ** & board, int n, char chess_piece, int row, int column){ for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (row == i || column == j || row - column == i - j || row + column == i + j) { if ('W' == chess_piece) { --board[i][j].WhiteEnemies; } else { --board[i][j].BlackEnemies; } } } }}int ArrangeQueen(int Next,Square ** & board, int n, int black, int white){ static int max = 0; if (black == white && max < black) { max = black; } else { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (Next %2 == 0 && 0 == board[i][j].WhiteEnemies && '*' == board[i][j].Queen) { board[i][j].Queen = 'B'; AddEnemies(board, n, 'B', i, j); ArrangeQueen(Next+1,board, n, black + 1, white); ReduceEnemies(board, n, 'B', i, j); board[i][j].Queen = '*'; } else if (Next %2 == 1 && 0 == board[i][j].BlackEnemies && '*' == board[i][j].Queen) { board[i][j].Queen = 'W'; AddEnemies(board, n, 'W', i, j); ArrangeQueen(Next+1,board, n, black, white + 1); ReduceEnemies(board, n, 'W', i, j); board[i][j].Queen = '*'; } } } } return max;}
> Is this ok? Presumably not, because otherwise you wouldn't be posting here. What exactly does the program not do that you want it to, in specific terms? What input do you give and what output did you get, and what output did you expect?
I not only want to find kmax but also I want to display the chess-board. I run the program for n = 5 but if n> 5, it'll take too much time. Some of my friend can run up to n = 12!!!
Sorry I have not made the description! Outline: 1. A square in the chess-board has 3 properties: the queen in it, can be attacked by how many black queen and how may white ones. 2. We put the black queens and white queens consecutively by using a variable Next to control (if Next is divisible by 2, black goes; else white goes) 3. If the number of white queens equal to the number of black queens and that number is greater than max (max is first assigned as 0) then max is that number.
Maybe my problem is not too difficult for many programmers, but to me it is challenging. I have tried ShowBoard function in the function Release (just imitate the Arrange function but put an if (white == black && black == max) then ShowBoard, but this did not work so I did not use it. Can you suggest me some solutions for this?
This doesn't make sense. If you've written all the above code then determining where to put a ShowBoard call should be trivial. Have you written it or have you got it all from other people suggesting you some solutions? But I can't suggest where to put the call to ShowBoard simply because I do not know where you want to put that call. Only you know where you want the board to be shown. Also I'm not sure what you expect would be shown, because after ArrangeQueen has returned, it looks like the board will be full of asterisks (*). Do you want to see 64 asterisks or something else?
I have tried this problem for a week. It would be trivial to show the board of course but I am too tired after doing this as I am a beginner. Let me check what you have pointed out. However, I am quite sure that the algorithm to find max is correct! Thanks for your help.