Go4Expert - k black and k white

Go4Expert (http://www.go4expert.com/)

- C++ (http://www.go4expert.com/forumdisplay.php?f=100)

- - k black and k white (http://www.go4expert.com/showthread.php?t=17315)

k black and k white

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 ** & 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?

Re: k black and k white

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 ** & 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;
}

Re: k black and k white

> 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?

Re: k black and k white

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!!!

Re: k black and k white

Could you outline how the code works and the algorithm you use?

Re: k black and k white

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.

Re: k black and k white

Your code doesn't call ShowBoard. Could that be why it doesn't display it?

Re: k black and k white

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?

Re: k black and k white

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?

Re: k black and k white

correction: n*n asterisks, not 64.