k black and k white

thxthn's Avatar, Join Date: May 2009
Light Poster
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 Code:
#include <iostream>

using namespace std;

struct Square
{
    
char Queen;
    
int BlackEnemies;
    
int WhiteEnemies;
};

void AllocBoard(Square ** & boardint n);

void DelBoard(Square ** & boardint n);

void ShowBoard(Square ** boardint n); 

void AddEnemies(Square ** & boardint nchar chess_pieceint rowint column);

void ReduceEnemies(Square ** & boardint nchar chess_pieceint rowint column);

int ArrangeQueen(Square ** & boardint nint blackint white);

void Release(Square ** & boardint nint blackint whiteint max);

int main()
{
    
Square ** board;
    
int nmax;
    
    
AllocBoard(boardn);

    
max ArrangeQueen(boardn00);

    
cout << "kmax is: " << max;
    
cout << endl;

    
Release(boardn00max);
    
    
DelBoard(boardn);

    return 
0;
}

void AllocBoard(Square ** & boardint n)
{
    
cout << "Enter the size of the chess-board: ";
    
cin >> n;

    
// Allocate
    
board = new Square * [n];
    for (
int i 0n; ++i)
    {
        
board[i] = new Square [n];
    }

    
// Initialize
    
for (int i 0n; ++i)
    {
        for (
int j 0n; ++j)
        {
            
board[i][j].Queen '*';
            
board[i][j].WhiteEnemies 0
            
board[i][j].BlackEnemies 0;
        }
    }
}

void DelBoard(Square ** & boardint n)
{
    for (
int i 0n; ++i)
    {
        
delete [] board[i];
    }

    
delete [] board;
}

void ShowBoard(Square ** boardint n)
{
    for (
int i 0n; ++i)
    {
        for (
int j 0n; ++j)
        {
            
cout << board[i][j].Queen << " ";
        }

        
cout << endl;
    }
}

void AddEnemies(Square ** & boardint nchar chess_pieceint rowint column)
{
    for (
int i 0n; ++i)
    {
        for (
int j 0n; ++j)
        {
            if (
row == || column == || row column == || row column == j)
            {
                if (
'W' == chess_piece)
                {
                    ++
board[i][j].WhiteEnemies;
                }
                else
                {
                    ++
board[i][j].BlackEnemies;
                }
            }
        }
    }
}

void ReduceEnemies(Square ** & boardint nchar chess_pieceint rowint column)
{
    for (
int i 0n; ++i)
    {
        for (
int j 0n; ++j)
        {
            if (
row == || column == || row column == || row column == j)
            {
                if (
'W' == chess_piece)
                {
                    --
board[i][j].WhiteEnemies;
                }
                else
                {
                    --
board[i][j].BlackEnemies;
                }
            }
        }
    }
}

int ArrangeQueen(Square ** & boardint nint blackint white)
{
    static 
int max 0;

    if (
black == white && max black)
    {
        
max black;
    }
    else
    {
        for (
int i 0n; ++i)
        {
            for (
int j 0n; ++j)
            {
                if (
== board[i][j].WhiteEnemies && '*' == board[i][j].Queen)
                {
                    
board[i][j].Queen 'B';
                    
AddEnemies(boardn'B'ij);
                    
ArrangeQueen(boardnblack 1white);
                    
ReduceEnemies(boardn'B'ij);
                    
board[i][j].Queen '*';
                }
                if (
== board[i][j].BlackEnemies && '*' == board[i][j].Queen)
                {
                    
board[i][j].Queen 'W';
                    
AddEnemies(boardn'W'ij);
                    
ArrangeQueen(boardnblackwhite 1);
                    
ReduceEnemies(boardn'W'ij);
                    
board[i][j].Queen '*';
                }
            }
        }
    }

    return 
        
max;
}

