I need to put on a chessboard 5 queens so that don't attack each other and they cover the entire cheesboard.
Printable View
I need to put on a chessboard 5 queens so that don't attack each other and they cover the entire cheesboard.
I think you mean you need to find, on an 8x8 grid,
5 places where no diagonal, horz or vertical line meets. Is this right?
If so create an int array
#define MAX_SQUARES 8
int iBoardArray[MAX_SQUARES][MAX_SQUARES];
setup the queen locations in a point array (POINT is struc of two ints x,y or use int[2])
POINT ptQueen[5];
init both to zero with for loops.
Place a queen in the 0,0 location (or get the user to select a location x,y) and set all the horz, vert and diags to one.
ie
Fill in the squares that are in the queens attacking zone and display the modified boardCode://do vert (Y direction)
for(i=0;i<MAX_SQUARES;i++)
iBoardArray[ptQueen[0].x][i]=1;
//do horz (X direction)
for(i=0;i<MAX_SQUARES;i++)
iBoardArray[i][ptQueen[0].y]=1;
//do diag right to left
//This finds the start of a diag line and // ensures that it is in the array ie >=0
xStart=max((ptQueen[0].x-ptQueen[0].y),0);
yStart=max((ptQueen[0].y-ptQueen[0].x),0);
for(i=xStart;i<MAX_SQUARES;i++)
for(j=yStart;j<MAX_SQUARES;j++)
iBoardArray[i][j]=1;
//get the idea? ect
Ask the user to select a new x,y for the second queen and test that all the locations are ==zero. If any are not (==one) then the queen can not be placed there.
Allow the user to clear the board if they wish so need a menu.
I did this in 5mins so may not be 100% or even close but will give you some ideas.
There are 3 ways to do this:
1) perfect algorithm.
sorry, I can't think of one right now, but they do exist.
2) brute force.
Create a function that only checks your board. Create
every possible variant of placing on board and run them
all through your function to see which one is correct.
3) trial and error
let your program do the thing humans would do:
place first queen in first row. mark fields below
that are down or diagonal as occupied. proceed to next
line. repeat. if you come to the last placement and it's
ok, you are done. if you come to a line where you cannot
place a piece, go back one line, take that piece away,
eraze any occupied markings from your removed pieces
and mark that place occupied. proceed with placing on the
line of the removed place.
( obviously you cannot place queens in occupied spaces. )
You can place 8 queens that way. Nice project.