1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

k black and k white

Discussion in 'C++' started by thxthn, May 4, 2009.

  1. thxthn

    thxthn New Member

    Joined:
    May 4, 2009
    Messages:
    6
    Likes Received:
    0
    Trophy Points:
    0
    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 ** & 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?
     
  2. thxthn

    thxthn New Member

    Joined:
    May 4, 2009
    Messages:
    6
    Likes Received:
    0
    Trophy Points:
    0
    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 ** & 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;
    }

     
  3. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    > 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?
     
  4. thxthn

    thxthn New Member

    Joined:
    May 4, 2009
    Messages:
    6
    Likes Received:
    0
    Trophy Points:
    0
    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!!!
     
  5. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    Could you outline how the code works and the algorithm you use?
     
  6. thxthn

    thxthn New Member

    Joined:
    May 4, 2009
    Messages:
    6
    Likes Received:
    0
    Trophy Points:
    0
    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.
     
  7. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    Your code doesn't call ShowBoard. Could that be why it doesn't display it?
     
  8. thxthn

    thxthn New Member

    Joined:
    May 4, 2009
    Messages:
    6
    Likes Received:
    0
    Trophy Points:
    0
    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?
     
  9. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    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?
     
  10. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    correction: n*n asterisks, not 64.
     
  11. thxthn

    thxthn New Member

    Joined:
    May 4, 2009
    Messages:
    6
    Likes Received:
    0
    Trophy Points:
    0
    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.
     

Share This Page