I need to write a program which finds the places on a chess board, where 8 bishops should be placed that the lines of their movement would cover whole chess board. Maybe someone could help me and suggest some algorithm for this task?
Thanks
I need to write a program which finds the places on a chess board, where 8 bishops should be placed that the lines of their movement would cover whole chess board. Maybe someone could help me and suggest some algorithm for this task?
Thanks
Vaguely thinking, the most plain cases are the two diagonals.
When either diagonal of the board is lined with bishops, then they cover the whole board.
But, permuting the bishops along their movement on the board would also cover the whole board.
So your algorithm might look like all the permutations of bishops positioned along either the right or the left diagonal when allowed to move on their movement path.
eg.
[.......B]
[......B.]
[.....B..]
[....B...]
[...B....]
[..B.....]
[.B......]
[B.......]
Start from something like this, and starting moving them around and i think it should do the job.
A typical example of ...cheap programming practices.Code:... goto johny_walker_red_label; johny_walker_blue_label: exit(-149$); johny_walker_red_label : exit( -22$);
I think he means cover every possible square. If they are on a diagonal, that only covers one color.
I would code up a scan of the search space, (brute force), where no two bishops can be on the same diagonal. Also, the individuality of each bishop should be ignored. If the answer is a straight line of bishops right down the middle of the board, it won't matter if the #1 bishop is top of the row of bishops, or if the bishop is really #2, etc.
At the end of every placement, count up the number of squares that the bishops cover (remembering their 4 possible ways of moving: 2, 4, 8, and 10 o'clock), which converts to (say 2 o'clock): row + i, col + i, until the diagonal ray reaches the edge of the board.
When the 4 ways of moving have been taken into consideration, then simply add up every square each bishop has covered. When you reach 64, you're done.
There will be mirrored or rotated answers to this, but that should cause no worries.
If you do this, you'll want to be careful not to double-count squares, if two bishops end up attacking the same square.
Other alternative: backtracking. Place a bishop, place another bishop on an unattacked square, place a third bishop on an unattacked square, ..., place an eighth bishop on an unattacked square. If there are unattacked square, move the eighth bishop. If it turns out that nowhere works for the eighth bishop, move the seventh bishop and try the eighth again. Obviously, you will want a systematic way to move the bishops so that you know you've tried all the squares.