Reply
 
LinkBack Thread Tools Display Modes
  #1   Report Post  
Old September 20th 07, 12:03 AM posted to rec.games.chess.misc,alt.chess,rec.games.chess.computer,alt.math.recreational
external usenet poster
 
First recorded activity by ChessBanter: Oct 2006
Posts: 95
Default Source for Eight Officers Problem?


Last night, I googled the Web for information about the Eight Officers
problem. (Put two rooks, two knights, two bishops, a queen, and a king
on a blank chessboard so that every square is attacked --- not just
occupied.) I found a solution where both bishops are on the same
colored square, and about a dozen positions where 63 squares are
attacked. The general consensus is that 63 is best possible, and that
the Eight Officers problem is impossible.

My question is this: Can anyone reference a book or a journal where a
full analysis of the impossibility of the Eight Officers appears? I am
seeking something along the lines of mathematical proof or a report of
doing brute force.

Thank you.

--- Christopher Heckman

  #2   Report Post  
Old September 20th 07, 02:49 AM posted to rec.games.chess.misc,alt.chess,rec.games.chess.computer,alt.math.recreational
external usenet poster
 
First recorded activity by ChessBanter: Oct 2006
Posts: 95
Default Source for Eight Officers Problem?

On Sep 19, 6:35 pm, "Dan in NY" wrote:
"Proginoskes" wrote in message ups.com...

Last night, I googled the Web for information about the Eight Officers
problem. (Put two rooks, two knights, two bishops, a queen, and a king
on a blank chessboard so that every square is attacked --- not just
occupied.) I found a solution where both bishops are on the same
colored square, and about a dozen positions where 63 squares are
attacked. The general consensus is that 63 is best possible, and that
the Eight Officers problem is impossible.


My question is this: Can anyone reference a book or a journal where a
full analysis of the impossibility of the Eight Officers appears? I am
seeking something along the lines of mathematical proof or a report of
doing brute force.


&&&
Greetings Christopher,

I searched google with [chess puzzles "eight officers"] (without the []) and
got 127 hits. One is The Kibitzer's Cafe on this website of chessgames.com:http://www.chessgames.com/perl/chess...463#reply12029
It looks like some sort of blog entry from 2004. Maybe The Oxford
Companion to Chess has something for you but all I know about it is this:
&&&
May-26-04
donhart: The Oxford Companion to Chess contains 570 biographies,
entries for 700 openings and variations, definitions for even the most
obscure terms, 220 games, and 1990 compositions, plus interesting entries on
blindfold chess, coffee houses, the Lewis chessmen, education and chess,
literature and chess, chess literature itself, etc. Perhaps you have
dicovered 'ad libitum' in the literature and want to know what it means?
Curious about how long a chess game could theoretically be? Ever heard of
the Alfonso Ms.? The Eight Officers Puzzle? I bought my copy at a second
hand store for $20 Canadian, and I have seen it repeatedly in other second
hand shops. It's listed at amazon.com, along with several different readers'
reviews. It has often proven itself to be an invaluable reference tool for
me. Many of the questions that are posted here at the Kibitzer's Cafe can be
answered with this fascinating book. Chess Champ You were expressing an
interest in The Oxford Companion a little while ago. If you have not got it
yet, perhaps I can whet your appetite.
&&&
If you don't want to purchase it, perhaps a local library could search and
find a copy for you.


They have it at the library here at ASU, so I'll check it out. (No pun
intended!)

BTW, I seem to recall this review of the book, but I kept searching
for something more definite (with all the gory details!). I thought
that MathSciNet, which is an index to many many many mathematics
journals, might be able to help find the article, but it couldn't find
anything.

--- Christopher Heckman

  #3   Report Post  
Old September 20th 07, 09:42 AM posted to rec.games.chess.misc,alt.chess,rec.games.chess.computer,alt.math.recreational
external usenet poster
 
First recorded activity by ChessBanter: Oct 2006
Posts: 95
Default Source for Eight Officers Problem?

On Sep 19, 6:49 pm, Proginoskes wrote:
On Sep 19, 6:35 pm, "Dan in NY" wrote:



