eight queen exhaustive techinue

Question

ntrncx 19 Junior Poster

13 Years Ago

hey again i do that problem from my book,

worked but i am pretty sure is not the exhaustive technique that book is asking cause i didnt have success and was too fast.
i tried a counter and do 64x64 loops or 4096 loops.

so my question cause i couldnt find in google,is there are site or someone explain me where i can read about exhaustive technique for that problem or in general?

thats the code i have writen for that problem

p.s: is the code in readable form?or is chaotic?

#include <iostream>
#include <cmath>
using namespace std;

const int size=8;

void calculateMoves(int[][size],int,int,int&,int);
void proccess(int[][size],int&,int);

//Moves and directions of the queen
void right(int[][size],int,int,int&,int);
void down(int[][size],int,int,int&,int);
void left(int[][size],int,int,int&,int);
void up(int[][size],int,int,int&,int);
void diagonalUpRight(int[][size],int,int,int&,int);
void diagonalUpLeft(int[][size],int,int,int&,int);
void diagonalDownRight(int[][size],int,int,int&,int);
void diagonalDownLeft(int[][size],int,int,int&,int);

//Board manipulations
void resetBoard(int [][size]);
void printBoard(int[][size]);

int main()
{
    int chessBoard[size][size]={};
    int counter=0;
    int queen=1;
    srand(time(0));
    
    for(int currentRow=0;currentRow<size;currentRow++)
    {
        for(int currentColumn=0;currentColumn<size;currentColumn++)
        {
            calculateMoves(chessBoard,currentRow,currentColumn,counter,queen);
            proccess(chessBoard,counter,queen);
            resetBoard(chessBoard);
            queen=1;       
        }
    }
}

//------------------------------------------------------------------------------

void proccess(int chessBoard[][size],int &counter,int queen)
{
    for(int row=0;row<size;row++)
    {
        for(int column=0;column<size;column++)
        {
            if(chessBoard[row][column]==0)
            {
                calculateMoves(chessBoard,row,column,counter,queen);
                queen++;
            }
        }
    }
    if (queen==8) //i still have a problem with that ,i have to put 8 for show when its 7 :P
        printBoard(chessBoard);
}

//------------------------------------------------------------------------------

void calculateMoves(int board[][size],int row,int column,int &counter,int queen)
{
    counter=0;

    down(board,row,column,counter,queen);
    right(board,row,column,counter,queen);
    up(board,row,column,counter,queen);
    left(board,row,column,counter,queen);

    diagonalDownRight(board,row,column,counter,queen);
    diagonalUpLeft(board,row,column,counter,queen);
    diagonalUpRight(board,row,column,counter,queen);
    diagonalDownLeft(board,row,column,counter,queen);
}

//Moves and directions of the queen
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------

void right(int chessboard[][size],int row,int column,int &counter,int queen)
{
    //decreasing row
    for(int temponarycolumn=column;temponarycolumn<size;temponarycolumn++)
    {
        if(temponarycolumn>=0 && temponarycolumn<size)
        {
            if (chessboard[row][temponarycolumn]==0)
            {
                chessboard[row][temponarycolumn]=queen;
                counter++;
            }
        }
    }
}

//------------------------------------------------------------------------------

void down(int chessboard[][size],int row,int column,int &counter,int queen)
{
    //increasing row
    for(int temponaryrow=row;temponaryrow<size;temponaryrow++)
    {
        if(temponaryrow>=0 && temponaryrow<size)
        {
            if (chessboard[temponaryrow][column]==0)
            {
                chessboard[temponaryrow][column]=queen;
                counter++;
            }
        }
    }
}

//------------------------------------------------------------------------------

void left(int chessboard[][size],int row,int column,int &counter,int queen)
{
    //decreasing row
    for(int temponarycolumn=column;temponarycolumn>=0;temponarycolumn--)
    {
        if(temponarycolumn>=0 && temponarycolumn<size)
        {
            if (chessboard[row][temponarycolumn]==0)
            {
                chessboard[row][temponarycolumn]=queen;
                counter++;
            }
        }
    }
}

//------------------------------------------------------------------------------

void up(int chessboard[][size],int row,int column,int &counter,int queen)
{
    //increasing row
    for(int temponaryrow=row;temponaryrow>=0;temponaryrow--)
    {
        if(temponaryrow>=0 && temponaryrow<size)
        {
            if (chessboard[temponaryrow][column]==0)
            {
                chessboard[temponaryrow][column]=queen;
                counter++;
            }
        }
    }
}

//------------------------------------------------------------------------------

void diagonalUpRight(int chessboard[][size],int row,int column,int &counter,int queen)
{
// diagonal
    int temponaryrow=row;
    int temponarycolumn=column;

    for(int x=0;x<size;x++)
    {
        temponaryrow+=-1;
        temponarycolumn+=1;

        if(temponaryrow>=0 && temponaryrow<size && temponarycolumn>=0 && temponarycolumn<size)
        {
            if (chessboard[temponaryrow][temponarycolumn]==0)
            {
                chessboard[temponaryrow][temponarycolumn]=queen;
                counter++;
            }
        }
    }
}

