Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C++ (http://www.go4expert.com/forums/cpp/)
-   -   k black and k white (http://www.go4expert.com/forums/k-black-k-white-t17315/)

thxthn 4May2009 10:39

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

thxthn 4May2009 14:49

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



xpi0t0s 4May2009 16:45

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?

thxthn 4May2009 18:53

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

xpi0t0s 4May2009 19:56

Re: k black and k white
 
Could you outline how the code works and the algorithm you use?

thxthn 5May2009 16:20

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.

xpi0t0s 6May2009 14:54

Re: k black and k white
 
Your code doesn't call ShowBoard. Could that be why it doesn't display it?

thxthn 6May2009 15:21

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?

xpi0t0s 6May2009 15:29

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?

xpi0t0s 6May2009 15:30

Re: k black and k white
 
correction: n*n asterisks, not 64.


All times are GMT +5.5. The time now is 03:35.