"Proginoskes" wrote in oglegroups.com...


Last night, I googled the Web for information about the Eight Officers
problem. (Put two rooks, two knights, two bishops, a queen, and a king
on a blank chessboard so that every square is attacked --- not just
occupied.) I found a solution where both bishops are on the same
colored square, and about a dozen positions where 63 squares are
attacked. The general consensus is that 63 is best possible, and that
the Eight Officers problem is impossible.


My question is this: Can anyone reference a book or a journal where a
full analysis of the impossibility of the Eight Officers appears? I am
seeking something along the lines of mathematical proof or a report of
doing brute force.


&&&
Greetings Christopher,


I searched google with [chess puzzles "eight officers"] (without the []) and
got 127 hits. One is The Kibitzer's Cafe on this website of chessgames.com:http://www.chessgames.com/perl/chess...463#reply12029
It looks like some sort of blog entry from 2004. Maybe The Oxford
Companion to Chess has something for you but all I know about it is this:
&&&
May-26-04
donhart: The Oxford Companion to Chess contains 570 biographies,
entries for 700 openings and variations, definitions for even the most
obscure terms, 220 games, and 1990 compositions, plus interesting entries on
blindfold chess, coffee houses, the Lewis chessmen, education and chess,
literature and chess, chess literature itself, etc. Perhaps you have
dicovered 'ad libitum' in the literature and want to know what it means?
Curious about how long a chess game could theoretically be? Ever heard of
the Alfonso Ms.? The Eight Officers Puzzle? I bought my copy at a second
hand store for $20 Canadian, and I have seen it repeatedly in other second
hand shops. It's listed at amazon.com, along with several different readers'
reviews. It has often proven itself to be an invaluable reference tool for
me. Many of the questions that are posted here at the Kibitzer's Cafe can be
answered with this fascinating book. Chess Champ You were expressing an
interest in The Oxford Companion a little while ago. If you have not got it
yet, perhaps I can whet your appetite.
&&&
If you don't want to purchase it, perhaps a local library could search and
find a copy for you.


They have it at the library here at ASU, so I'll check it out. (No pun
intended!) [...]


No good. They only say it's "impossible". No name, no reference. But
it's a good enough reference that if I ever see it, I'll pick it up.

(In mathematics, there are some theorems known as "folklore theorems".
These are theorems which have obvious but long proofs, which "someone"
did a long time ago but never published, so you can't give a
reference. That's what this result about the Eight Officers reminds me
of.)

However, I _did_ find an interesting book, which should be called
_Chess To Enjoy II_ but whose real title is _The even more complete
chess addict_ which is by Mike Fox and Richard James. Another one for
my list.

--- Christopher Heckman


  #4   Report Post  
Old September 21st 07, 05:18 PM posted to rec.games.chess.misc,alt.chess,rec.games.chess.computer,alt.math.recreational
external usenet poster
 
First recorded activity by ChessBanter: Nov 2006
Posts: 364
Default Source for Eight Officers Problem?

Den 2007-09-20 01:03:03 skrev Proginoskes :


Last night, I googled the Web for information about the Eight Officers
problem. (Put two rooks, two knights, two bishops, a queen, and a king
on a blank chessboard so that every square is attacked --- not just
occupied.) I found a solution where both bishops are on the same
colored square, and about a dozen positions where 63 squares are
attacked. The general consensus is that 63 is best possible, and that
the Eight Officers problem is impossible.

My question is this: Can anyone reference a book or a journal where a
full analysis of the impossibility of the Eight Officers appears? I am
seeking something along the lines of mathematical proof or a report of
doing brute force.

Thank you.

--- Christopher Heckman




Have you seen this?
http://www.gpj.connectfree.co.uk/gpjv.htm

BTW, Zillions of Games is ideal for implementing this kind of problem. In the
freeware download are the six-, eight-, and sixteen queens problems, ten
Maharadas problem, and maximal knights problem.

Mats
  #5   Report Post  