//------------------------------------------------------------------------------

void diagonalUpLeft(int chessboard[][size],int row,int column,int &counter,int queen)
{
    //diagonal
    int temponaryrow=row;
    int temponarycolumn=column;

    for(int x=0;x<size;x++)
    {
        temponaryrow+=-1;
        temponarycolumn+=-1;

        if(temponaryrow>=0 && temponaryrow<size && temponarycolumn>=0 && temponarycolumn<size)
        {
            if (chessboard[temponaryrow][temponarycolumn]==0)
            {
                chessboard[temponaryrow][temponarycolumn]=queen;
                counter++;
            }
        }
    }
}

//------------------------------------------------------------------------------

void diagonalDownRight(int chessboard[][size],int row,int column,int &counter,int queen)
{
// diagonal
    int temponaryrow=row;
    int temponarycolumn=column;

    for(int x=0;x<size;x++)
    {
        temponaryrow+=1;
        temponarycolumn+=1;

        if(temponaryrow>=0 && temponaryrow<size && temponarycolumn>=0 && temponarycolumn<size)
        {
            if (chessboard[temponaryrow][temponarycolumn]==0)
            {
                chessboard[temponaryrow][temponarycolumn]=queen;
                counter++;
            }
        }
    }
}

//------------------------------------------------------------------------------

void diagonalDownLeft(int chessboard[][size],int row,int column,int &counter,int queen)
{
    //diagonal
    int temponaryrow=row;
    int temponarycolumn=column;

    for(int x=0;x<size;x++)
    {
        temponaryrow+=1;
        temponarycolumn+=-1;

         if(temponaryrow>=0 && temponaryrow<size && temponarycolumn>=0 && temponarycolumn<size)
        {
             if (chessboard[temponaryrow][temponarycolumn]==0)
            {
                chessboard[temponaryrow][temponarycolumn]=queen;
                counter++;
            }
        }
    }
}

//------------------------------------------------------------------------------

//Board manipulations
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------

void printBoard(int chessBoard[][size])
{
    for(int row=0;row<size;row++)
    {
        for(int column=0;column<size;column++)
        {
            cout<<chessBoard[row][column]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}

//------------------------------------------------------------------------------

void resetBoard(int chessBoard[][size])
{
    for(int row=0;row<size;row++)
    {
        for(int column=0;column<size;column++)
        {
            chessBoard[row][column]=0;
        }
    }
}

//------------------------------------------------------------------------------

c++

4 Contributors
8 Replies
202 Views
2 Weeks Discussion Span
Latest Post 13 Years Ago Latest Post by template<>

template<> 37 Junior Poster

13 Years Ago

Might be cleaner if you design you problem in terms of objects (use classes)

Momerath 1,327 Nearly a Senior Poster

13 Years Ago

If you want exhaustive bruteforce then just have 8 loops going from column position 1 to 8. Each loop represents a row. Take the 8 positions and see if it is a solution. Continue until done. It's only 16,777,216 different positions.

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

ntrncx 19 Junior Poster · Answer 1 · 2011-03-06T23:37:12+00:00

i will try to modify it with classes and post it again here

ntrncx 19 Junior Poster · Answer 2 · 2011-03-07T23:01:47+00:00

meanwhile no one any advice about the concept and login of exhaustive tequinque in 8x8 2d array?

arkoenig 340 Practically a Master Poster · Answer 3 · 2011-03-07T23:52:20+00:00

If you are trying to solve the problem of putting eight queens on a chessboard so that none of them attacks any of the others, your program is dramatically larger than it needs to be. You can find a shorter solution here.

ntrncx 19 Junior Poster · Answer 4 · 2011-03-08T07:34:18+00:00

yes thats what i try to do but,i did it with strategy/heritage,i did it with random bruteforce now i have to do it with exhaustive bruteforce but i dont know how to start.
it suppose that it must check all the possibilities.

ntrncx 19 Junior Poster · Answer 5 · 2011-03-24T04:44:09+00:00

some one said that is too big my code,i try to thing a way to check the moves together but i cant thing about,how to do it.

in am asking an advice about replacing all the functions that check the queen moves separately to something smaller.

any description will be helpful :D

template<> 37 Junior Poster · Answer 6 · 2011-03-24T07:47:02+00:00

Have you tried google? eight queen problem c++ recursion

Lots of information on the classic problem, below are some..

http://wn.com/eight_queens_problem

http://en.wikipedia.org/wiki/Eight_queens_puzzle

http://people.moreheadstate.edu/fs/d.chatham/dlxMCCC.pdf