Home 
Search 
Today's Posts 
#1




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




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: &&& May2604 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




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: &&& May2604 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




Source for Eight Officers Problem?
Den 20070920 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




Source for Eight Officers Problem?
On Sep 21, 9:18 am, "M Winther" wrote:
Den 20070920 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




Source for Eight Officers Problem?
Den 20070922 01:17:34 skrev Proginoskes :
On Sep 21, 9:18 am, "M Winther" wrote: Den 20070920 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




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




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 nontrivial (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




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




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 ultralazy, 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, precalculate 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 precalculated 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  


Similar Threads  
Thread  Forum  
Source for Anastasia's Mate problem?  rec.games.chess.misc (Chess General) 