Thread: Bishops on the chess board, I need help

  1. #1
    Registered User
    Join Date
    Mar 2008
    Posts
    1

    Bishops on the chess board, I need help

    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

  2. #2
    uint64_t...think positive xuftugulus's Avatar
    Join Date
    Feb 2008
    Location
    Pacem
    Posts
    355
    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.
    Code:
    ...
        goto johny_walker_red_label;
    johny_walker_blue_label: exit(-149$);
    johny_walker_red_label : exit( -22$);
    A typical example of ...cheap programming practices.

  3. #3
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    I think he means cover every possible square. If they are on a diagonal, that only covers one color.

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by Adak View Post
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need a second opinion - code error and i cant see it
    By bigfootneedhelp in forum C Programming
    Replies: 19
    Last Post: 10-25-2007, 06:02 AM
  2. Constructor problem
    By rebel in forum C++ Programming
    Replies: 22
    Last Post: 01-11-2006, 06:45 AM
  3. function trouble
    By rebel in forum C++ Programming
    Replies: 4
    Last Post: 12-21-2005, 05:23 AM
  4. Pick a number....
    By Salem in forum A Brief History of Cprogramming.com
    Replies: 39
    Last Post: 01-19-2003, 07:27 AM