Old September 22nd 07, 12:17 AM posted to rec.games.chess.misc,alt.chess,rec.games.chess.computer,alt.math.recreational
external usenet poster
 
First recorded activity by ChessBanter: Oct 2006
Posts: 95
Default Source for Eight Officers Problem?

On Sep 21, 9:18 am, "M Winther" wrote:
Den 2007-09-20 01:03:03 skrev Proginoskes :

Last night, I googled the Web for information about the Eight Officers
problem. (Put two rooks, two knights, two bishops, a queen, and a king
on a blank chessboard so that every square is attacked --- not just
occupied.) I found a solution where both bishops are on the same
colored square, and about a dozen positions where 63 squares are
attacked. The general consensus is that 63 is best possible, and that
the Eight Officers problem is impossible.


My question is this: Can anyone reference a book or a journal where a
full analysis of the impossibility of the Eight Officers appears? I am
seeking something along the lines of mathematical proof or a report of
doing brute force.


Have you seen this? http://www.gpj.connectfree.co.uk/gpjv.htm


Yes. That's one of the first hits for "Eight Officers" and "chess" on
Google. They say "It is impossible to arrange the eight officers to
dominate the board, that is to guard all 64 cells.", and that's it. No
mention of who, when, how they did it; _that_'s what I'm after.

BTW, Zillions of Games is ideal for implementing this kind of problem. In the
freeware download are the six-, eight-, and sixteen queens problems, ten
Maharadas problem, and maximal knights problem.


Looks like a fun program too. They have many variations of chess, but
I didn't see Laser Chess: http://www.public.asu.edu/~checkma/laserchess/

--- Christopher Heckman



  #6   Report Post  
Old September 22nd 07, 08:41 AM posted to rec.games.chess.misc,alt.chess,rec.games.chess.computer,alt.math.recreational
external usenet poster
 
First recorded activity by ChessBanter: Nov 2006
Posts: 364
Default Source for Eight Officers Problem?

Den 2007-09-22 01:17:34 skrev Proginoskes :

On Sep 21, 9:18 am, "M Winther" wrote:
Den 2007-09-20 01:03:03 skrev Proginoskes :

Last night, I googled the Web for information about the Eight Officers
problem. (Put two rooks, two knights, two bishops, a queen, and a king
on a blank chessboard so that every square is attacked --- not just
occupied.) I found a solution where both bishops are on the same
colored square, and about a dozen positions where 63 squares are
attacked. The general consensus is that 63 is best possible, and that
the Eight Officers problem is impossible.


My question is this: Can anyone reference a book or a journal where a
full analysis of the impossibility of the Eight Officers appears? I am
seeking something along the lines of mathematical proof or a report of
doing brute force.


Have you seen this? http://www.gpj.connectfree.co.uk/gpjv.htm


Yes. That's one of the first hits for "Eight Officers" and "chess" on
Google. They say "It is impossible to arrange the eight officers to
dominate the board, that is to guard all 64 cells.", and that's it. No
mention of who, when, how they did it; _that_'s what I'm after.

BTW, Zillions of Games is ideal for implementing this kind of problem. In the
freeware download are the six-, eight-, and sixteen queens problems, ten
Maharadas problem, and maximal knights problem.


Looks like a fun program too. They have many variations of chess, but
I didn't see Laser Chess: http://www.public.asu.edu/~checkma/laserchess/

--- Christopher Heckman




Many Zillions programs of chess variants are downloadable on
http://www.chessvariants.org

I have implemented many myself:
http://hem.passagen.se/melki9/chessvar.htm

Mats

  #7   Report Post  
Old September 22nd 07, 05:53 PM posted to rec.games.chess.misc,alt.chess,rec.games.chess.computer,alt.math.recreational
external usenet poster
 
First recorded activity by ChessBanter: Sep 2007
Posts: 3
Default Source for Eight Officers Problem?

On Sep 19, 4:03 pm, Proginoskes wrote:
Last night, I googled the Web for information about the Eight Officers
problem. (Put two rooks, two knights, two bishops, a queen, and a king
on a blank chessboard so that every square is attacked --- not just
occupied.) I found a solution where both bishops are on the same
colored square, and about a dozen positions where 63 squares are
attacked. The general consensus is that 63 is best possible, and that
the Eight Officers problem is impossible.

