Results 1 to 14 of 14
Like Tree1Thanks
  • 1 Post By PaddyMac

Math Help - A chessboard problem

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    Newton
    Posts
    5

    A chessboard problem

    I already posted this on a different forum, but since this is a very special problem, I will shared it here as play first post

    The problem is: you are given a 20x20 chessboard, you are going to place as many queens as possible using the following rules:
    You may place and only queens
    each queen may attack maximum one other queen

    The point system worked as: for the first twenty queens, you get 0 points, then for each queen you place, you get five points. And yes, you try to get as many points as possible.

    For the question maker, they did have something more than 20...

    Enjoy!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    16

    Re: A chessboard problem

    I was able to successfully place 27 queens. I wonder what the maximum is!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2012
    From
    Newton
    Posts
    5

    Re: A chessboard problem

    mmm, is it possible for you to post the solution you had? because the answer they gave is less than that
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    16

    Re: A chessboard problem

    This is wrong because I thought it was rooks, not queens for some reason!

    Actually, my solution has 26 queens haha. You place queens like

    \begin{bmatrix}1 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 1\end{bmatrix}

    to get 4 queens out of a 3 by 3 square. You place these along the diagonal (you can place 6 of these) and you are left with a 2 by 2 square. You can put 2 queens there, to get a total of 26. All the rest of the squares are either occupied or will be attacked by a queen which attacks another queen, so I cannot put more than that with this solution.
    Last edited by Vlasev; September 9th 2012 at 01:35 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Sep 2012
    From
    Newton
    Posts
    5

    Re: A chessboard problem

    the queen can only attack 1 other maximum, not 2 , the queen at the first row second column attacks both first row first column and second row third column, that is attacking 2 other queens
    and by the way, i think you might have not realized queens move in diagonals as well..
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    16

    Re: A chessboard problem

    You are absolutely right, haha. I thought the problem involved rooks, not queens for some reason. I'll have to try it with actual queens now!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Nov 2012
    From
    Hanover, NH
    Posts
    12
    Thanks
    2

    Re: A chessboard problem

    The best I can get is 22, totalling 10 points. I'd be interested to see the solution with 27.
    Attached Thumbnails Attached Thumbnails A chessboard problem-grid.png  
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Nov 2012
    From
    Hanover, NH
    Posts
    12
    Thanks
    2

    Re: A chessboard problem

    Actually, 26.
    Attached Thumbnails Attached Thumbnails A chessboard problem-grid2.png  
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Sep 2012
    From
    Newton
    Posts
    5

    Re: A chessboard problem

    the two last posts does work since the queen at the upper left corner attacks two other queens, the rule is: attack only one or less other queens.
    Once again: Queens move up-down, left-right, and diagonally for a unlimited amount of squares. A queen is attacking another one if the other queen is on one of those "possible movement squares".
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Nov 2012
    From
    Hanover, NH
    Posts
    12
    Thanks
    2

    Re: A chessboard problem

    Oh, well just move the queen from the top left to the bottom left corner. That should work. Then it is a 30 point board.
    Last edited by Stephen347; November 22nd 2012 at 04:53 PM.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Sep 2012
    From
    Newton
    Posts
    5

    Re: A chessboard problem

    does not work still for many other queens many of them are attacking two other ones..
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Nov 2012
    From
    Southern California
    Posts
    12
    Thanks
    1

    Re: A chessboard problem

    The search for a 27-queen solution continues, but for now I have a 26 queens for 30 points. The stairstep pattern at the upper-left is a good indication how early in the search this is.
    The first five queens are in their starting positions and the sixth has only stepped once. There's a lot of room here for a 27 to pop out.
    Attached Thumbnails Attached Thumbnails A chessboard problem-soln56.png  
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Nov 2012
    From
    Southern California
    Posts
    12
    Thanks
    1

    Re: A chessboard problem

    A little analysis shows that 26 queens is the maximum.

    After 20 queens are on the board, additional queens have to share a row with another. The same goes for columns.
    To get 26 queens, we need 6 horizontal pairs and 6 vertical pairs. That is 12 required pairs. Since 26 queens could form 13 pairs, this can be done.
    After forming 6 horizontal pairs and 6 vertical pairs, there are 2 queens free to do as they please so to speak. They may form a pair horizontally, vertically, diagonally or not attack each other at all.
    For example, in my previous post, the queens in columns 17 and 18 do not attack any queens at all.

    To get 27 queens would require 7 horizontal pairs and 7 vertical pairs. That makes 14 required pairs. Since 27 queens can form no more than 13 pairs this is impossible.
    Thanks from Shakarri
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Newbie
    Joined
    Jul 2013
    From
    ho chi minh
    Posts
    2

    Re: A chessboard problem

    doh yeah, good idea

    thiet ke web|du hoc my-----------------
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Chessboard problem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 31st 2011, 03:47 PM
  2. chessboard problem
    Posted in the Statistics Forum
    Replies: 2
    Last Post: January 5th 2011, 01:00 AM
  3. easy chessboard problem
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: August 23rd 2010, 01:09 PM
  4. chessboard problem
    Posted in the Math Topics Forum
    Replies: 4
    Last Post: January 24th 2009, 06:02 AM
  5. Chessboard Problem!
    Posted in the Math Challenge Problems Forum
    Replies: 5
    Last Post: October 22nd 2006, 06:45 PM

Search Tags


/mathhelpforum @mathhelpforum