void Release(Square ** & boardint nint blackint whiteint max)
{
    if (
black == white && max == white)
    {
        
cout << endl;
        
ShowBoard(boardn);
        
cout << endl;
    }
    else
    {
        for (
int i 0n; ++i)
        {
            for (
int j 0n; ++j)
            {
                if (
== board[i][j].WhiteEnemies && '*' == board[i][j].Queen)
                {
                    
board[i][j].Queen 'B';
                    
AddEnemies(boardn'B'ij);
                    
ArrangeQueen(boardnblack 1white);
                    
ReduceEnemies(boardn'B'ij);
                    
board[i][j].Queen '*';
                }
                if (
== board[i][j].BlackEnemies && '*' == board[i][j].Queen)
                {
                    
board[i][j].Queen 'W';
                    
AddEnemies(boardn'W'ij);
                    
ArrangeQueen(boardnblackwhite 1);
                    
ReduceEnemies(boardn'W'ij);
                    
board[i][j].Queen '*';
                }
            }
        }
    }

Is this ok?
0
thxthn's Avatar, Join Date: May 2009
Light Poster
I have changed the code, but I still cannot display it??
PHP Code:
#include <iostream>

using namespace std;

struct Square
{
    
char Queen;
    
int BlackEnemies;
    
int WhiteEnemies;
};

void AllocBoard(Square ** & boardint n);

void DelBoard(Square ** & boardint n);

void ShowBoard(Square ** boardint n); 

void AddEnemies(Square ** & boardint nchar chess_pieceint rowint column);

void ReduceEnemies(Square ** & boardint nchar chess_pieceint rowint column);

int ArrangeQueen(int Next,Square ** & boardint nint blackint white);

int main()
{
    
Square ** board;
    
int nmax;

    
AllocBoard(boardn);

    
max ArrangeQueen(0boardn00);

    
cout << "kmax is " << max;
    
cout << endl;

    
DelBoard(boardn);

    return 
0;
}

void AllocBoard(Square ** & boardint n)
{
    
cout << "Enter the size of the chess-board: ";
    
cin >> n;

    
// Allocate
    
board = new Square * [n];
    for (
int i 0n; ++i)
    {
        
board[i] = new Square [n];
    }

    
// Initialize
    
for (int i 0n; ++i)
    {
        for (
int j 0n; ++j)
        {
            
board[i][j].Queen '*';
            
board[i][j].WhiteEnemies 0
            
board[i][j].BlackEnemies 0;
        }
    }
}

void DelBoard(Square ** & boardint n)
{
    for (
int i 0n; ++i)
    {
        
delete [] board[i];
    }

    
delete [] board;
}

void ShowBoard(Square ** boardint n)
{
    for (
int i 0n; ++i)
    {
        for (
int j 0n; ++j)
        {
            
cout << board[i][j].Queen << " ";
        }

        
cout << endl;
    }
}

void AddEnemies(Square ** & boardint nchar chess_pieceint rowint column)
{
    for (
int i 0n; ++i)
    {
        for (
int j 0n; ++j)
        {
            if (
row == || column == || row column == || row column == j)
            {
                if (
'W' == chess_piece)
                {
                    ++
board[i][j].WhiteEnemies;
                }
                else
                {
                    ++
board[i][j].BlackEnemies;
                }
            }
        }
    }
}

void ReduceEnemies(Square ** & boardint nchar chess_pieceint rowint column)
{
    for (
int i 0n; ++i)
    {
        for (
int j 0n; ++j)
        {
            if (
row == || column == || row column == || row column == j)
            {
                if (
'W' == chess_piece)
                {
                    --
board[i][j].WhiteEnemies;
                }
                else
                {
                    --
board[i][j].BlackEnemies;
                }
            }
        }
    }
}

int ArrangeQueen(int Next,Square ** & boardint nint blackint white)
{
    static 
int max 0;

    if (
black == white && max black)
    {
        
max black;
    }

    else
    {
        for (
int i 0n; ++i)
        {
            for (
int j 0n; ++j)
            {
                if (
Next %== && == board[i][j].WhiteEnemies && '*' == board[i][j].Queen)
                {
                    
board[i][j].Queen 'B';
                    
AddEnemies(boardn'B'ij);
                    
ArrangeQueen(Next+1,boardnblack 1white);
                    
ReduceEnemies(boardn'B'ij);
                    
board[i][j].Queen '*';
                }
                else if (
Next %== && == board[i][j].BlackEnemies && '*' == board[i][j].Queen)
                {
                    
board[i][j].Queen 'W';
                    
AddEnemies(boardn'W'ij);
                    
ArrangeQueen(Next+1,boardnblackwhite 1);
                    
ReduceEnemies(boardn'W'ij);
                    
board[i][j].Queen '*';
                }
            }
        }
    }

    return 
        
max;

0
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
> 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?
0
thxthn's Avatar, Join Date: May 2009
Light Poster
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!!!
0
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
Could you outline how the code works and the algorithm you use?
0
thxthn's Avatar, Join Date: May 2009
Light Poster
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.
0
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
Your code doesn't call ShowBoard. Could that be why it doesn't display it?
0
thxthn's Avatar, Join Date: May 2009
Light Poster
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?
0
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
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?
0
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
correction: n*n asterisks, not 64.