My question is this: Can anyone reference a book or a journal where a
full analysis of the impossibility of the Eight Officers appears? I am
seeking something along the lines of mathematical proof or a report of
doing brute force.

Thank you.

--- Christopher Heckman


Why cannot both bishops be on the same colored square? Does the
problem specifically state that all "officers" must be of the same
"color"; ie, all white or all black?

Bill J


  #8   Report Post  
Old September 23rd 07, 09:55 AM posted to rec.games.chess.misc,alt.chess,rec.games.chess.computer,alt.math.recreational
external usenet poster
 
First recorded activity by ChessBanter: Oct 2006
Posts: 95
Default Source for Eight Officers Problem?

On Sep 22, 9:53 am, JillBones wrote:
On Sep 19, 4:03 pm, Proginoskes wrote:

Last night, I googled the Web for information about the Eight Officers
problem. (Put two rooks, two knights, two bishops, a queen, and a king
on a blank chessboard so that every square is attacked --- not just
occupied.) I found a solution where both bishops are on the same
colored square, and about a dozen positions where 63 squares are
attacked. The general consensus is that 63 is best possible, and that
the Eight Officers problem is impossible.


My question is this: Can anyone reference a book or a journal where a
full analysis of the impossibility of the Eight Officers appears? I am
seeking something along the lines of mathematical proof or a report of
doing brute force.


Thank you.


Why cannot both bishops be on the same colored square?


(1) Some people insist on this condition. (2) It makes solving the
problem non-trivial (which is the same reason that occupying a square
doesn't count as controlling it). If you allow the bishops to be on
the same color, then you *can* control all 64 squares, and the proof
is a simple diagram.

Does the problem specifically state that all "officers" must be of the same
"color"; ie, all white or all black?


Yes.

--- Christopher Heckman

  #9   Report Post  
Old September 24th 07, 06:25 AM posted to rec.games.chess.misc,alt.chess,rec.games.chess.computer,alt.math.recreational
external usenet poster
 
First recorded activity by ChessBanter: Oct 2006
Posts: 95
Default Source for Eight Officers Problem?

On Sep 23, 2:11 am, rrock wrote:
Proginoskes wrote:
Last night, I googled the Web for information about the Eight Officers
problem. (Put two rooks, two knights, two bishops, a queen, and a king
on a blank chessboard so that every square is attacked --- not just
occupied.) I found a solution where both bishops are on the same
colored square, and about a dozen positions where 63 squares are
attacked. The general consensus is that 63 is best possible, and that
the Eight Officers problem is impossible.


My question is this: Can anyone reference a book or a journal where a
full analysis of the impossibility of the Eight Officers appears? I am
seeking something along the lines of mathematical proof or a report of
doing brute force.


Thank you.


So were i to put together a brute force approach, just what sort of
report would you have it spit out?


The simple way would be an algorithm to look at all possible placings
of the pieces and then to output any arrangements that work; then the
lack of output would be the proof of the impossibility.

This is, of course, not the best possible proof, especially if you use
a computer, since all sorts of things can go wrong: Bad programming,
bad compiler, power spike, etc.

--- Christopher Heckman

  #10   Report Post  
Old September 24th 07, 02:31 PM posted to rec.games.chess.misc,alt.chess,rec.games.chess.computer,alt.math.recreational
external usenet poster
 
First recorded activity by ChessBanter: Sep 2007
Posts: 51
Default Source for Eight Officers Problem?

rrock wrote:


Proginoskes wrote:

On Sep 23, 2:11 am, rrock wrote:

Proginoskes wrote:

Last night, I googled the Web for information about the Eight Officers
problem. (Put two rooks, two knights, two bishops, a queen, and a king
on a blank chessboard so that every square is attacked --- not just
occupied.) I found a solution where both bishops are on the same
colored square, and about a dozen positions where 63 squares are
attacked. The general consensus is that 63 is best possible, and that
the Eight Officers problem is impossible.

My question is this: Can anyone reference a book or a journal where a
full analysis of the impossibility of the Eight Officers appears? I am
seeking something along the lines of mathematical proof or a report of
doing brute force.

Thank you.

So were i to put together a brute force approach, just what sort of
report would you have it spit out?



The simple way would be an algorithm to look at all possible placings
of the pieces and then to output any arrangements that work; then the
lack of output would be the proof of the impossibility.

This is, of course, not the best possible proof, especially if you use
a computer, since all sorts of things can go wrong: Bad programming,
bad compiler, power spike, etc.

--- Christopher Heckman


Such an algorithm is trivial and could easily test itself.
I suspect that there would be quite a bit of pattern redundancy, so
how about sorting the outcomes on the number of total squares under
control. That way, rather than "no output", the sum of all output
could be used to prove that the program had tallied correctly (sort
of like balancing a ledger in accounting). The question then becomes
figuring out how many different possible patterns there actually
are.

When i first looked at it, it appeared that the total number of
possibilities would be 64^8, but that notion quickly faded when
realizing that some of the pieces being interchangable would
simply be a redundant case, and the bishops, of course, only
each have 32 possible positions.

Another thing is that since none of the pieces are bound to any
given direction (such as a pawn would be) there would automatically
be 4 different ways of representing numerically any given layout
(i.e. turning the board in any of the four directions, the pattern
of the pieces would be the same and yield the same output and thus
be simply another type of redundancy). This would still be true
even though the bishops would "change color" when representing
the pattern at 90 degrees since both of them would change color
as well as both of them controlling an identical number of squares
before and after the shift.


Imagine that we have a solution. Rotate the board so that the black
bishop is in the top left 4x4 quadrant. Two cases occur. Either it is on
the shared main diagonal (four positions) or it is not (12 positions).

In the former case, we have 32 positions for the white bishop, but a
reflection about the diagonal that the black bishop is on yields no
significantly different a solution.

In the latter case, we can reflect about the shared main diagonal
without significant change to the solution, but then all 32 positions of
the white bishop are significant.

Basically, reflections and rotations give us 256 significant bishop
patterns to examine, except that the above is black/white specific. Of
these, a proportion are symmetric wrt the pair, but the order of
magnitude is all I'm after, say 150 cases to consider. (I'm getting lazy).

