Chess board program.

[Garandy]

I'm supposed to be writing a program for a programming class that involves taking an infinitely scalable chess board, and randomly placing queen pieces on it in such a way that no two can take each other. I've got almost all of my code busted out, it displays and all, but I keep getting an issue where one of my queens doesn't show up (still interacts with the board, kind of), and I get a random 'X' floating around.

#include <iostream>
#include <cstdio>

using namespace std;

#define BOARD_W 4
#define BOARD_H 4

void generate(char[][BOARD_H]);
void display(char[][BOARD_H]);
bool validate(char);
bool validate(char[][BOARD_H], int, int);
void mark(char[][BOARD_H], int, int);
bool check(char[][BOARD_H]);
//bool check(char[][BOARD_H],int,int);

int main()
{
    bool finish = false, valid_reply = false;
    char board[BOARD_W][BOARD_H];
    char reply;
    int count1, count2;
    
    while(finish != true)
    {
                 for(count1 = 0; count1 < BOARD_W; count1++)
                 {
                            for(count2 = 0; count2 < BOARD_H; count2++)
                            {
                                       board[count1][count2] = '.';
                            }
                 }
                 generate(board);
                 display(board);
                 
                 //Asks for another go, and ends if told no.
                 while(valid_reply != true)
                 {
                                   cout << "\n\nWould you like to generate another configuration? (y/n)";
                                   cin >> reply;
                                   valid_reply = validate(reply);
                                   if(reply == 'n')
                                       finish = true;
                                   else
                                       finish = false;
                 }
                 valid_reply = false;
    }
}

void generate(char board[][BOARD_H])
{
     int W;
     int H;
     bool valid = false;
     do
     {
          W = rand()%(BOARD_W);
          H = rand()%(BOARD_H);
          while(board[W][H] != '.')
          {
                          W = rand()%BOARD_W;
                          H = rand()%BOARD_H;
          }
          mark(board, W, H);
          board[W][H] = 'Q';
          cout << endl << H + 1 << " " << W + 1 << " " << check(board) << endl; //DEBUG LINE  */
     }
     while(check(board) != true);
}

void display(char board[][BOARD_H])
{
     int count, count1;
     for(count1 = 0; count1 < BOARD_H; count1 ++)
     {
                cout << "\n";
                for(count = 0; count < BOARD_W; count++)
                {
                          cout << " -";
                }
                cout << " \n";
                for(count = 0; count < BOARD_W; count++)
                {
                          cout << "|" << board[count][count1];
                }
                cout << "|";
     }
     cout << "\n";
     for(count = 0; count < BOARD_W; count++)
     {
                cout << " -";
     }
}

bool validate(char reply)
{
     if(reply == 'y' || reply == 'n')
              return true;
     else
              return false;
}

void mark(char board[][BOARD_H], int W, int H)
{
     int W1, H1, count1;
     W1 = W;
     H1 = H;
     while(W1 > 0 && H1 > 0)
     {
            W1-- && H1--;
            board[W1][H1] = 'X';
     }
     W1 = W;
     H1 = H;
     while(W1 <= BOARD_W && H1 > 0)
     {
            W1++ && H1--;
            board[W1][H1] = 'X';
     }
     W1 = W;
     H1 = H;
     while(W1 > 0 && H1 <= BOARD_H)
     {
            W1-- && H1++;
            board[W1][H1] = 'X';
     }
     W1 = W;
     H1 = H;
     while(W1 <= BOARD_W && H1 <= BOARD_H)
     {
            W1++ && H1++;
            board[W1][H1] = 'X';
     }
     for(count1 = 0; count1 < BOARD_W; count1++)
     {
                board[count1][H] = 'X';
     }
     for(count1 = 0; count1 < BOARD_H; count1++)
     {
                board[W][count1] = 'X';
     }
     board[W][H] = 'Q';
     return;
}

bool check(char board[][BOARD_H])
{
     bool done = true;
     int count, count2;
     for(count = 0; count < BOARD_W; count++)
     {
               for(count2 = 0; count2 < BOARD_H; count2++)
               {
                          if(board[count][count2] == '.')
                                                  done = false;
               }
     }
     return done;
}