Thereafter, we have essentially (62*61/2)*(60*59/2)*58*57 cases, for a
grand total of say 1,631,679,606,000 cases to examine.

While today's computers are pretty fast, this sounds a little time
consuming, but not at all impossible. I can certainly write a program
that solves in on my puny 1.6GHz P4 within a day, assuming about 85
machine cycles per inner loop,

If I had to produce a histogram of patterns by number of squares
attacked, I'd need a little more time.

Being ultra-lazy, and my brain is not working too brilliantly at the
moment, I think I'd like to establish a surer way of sorting out the
symmetry considerations, before launching into writing the program,
which in itself is rather trivial.

There are some heuristics that I'd probably use, if I didn't have to
count squares attacked below 60, say. That would be to place the king
and two horsies(1) last, and skip bothering with them if the final
squares attacked was never going to make it, wherever they went.

Sketch of program design...
Use 64 bit masks.
For each piece, pre-calculate a 64 entry table of the attack mask for
the places it could go.
Count bits in current mask by table lookup via its two 16 bit halves of
of pre-calculated bit counts,
Pretty simple eight nested loops.

(1) The Young Ones
--
Lau AS! d-(!) a++ c++++ p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++
ASC Decoder at http://www32.brinkster.com/ascdecode/
Reply
Thread Tools
Display Modes

Posting Rules

Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
Source for Anastasia's Mate problem? Frisco Del Rosario rec.games.chess.misc (Chess General) 1 August 21st 07 09:38 AM


All times are GMT +1. The time now is 06:33 AM.

Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Copyright 2004-2019 ChessBanter.
The comments are property of their posters.
 

About Us

"It's about Chess"

 

Copyright © 2017