/*bool check(char board[][BOARD_H], int W, int H)
{
     int W1, H1, count1;
     W1 = W;
     H1 = H;
     while(W1 > 0 && H1 > 0)
     {
            W1-- && H1--;
            if(board[W1][H1] == 'Q')
                             return false;
     }
     W1 = W;
     H1 = H;
     while(W1 <= BOARD_W && H1 > 0)
     {
            W1++ && H1--;
            if(board[W1][H1] == 'Q')
                             return false;
     }
     W1 = W;
     H1 = H;
     while(W1 > 0 && H1 <= BOARD_H)
     {
            W1-- && H1++;
            if(board[W1][H1] == 'Q')
                             return false;
     }
     W1 = W;
     H1 = H;
     while(W1 <= BOARD_W && H1 <= BOARD_H)
     {
            W1++ && H1++;
            if(board[W1][H1] == 'Q')
                             return false;
     }
     for(count1 = 0; count1 < BOARD_W; count1++)
     {
                if(board[W1][H1] == 'Q')
                             return false;
     }
     for(count1 = 0; count1 < BOARD_H; count1++)
     {
                if(board[W1][H1] == 'Q')
                             return false;
     }
     return true;
}
*/

I realize it's probably very sloppy, and 1 of my includes is unneccessary. Right now, I just need a sounding board, someone to look it over and find that one little thing that keeps throwing me for a loop.

[writetonsharma]

i think you are trying to develop the famous 8 queen problem. am i correct?
where no queen comes in the way of any other queen.

[writetonsharma]

see you are generating the positions randomly, there is no guarantee that the queens will be placed this way.. it can take any amount of time for this.. because your algo is based on chance.. secondly if it didnt find any position on any specific row then what will happen, it will go to next row.. if i am correct?

[Garandy]

Yes, just with the ability to scale it (thus my #defines). Any Ideas what could possibly be up with my code?

[writetonsharma]

i suggest you should recreate your logic using back tracking.. i wrote this problem some time back and you can have a look at it:

http://www.codeproject.com/KB/cpp/8Queen_Problem.aspx

i create it on windows though with a very good interface, if you are working on windows then you can compile the code and look at it.
i am posting something which will be useful to you. check the next post.

[writetonsharma]

take a board:
BOOL **g_QueenArray; //allocate memory to according to your #defines

//allocate memory, instead of g_BoardSize use your #defines.
g_QueenArray = (BOOL**)calloc(g_BoardSize, sizeof(BOOL));
for(i = 0;i < g_BoardSize;i++)
{
    *(g_QueenArray + i) = (BOOL*)calloc(g_BoardSize, sizeof(BOOL));
} 

//this is the main function, it will return when it places all the queens correctly in g_QueenArray.
//otherwise it will return false. X and Y are row and column positions. see if you find anything useful in this and can create your own program.
int Backtracking(HWND hWnd, int Pos_X, int Pos_Y)
{
    int New_Y;
    RECT    rect;    

    if(g_BoardSize == 0)
        return TRUE;

    if(Pos_X == g_BoardSize)
        return TRUE;

    while(Pos_Y < g_BoardSize)
    {
        if(!SetNextQueen(Pos_X, Pos_Y, &New_Y))
            return false;

        int OneBoxSize = WND_WIDTH / g_BoardSize;

        Pos_Y = New_Y;    

        rect.left = Pos_Y * OneBoxSize;
        rect.right = (Pos_Y + 1) * (OneBoxSize);
        rect.top = Pos_X * OneBoxSize;
        rect.bottom = (Pos_X + 1) * OneBoxSize;
        
        InvalidateRect(hWnd, &rect, TRUE);
        //UpdateWindow(hWnd);
        Sleep(400);
        if(g_Stop)
        {
            g_Stop = FALSE;
            return TRUE;
        }

        if(Backtracking(hWnd, Pos_X + 1, 0))
        {
            return TRUE;
        }
        else
        {
            rect.left = Pos_Y * OneBoxSize;
            rect.right = (Pos_Y + 1) * (OneBoxSize);
            rect.top = Pos_X * OneBoxSize;
            rect.bottom = (Pos_X + 1) * OneBoxSize;

            g_QueenArray[Pos_X][Pos_Y++] = FALSE;
            
            InvalidateRect(hWnd, &rect, TRUE);
            UpdateWindow(hWnd);
            Sleep(400);
            
            if(Pos_Y == g_BoardSize)
                return false;
        }
    }
    
    return TRUE;
} 

[Garandy]

Holy crap. I understood... 15% of that.

I'm doing this for an OOP course in college. My primary language is VB.Net (foraying into C/C++, no windows yet), so none of that made any sense.

The page seems to have a bit of helpful info, though. Thanks.

[writetonsharma]

lets make it a bit easy.. wat say??? if it solves your problem..

[writetonsharma]

actually your design will not be able to solve the problem which are doing.

see the problem is this:
for each row you calculate a position where the queen can fit. but after 3-4 rows there will be no position left to fit the queen and your program will move to next row. so some rows will be left blank. correct??

in this case you need to go back to previous rows and recheck the positions and again move forward.. if still you didn't succeed then again move back and reposition.. this process will continue till you place all your queens.

and this process is called back tracking.. you move back and again rethink and move forward..till you succeed.