Source for Eight Officers Problem?

Main

Date: 19 Sep 2007 23:03:03
From: Proginoskes
Subject: 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

Date: 20 Oct 2007 07:04:49
From: Proginoskes
Subject: Re: Two more puzzles: "100 Moves" and "36 Mates": Was: Re: Source for Eight Officers Problem?

On Oct 15, 2:21 pm, Peter Osterlund <[email protected] > wrote:
> Proginoskes <[email protected]> writes:
> >> Btw, this problems seems a lot easier to prove formally than the first
> >> "eight officers" problem. For example, I was able to prove that if
> >> there is a solution with >= 101 moves, then there is such a solution
> >> with a bishop on c3, d3 or d4. (Note that the theoretical max is 105,
> >> not 108.)
>
> > I must have mis-counted the maximum number of squares a bishop can
> > move to, then.
>
> You correctly wrote
>
> 8 + 27 + 13 + 13 + 8 + 8 + 14 + 14
>
> but that sum equals 105, not 108.
>
>
>
> >> > (2) Place any (but not necessarily?) all pieces (both colors) from a
> >> > standard chess set on the board so that the Black king is not in
> >> > check, but the number of moves which checkmate Black is maximized.
> >> > Dudeney has a position which produces 36 mates (below) in his
> >> > _Amusements in Mathematics_. I don't think you can brute-force this
> >> > one. 8-)
>
> >> > r1b2n1B/6R1/pQ1R3n/NpNB1p1p/1P1k1KpP/P1ppp1P1/2PPPP1b/r2q4
>
> >> That position uses all 32 pieces and the position seems to be
> >> reachable from the initial position. I can improve on the 36 by
> >> breaking those assumptions, but is that allowed?
>
> > Good question. Dudeney doesn't say one way or another (and he's dead,
> > so we can't ask him), but he said that "no one had been able to beat
> > [36]." He probably insisted on a "legal" position, seeing as how fast
> > you were able to beat 36.
>
> Just move the white b4 pawn to b2. Then there are two more possible
> mates, bxc3# and dxc3#. However, then there would be no way for the
> white bishop to have gotten away from the c1 square.
>
> If you are allowed to remove some pieces, you can remove Ra8, Bc8,
> Nf8, move the white rook from d6 to d8, move the white pawn from h4 to
> b2. Then another mate would be Qf6#.
>
> Also, if you remove Pg4, Bh2, Pg3, three additional mates are Rg3#,
> Rg2# and Rg1#. That would give a position with 42 mates.
>
> Looks like we finally found the question for which 42 is the answer :)

Well, maybe not ...

I did more digging in the back issues of Chess Life today. In Andy
Soltis's column "Chess to Enjoy" in the February 1981 issue, he
mentions four unsolved problems, three of which I've already mentioned
in this thread.

The fourth is DOUBLE STALEMATE: Construct a legal position with all 32
pieces and pawns so that neither side can move. The record was held by
Karl Fabel, who in 1947 constructed such a position with only one
possible move.

He calls the problem of a legal position with the most mates-in-one-
move MAXIMUM MATE [which I called "36 Mates"], and there is a position
with 47 mates, but not all the pieces are on the board. So 42 isn't
the answer (not expressed in base 10, anyway ... but you could hope
for base 13, where in fact 6*9=42).

The BREAKING 100 problem [which I called "100 Moves"] was proven (it
seems formally) independently by Paul Flore, Waye Pineault, and Chris
Ferrante [Aug 1981, CTE].

Wayne Pineault used a computer to show that the EIGHT OFFICERS problem
was unsolvable. The machine took 400 hours to run [Feb 1984, CTE].

As of ch, 1984, that's where it stands; two down, two to go.

[To be continued...]

--- Christopher Heckman

Date: 15 Oct 2007 07:54:50
From: Proginoskes
Subject: Re: Two more puzzles: "100 Moves" and "36 Mates": Was: Re: Source for Eight Officers Problem?

On Oct 14, 7:32 am, Peter Osterlund <[email protected] > wrote:
> Proginoskes <[email protected]> writes:
> > (1) Arrange the "eight officers" (king, queen, 2 bishops -- opposite
> > colors, 2 knights, 2 rooks) on an otherwise blank board so that the
> > total number of moves is maximized. (This is not the same problem as
> > the Eight Officers problem, since a square attacked by two or more
> > pieces is counted twice.) An arrangement giving 100 moves ---
> > purported to be the answer --- is given below in FEN notation. (Yeah,
> > I know that's redundant ...) There is also a variation that also has
> > 100 moves. As of 1980, this problem was unsolved. (This is another old
> > problem, from 1848.)
>
> > Note that the maximum is at most 8 + 27 + 13 + 13 + 8 + 8 + 14 + 14 =
> > 108 (obtained by adding the maximum number of squares that a piece
> > attacks; however, not all pieces can be placed optimally). And you
> > don't need to bother counting castling; no maximum solution has the
> > possibility of castling.
>
> > FEN: 8/2R5/3N4/6R1/3BBN2/1Q6/3K4/8
> > (Seehttp://en.wikipedia.org/wiki/FEN)
>
> That problem is very easy for a computer. A simple and very efficient
> B&B rule is:
>
> The already available moves + the theretical maximum for the
> remaining pieces must be at least as large as the best solution
> found so far.
>
> Using that rule, the search space basically vanishes, and after a 30ms
> calculation (on only one CPU), the program concludes that the best
> possible is 100 moves, and that there are two solutions. The first one
> is the one you gave and the second one can be obtained from the first
> by moving just one rook.

Yes, to a5, I think.

> Btw, this problems seems a lot easier to prove formally than the first
> "eight officers" problem. For example, I was able to prove that if
> there is a solution with >= 101 moves, then there is such a solution
> with a bishop on c3, d3 or d4. (Note that the theoretical max is 105,
> not 108.)

I must have mis-counted the maximum number of squares a bishop can
move to, then.

> > (2) Place any (but not necessarily?) all pieces (both colors) from a
> > standard chess set on the board so that the Black king is not in
> > check, but the number of moves which checkmate Black is maximized.
> > Dudeney has a position which produces 36 mates (below) in his
> > _Amusements in Mathematics_. I don't think you can brute-force this
> > one. 8-)
>
> > r1b2n1B/6R1/pQ1R3n/NpNB1p1p/1P1k1KpP/P1ppp1P1/2PPPP1b/r2q4
>
> That position uses all 32 pieces and the position seems to be
> reachable from the initial position. I can improve on the 36 by
> breaking those assumptions, but is that allowed?

Good question. Dudeney doesn't say one way or another (and he's dead,
so we can't ask him), but he said that "no one had been able to beat
[36]." He probably insisted on a "legal" position, seeing as how fast
you were able to beat 36. Promotions, and underpromitions, are
probably okay as well.

I suspect the problem is already hard enough without insisting on
legality; you would need retrograde analysis to determine whether a
position is legal. (Of course, if you find out it _is_ legal,
constructing a game would be the only necessary proof. But you would
need to answer the question first.)

--- Christopher Heckman

Date: 15 Oct 2007 21:21:27
From: Peter Osterlund
Subject: Re: Two more puzzles: "100 Moves" and "36 Mates": Was: Re: Source for Eight Officers Problem?

Proginoskes <[email protected] > writes:

>> Btw, this problems seems a lot easier to prove formally than the first
>> "eight officers" problem. For example, I was able to prove that if
>> there is a solution with >= 101 moves, then there is such a solution
>> with a bishop on c3, d3 or d4. (Note that the theoretical max is 105,
>> not 108.)
>
> I must have mis-counted the maximum number of squares a bishop can
> move to, then.

You correctly wrote

8 + 27 + 13 + 13 + 8 + 8 + 14 + 14

but that sum equals 105, not 108.

>> > (2) Place any (but not necessarily?) all pieces (both colors) from a
>> > standard chess set on the board so that the Black king is not in
>> > check, but the number of moves which checkmate Black is maximized.
>> > Dudeney has a position which produces 36 mates (below) in his
>> > _Amusements in Mathematics_. I don't think you can brute-force this
>> > one. 8-)
>>
>> > r1b2n1B/6R1/pQ1R3n/NpNB1p1p/1P1k1KpP/P1ppp1P1/2PPPP1b/r2q4
>>
>> That position uses all 32 pieces and the position seems to be
>> reachable from the initial position. I can improve on the 36 by
>> breaking those assumptions, but is that allowed?
>
> Good question. Dudeney doesn't say one way or another (and he's dead,
> so we can't ask him), but he said that "no one had been able to beat
> [36]." He probably insisted on a "legal" position, seeing as how fast
> you were able to beat 36.

Just move the white b4 pawn to b2. Then there are two more possible
mates, bxc3# and dxc3#. However, then there would be no way for the
white bishop to have gotten away from the c1 square.

If you are allowed to remove some pieces, you can remove Ra8, Bc8,
Nf8, move the white rook from d6 to d8, move the white pawn from h4 to
b2. Then another mate would be Qf6#.

Also, if you remove Pg4, Bh2, Pg3, three additional mates are Rg3#,
Rg2# and Rg1#. That would give a position with 42 mates.

Looks like we finally found the question for which 42 is the answer :)

> I suspect the problem is already hard enough without insisting on
> legality; you would need retrograde analysis to determine whether a
> position is legal. (Of course, if you find out it _is_ legal,
> constructing a game would be the only necessary proof. But you would
> need to answer the question first.)

Agreed. I don't see how to solve this problem using brute force in a
reasonable amount of time.

--
Peter Osterlund - [email protected]
http://web.telia.com/~u89404340

Date: 14 Oct 2007 09:13:02
From: Proginoskes
Subject: Two more puzzles: "100 Moves" and "36 Mates": Was: Re: Source for Eight Officers Problem?

On Sep 19, 4:03 pm, Proginoskes <[email protected] > 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.

On Saturday, I went through the back issues of Chess Life up through
1980 at the local public library; still no mention of the Eight
Officers problem. I hope to get back in the next few weeks and search
some more.

For those of you who liked working on this problem, here are a couple
more in this vein. The first one should be a slight variation, in
terms of programming. The second will be much more difficult.

(1) Arrange the "eight officers" (king, queen, 2 bishops -- opposite
colors, 2 knights, 2 rooks) on an otherwise blank board so that the
total number of moves is maximized. (This is not the same problem as
the Eight Officers problem, since a square attacked by two or more
pieces is counted twice.) An arrangement giving 100 moves ---
purported to be the answer --- is given below in FEN notation. (Yeah,
I know that's redundant ...) There is also a variation that also has
100 moves. As of 1980, this problem was unsolved. (This is another old
problem, from 1848.)

Note that the maximum is at most 8 + 27 + 13 + 13 + 8 + 8 + 14 + 14 =
108 (obtained by adding the maximum number of squares that a piece
attacks; however, not all pieces can be placed optimally). And you
don't need to bother counting castling; no maximum solution has the
possibility of castling.

FEN: 8/2R5/3N4/6R1/3BBN2/1Q6/3K4/8
(See http://en.wikipedia.org/wiki/FEN )

(2) Place any (but not necessarily?) all pieces (both colors) from a
standard chess set on the board so that the Black king is not in
check, but the number of moves which checkmate Black is maximized.
Dudeney has a position which produces 36 mates (below) in his
_Amusements in Mathematics_. I don't think you can brute-force this
one. 8-)

r1b2n1B/6R1/pQ1R3n/NpNB1p1p/1P1k1KpP/P1ppp1P1/2PPPP1b/r2q4

--- Christopher Heckman

Date: 14 Oct 2007 14:32:14
From: Peter Osterlund
Subject: Re: Two more puzzles: "100 Moves" and "36 Mates": Was: Re: Source for Eight Officers Problem?

Proginoskes <[email protected] > writes:

> (1) Arrange the "eight officers" (king, queen, 2 bishops -- opposite
> colors, 2 knights, 2 rooks) on an otherwise blank board so that the
> total number of moves is maximized. (This is not the same problem as
> the Eight Officers problem, since a square attacked by two or more
> pieces is counted twice.) An arrangement giving 100 moves ---
> purported to be the answer --- is given below in FEN notation. (Yeah,
> I know that's redundant ...) There is also a variation that also has
> 100 moves. As of 1980, this problem was unsolved. (This is another old
> problem, from 1848.)
>
> Note that the maximum is at most 8 + 27 + 13 + 13 + 8 + 8 + 14 + 14 =
> 108 (obtained by adding the maximum number of squares that a piece
> attacks; however, not all pieces can be placed optimally). And you
> don't need to bother counting castling; no maximum solution has the
> possibility of castling.
>
> FEN: 8/2R5/3N4/6R1/3BBN2/1Q6/3K4/8
> (See http://en.wikipedia.org/wiki/FEN )

That problem is very easy for a computer. A simple and very efficient
B&B rule is:

The already available moves + the theretical maximum for the
remaining pieces must be at least as large as the best solution
found so far.

Using that rule, the search space basically vanishes, and after a 30ms
calculation (on only one CPU), the program concludes that the best
possible is 100 moves, and that there are two solutions. The first one
is the one you gave and the second one can be obtained from the first
by moving just one rook.

Btw, this problems seems a lot easier to prove formally than the first
"eight officers" problem. For example, I was able to prove that if
there is a solution with >= 101 moves, then there is such a solution
with a bishop on c3, d3 or d4. (Note that the theoretical max is 105,
not 108.)

> (2) Place any (but not necessarily?) all pieces (both colors) from a
> standard chess set on the board so that the Black king is not in
> check, but the number of moves which checkmate Black is maximized.
> Dudeney has a position which produces 36 mates (below) in his
> _Amusements in Mathematics_. I don't think you can brute-force this
> one. 8-)
>
> r1b2n1B/6R1/pQ1R3n/NpNB1p1p/1P1k1KpP/P1ppp1P1/2PPPP1b/r2q4

That position uses all 32 pieces and the position seems to be
reachable from the initial position. I can improve on the 36 by
breaking those assumptions, but is that allowed?

--
Peter Osterlund - [email protected]
http://web.telia.com/~u89404340

Date: 08 Oct 2007 06:07:45
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?

On Oct 7, 6:39 am, Peter Osterlund <[email protected] > wrote:
> Proginoskes <[email protected]> writes:
> > First of all, Laurence Reeves's algorithm is branch-and-bound (which
> > he originally called "heuristic"). Second, he can't produce histogram
> > data _for all values of N_, where N is the number of squares covered.
> > After he places the queen, bishops, and rooks, he counts how many
> > squares are not attacked, and if this number is greater than 24, he
> > doesn't bother with placing the king and knights, since these pieces
> > can attack at most 24 squares.* Thus, the histogram data will be
> > incorrect for N < 40. However, for larger values of N, it will be
> > correct, because he does check all cases.
>
> > * This number is smaller in some configurations, and in some cases,
> > the king and or a knight might block a piece's attack, but the latter
> > will only increase the number of squares that need to be attacked. He
> > does a slightly more clever check: He counts how many black squares
> > and how many white squares are not attacked. A king and two knights
> > can attack at most 12 white (resp. black) squares, which will catch
> > more of the "hopeless" cases before trying all possibilities for the
> > king and 2 knights.
>
> A king and two knights can attack at least 19 white squares.

SMACK!!! (That was directed at my forehead.)

Yes; I just divided 24 by 12. It should have been: king and two
knights can attack at most 8+8+4 = 20 white squares, since.the squares
that the knight attacks are all of the same color (opposite from where
the knight is).

Actually, it will be at most (20 of one color and 4 of the other
color), or at most 12 of each.

--- Christopher Heckman

> Is this a bug in the branch and bound implementation, or was your
> description just simplified in some way?
>
> (I actually implemented your description in my program before
> realizing this problem, but the program found 144 63-solutions
> anyway.)

Date: 03 Oct 2007 22:18:38
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?

On Oct 3, 2:08 pm, [email protected] wrote:
> In one of the previous posts, I believe you mentioned that all of the
> 63 square solutions had the Queen on a d4 type square. I'm wondering
> if it might be possible to prove that having the Queen on a d4 type
> square is superior than having the Queen anywhere else. If this proof
> were not too difficult, you'd only need to run through the cases where
> the Queen is on a d4 type square. There would still be an awful lot
> of cases to consider though, wouldn't there?

Yes, it would help, and yes the number of cases will be in the
hundreds of billions (about 10^11) instead of about 12 trillion (the
1.2 * 10^13 number I derived elsewhere in this post).

> Maybe there's some other observations that could be made about the
> placement of the pieces that could cut down the number of cases you
> need to consider.

This is actually along the lines of one of my suggestions earlier:
that you could prove some results that say: "If you have all 64
squares covered, then [certain piece] has to be on [certain square or
set of squares]." If you could establish that five of the eight pieces
had to be on certain squares, then the computer search wouldn't be so
bad, and you've moved away from a "computer proof" of the result to a
"computer-assisted proof" (where the computer searched through a lot
of cases, which suggested the way to the proof) of the result.

I think there will still have to be a computer search *somewhere*,
mostly because otherwise the problem would have been solved much
earlier. (Some 63-square solutions go back to the 1930s; this is an
OLD problem. It would be nice to find out who first asked it, as part
of the "official report".)

--- Christopher Heckman

Date: 03 Oct 2007 14:08:44
From:
Subject: Re: Source for Eight Officers Problem?

In one of the previous posts, I believe you mentioned that all of the
63 square solutions had the Queen on a d4 type square. I'm wondering
if it might be possible to prove that having the Queen on a d4 type
square is superior than having the Queen anywhere else. If this proof
were not too difficult, you'd only need to run through the cases where
the Queen is on a d4 type square. There would still be an awful lot
of cases to consider though, wouldn't there?

Maybe there's some other observations that could be made about the
placement of the pieces that could cut down the number of cases you
need to consider.

Date: 01 Oct 2007 21:57:26
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?

On Oct 1, 5:12 am, Laurence Reeves <[email protected] > wrote:
> Proginoskes wrote:
> > ... First of all, Laurence Reeves's algorithm is branch-and-bound (which
> > he originally called "heuristic"). ...
>
> A minor "point of order". I never called my method "heuristic". I went
> to some pains to explain that, to me, a "heuristic" approach would mean
> "not guaranteed to find all solutions". It might find 144 solutions, but
> could only EVER give that as a lower bound (unless there happened to be
> some a priori reason why it was known that there were exactly 144
> solutions). I use an algorithm (to find *the* solutions to the problem)
> not a heuristic (to maybe find *some* solutions to the problem).
>
> Having never come across the terminology of "branch and bound" before, I
> looked it up.
>
> Technically, I'm not sure that my algorithm is that either, as it does
> not do any branching.

The branching is done when you decide which square a certain piece
goes on. It's like a proof "by cases", where each possibility is
considered.

> I suppose you can interpret it that way, in that I
> progress each time from one specific (branched?) layout of five, six or
> seven pieces, and discard (bound) by rejecting further processing of a
> partial layout if it is provably not able to produce any solutions to
> the problem at hand (i.e. coverings of >= 63 squares).

Yes, that's exactly how I'm interpretting it. And, as a consequence,
each arrangement of chesspieces will either be (a) rejected because
fewer than 40 squares will covered,* or (b) accepted and counted in
the histogram. So this algorithm won't give correct results for the
number of ways to place the pieces so that exactly 20 squares are
attacked, but it will for the number of ways where 45 are attacked.

* I'm leaving out the discussion involving black and white squares,
for clarity's sake.

> Another distinction from "branch and bound" might be that my algorithm
> is exact and guaranteed to terminate, whereas B&B seems not to imply
> that it should go that far.

An algorithm terminates (by definition). And algorithms also solve
their problem (by definition). "Programs" or "code" might not.

--- Christopher Heckman

Date: 02 Oct 2007 00:34:48
From: Laurence Reeves
Subject: Re: Source for Eight Officers Problem?

Proginoskes wrote:
> ... An algorithm terminates (by definition). And algorithms also solve
> their problem (by definition). "Programs" or "code" might not.

:)

An algorithm, by definition, does not necessarily terminate. I can quite
happily give you an algorithm for calculating the decimal expansion of
pi. It does not terminate.

I can also give an algorithm for calculating the decimal expansion of
2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2. It
could terminate, but it won't.

Also, to quote Wikipedia "The analysis of algorithms for their
likelihood of termination is called Termination analysis."

Algorithms do NOT necessarily solve their problems. They are techniques
that maybe /intend/ to solve a problem. An algorithm doesn't cease to be
an algorithm just because it fails to solve the problem is was meant to
solve. It may even solve a different problem, which it transpires was a
good problem to have solved.

Indeed, an algorithm may not have any specific aim in view. I can
present an algorithm for constructing things out of bricks, without
having a specific problem to solve (building to construct).

My, ain't terminology fun.

OED. 2. Math. A process, or set of rules, usually one expressed in
algebraic notation, now used esp. in computing, machine translation and
linguistics.

Merriam-Webster leans toward your definition(?), but that seems silly,
to me. It means that you do not have a word to describe what I call an
algorithm, until you have shown that it terminates and gets the correct
solution to a particular problem.

--
Lau AS! d-(!) a++ c++++ p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++
ASC Decoder at <http://www32.brinkster.com/ascdecode/ >

Date: 01 Oct 2007 05:57:06
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?

On Sep 30, 12:17 am, Peter Osterlund <[email protected] > wrote:
> Proginoskes <[email protected]> writes:
> > On Sep 29, 2:31 pm, Peter Osterlund <[email protected]> wrote:
>
> >> My brute force program is currently running on a 2.4GHz Intel Core 2
> >> Quad computer in 64 bit mode at a speed of approximately 120 million
> >> positions per second. Since I didn't implement any symmetry detection
> >> at all, the search space size is about 1.13e13, which means that the
> >> computation should be finished in about 26 hours.
>
> >> The output will be the histogram data and the "maximum" positions.
> >> (Actually split up in 32 files because of how I implemented the
> >> parallel search and checkpointing, but merging should be simple.)
>
> > The code Laurence Reeves sent me took two hours (plus or minus 30
> > seconds) unmodified. I got a couple of basic ideas for speeding up the
> > process and have started another run. No information on processor
> > speed at the moment, though. (I got a new computer a few weeks ago.)
>
> I might be wrong, but I thought his program was using branch and
> bound, and was therefore not able to produce the histogram data.

First of all, Laurence Reeves's algorithm is branch-and-bound (which
he originally called "heuristic"). Second, he can't produce histogram
data _for all values of N_, where N is the number of squares covered.
After he places the queen, bishops, and rooks, he counts how many
squares are not attacked, and if this number is greater than 24, he
doesn't bother with placing the king and knights, since these pieces
can attack at most 24 squares.* Thus, the histogram data will be
incorrect for N < 40. However, for larger values of N, it will be
correct, because he does check all cases.

* This number is smaller in some configurations, and in some cases,
the king and or a knight might block a piece's attack, but the latter
will only increase the number of squares that need to be attacked. He
does a slightly more clever check: He counts how many black squares
and how many white squares are not attacked. A king and two knights
can attack at most 12 white (resp. black) squares, which will catch
more of the "hopeless" cases before trying all possibilities for the
king and 2 knights.

> Also, if I were to consider symmetries, I think it would be possible
> to cut down the run time to about 4 hours by only considering 10
> squares for the king. However, that would produce a different
> histogram.

Yes, because you can't get as good of a bound on the number of squares
that the last 3 pieces can attack, which will require more case-
checking and more configurations. The numbers near the top should be
the same, though.

--- Christopher Heckman

Date: 07 Oct 2007 13:39:47
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?

Proginoskes <[email protected] > writes:

> First of all, Laurence Reeves's algorithm is branch-and-bound (which
> he originally called "heuristic"). Second, he can't produce histogram
> data _for all values of N_, where N is the number of squares covered.
> After he places the queen, bishops, and rooks, he counts how many
> squares are not attacked, and if this number is greater than 24, he
> doesn't bother with placing the king and knights, since these pieces
> can attack at most 24 squares.* Thus, the histogram data will be
> incorrect for N < 40. However, for larger values of N, it will be
> correct, because he does check all cases.
>
> * This number is smaller in some configurations, and in some cases,
> the king and or a knight might block a piece's attack, but the latter
> will only increase the number of squares that need to be attacked. He
> does a slightly more clever check: He counts how many black squares
> and how many white squares are not attacked. A king and two knights
> can attack at most 12 white (resp. black) squares, which will catch
> more of the "hopeless" cases before trying all possibilities for the
> king and 2 knights.

A king and two knights can attack at least 19 white squares. For
example, Nc3, Ne5, Kg2 will attack:

b1,d1,e2,e4,d5,b5,a4,a2,
d3,f3,g4,g6,f7,d7,c6,c4,
f1,h1,h3

Is this a bug in the branch and bound implementation, or was your
description just simplified in some way?

(I actually implemented your description in my program before
realizing this problem, but the program found 144 63-solutions
anyway.)

--
Peter Osterlund - [email protected]
http://web.telia.com/~u89404340

Date: 07 Oct 2007 14:43:22
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?

Peter Osterlund <[email protected] > writes:

> Proginoskes <[email protected]> writes:
>
>> First of all, Laurence Reeves's algorithm is branch-and-bound (which
>> he originally called "heuristic"). Second, he can't produce histogram
>> data _for all values of N_, where N is the number of squares covered.
>> After he places the queen, bishops, and rooks, he counts how many
>> squares are not attacked, and if this number is greater than 24, he
>> doesn't bother with placing the king and knights, since these pieces
>> can attack at most 24 squares.* Thus, the histogram data will be
>> incorrect for N < 40. However, for larger values of N, it will be
>> correct, because he does check all cases.
>>
>> * This number is smaller in some configurations, and in some cases,
>> the king and or a knight might block a piece's attack, but the latter
>> will only increase the number of squares that need to be attacked. He
>> does a slightly more clever check: He counts how many black squares
>> and how many white squares are not attacked. A king and two knights
>> can attack at most 12 white (resp. black) squares, which will catch
>> more of the "hopeless" cases before trying all possibilities for the
>> king and 2 knights.
>
> A king and two knights can attack at least 19 white squares. For
> example, Nc3, Ne5, Kg2 will attack:
>
> b1,d1,e2,e4,d5,b5,a4,a2,
> d3,f3,g4,g6,f7,d7,c6,c4,
> f1,h1,h3

I implemented the following B&B rule instead:

// Return true if it is found to be impossible to get at least numWanted
// squares attacked by placing numKnights knights and one king, if the
// number of already attacked squares is given by whiteAttacked and
// blackAttacked.
static inline bool
hopeless(int numWanted, int whiteAttacked, int blackAttacked, int numKnights)
{
if (whiteAttacked + blackAttacked + numKnights * 8 + 8 < numWanted)
return true;
int minAttacked = std::min(whiteAttacked, blackAttacked);
int minNeeded = numWanted - 32;
if (minAttacked + 8 * numKnights + 4 < minNeeded)
return true;
return false;
}

With that rule, finding all 64-solutions (ie 0) takes 39 seconds and
finding all 63-solutions (ie 144) takes 64 seconds. This is on the
2.4GHz Core 2 Quad machine. On a 3GHz P4 machine, the program runs
about 8 times slower.

The updated program is available here:

http://web.telia.com/~u89404340/officer2.tar.bz2

--
Peter Osterlund - [email protected]
http://web.telia.com/~u89404340

Date: 09 Oct 2007 05:09:28
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?

Peter Osterlund <[email protected] > writes:

> I implemented the following B&B rule instead:
>
> static inline bool
> hopeless(int numWanted, int whiteAttacked, int blackAttacked, int numKnights)
> {
> if (whiteAttacked + blackAttacked + numKnights * 8 + 8 < numWanted)
> return true;
> int minAttacked = std::min(whiteAttacked, blackAttacked);
> int minNeeded = numWanted - 32;
> if (minAttacked + 8 * numKnights + 4 < minNeeded)
> return true;
> return false;
> }

That rule is quite inefficient though. New rule:

static inline bool
hopeless(int numWanted, int whiteAttacked, int blackAttacked, int numKnights)
{
for (int whiteKnights = 0; whiteKnights <= numKnights; whiteKnights++) {
int blackKnights = numKnights - whiteKnights;
int white = whiteAttacked + whiteKnights * 8 + 4;
int black = blackAttacked + blackKnights * 8 + 4;
if (std::min(white, 32) + std::min(black, 32) >= numWanted)
return false;
}
return true;
}

With that rule, finding all 64-solutions takes 8 seconds and finding
all 63-solutions takes 20 seconds.

--
Peter Osterlund - [email protected]
http://web.telia.com/~u89404340

Date: 09 Oct 2007 05:07:47
From: =?ISO-8859-1?Q?=AA=BA=AA_rrock?=
Subject: Re: Source for Eight Officers Problem?

Peter Osterlund wrote:
> Peter Osterlund <[email protected]> writes:
>
>
>>I implemented the following B&B rule instead:
>>
>> static inline bool
>> hopeless(int numWanted, int whiteAttacked, int blackAttacked, int numKnights)
>> {
>> if (whiteAttacked + blackAttacked + numKnights * 8 + 8 < numWanted)
>> return true;
>> int minAttacked = std::min(whiteAttacked, blackAttacked);
>> int minNeeded = numWanted - 32;
>> if (minAttacked + 8 * numKnights + 4 < minNeeded)
>> return true;
>> return false;
>> }
>
>
> That rule is quite inefficient though. New rule:
>
> static inline bool
> hopeless(int numWanted, int whiteAttacked, int blackAttacked, int numKnights)
> {
> for (int whiteKnights = 0; whiteKnights <= numKnights; whiteKnights++) {
> int blackKnights = numKnights - whiteKnights;
> int white = whiteAttacked + whiteKnights * 8 + 4;
> int black = blackAttacked + blackKnights * 8 + 4;
> if (std::min(white, 32) + std::min(black, 32) >= numWanted)
> return false;
> }
> return true;
> }
>
> With that rule, finding all 64-solutions takes 8 seconds and finding
> all 63-solutions takes 20 seconds.
>

It looks like you are getting closer to a formal proof. Why does it take
8 seconds to find zero solutions? A formal proof would find zero solutions
in zero seconds.

Date: 09 Oct 2007 19:01:37
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?

ªºª rrock <[email protected] > writes:

> Peter Osterlund wrote:
>> Peter Osterlund <[email protected]> writes:
>>
>>
>>>I implemented the following B&B rule instead:
>>>
>>> static inline bool
>>> hopeless(int numWanted, int whiteAttacked, int blackAttacked, int numKnights)
>>> {
>>> if (whiteAttacked + blackAttacked + numKnights * 8 + 8 < numWanted)
>>> return true;
>>> int minAttacked = std::min(whiteAttacked, blackAttacked);
>>> int minNeeded = numWanted - 32;
>>> if (minAttacked + 8 * numKnights + 4 < minNeeded)
>>> return true;
>>> return false;
>>> }
>>
>>
>> That rule is quite inefficient though. New rule:
>>
>> static inline bool
>> hopeless(int numWanted, int whiteAttacked, int blackAttacked, int numKnights)
>> {
>> for (int whiteKnights = 0; whiteKnights <= numKnights; whiteKnights++) {
>> int blackKnights = numKnights - whiteKnights;
>> int white = whiteAttacked + whiteKnights * 8 + 4;
>> int black = blackAttacked + blackKnights * 8 + 4;
>> if (std::min(white, 32) + std::min(black, 32) >= numWanted)
>> return false;
>> }
>> return true;
>> }
>>
>> With that rule, finding all 64-solutions takes 8 seconds and finding
>> all 63-solutions takes 20 seconds.
>
> It looks like you are getting closer to a formal proof. Why does it take
> 8 seconds to find zero solutions? A formal proof would find zero solutions
> in zero seconds.

It takes 8 seconds because the program has to analyze 36202866
positions. All other positions are discarded by the B&B rule and the
symmetry discarding logic. The result is the following incomplete
histogram:

43 5
44 14
45 35
46 203
47 830
48 2365
49 6247
50 13674
51 31684
52 137021
53 605595
54 1674620
55 3284892
56 9405862
57 11132660
58 6811766
59 2456563
60 559083
61 74414
62 5224
63 109
64 0

This shows (together with a proof that the program, compiler, cpu, etc
is correct) that there is no 64-solution to the problem.

However, it's still quite far away from a formal proof. Analyzing
those 36 million positions by hand and proving that the other
1416336714894 positions can be safely ignored, would probably take a
human being more than a lifetime.

--
Peter Osterlund - [email protected]
http://web.telia.com/~u89404340

Date: 09 Oct 2007 15:24:15
From: =?UTF-8?B?wqrCusKqIHJyb2Nr?=
Subject: Re: Source for Eight Officers Problem?

Peter Osterlund wrote:

> ªºª rrock <[email protected]> writes:
>
>
>>Peter Osterlund wrote:
>>
>>>Peter Osterlund <[email protected]> writes:
>>>
>>>
>>>
>>>>I implemented the following B&B rule instead:
>>>>
>>>> static inline bool
>>>> hopeless(int numWanted, int whiteAttacked, int blackAttacked, int numKnights)
>>>> {
>>>> if (whiteAttacked + blackAttacked + numKnights * 8 + 8 < numWanted)
>>>> return true;
>>>> int minAttacked = std::min(whiteAttacked, blackAttacked);
>>>> int minNeeded = numWanted - 32;
>>>> if (minAttacked + 8 * numKnights + 4 < minNeeded)
>>>> return true;
>>>> return false;
>>>> }
>>>
>>>
>>>That rule is quite inefficient though. New rule:
>>>
>>> static inline bool
>>> hopeless(int numWanted, int whiteAttacked, int blackAttacked, int numKnights)
>>> {
>>> for (int whiteKnights = 0; whiteKnights <= numKnights; whiteKnights++) {
>>> int blackKnights = numKnights - whiteKnights;
>>> int white = whiteAttacked + whiteKnights * 8 + 4;
>>> int black = blackAttacked + blackKnights * 8 + 4;
>>> if (std::min(white, 32) + std::min(black, 32) >= numWanted)
>>> return false;
>>> }
>>> return true;
>>> }
>>>
>>>With that rule, finding all 64-solutions takes 8 seconds and finding
>>>all 63-solutions takes 20 seconds.
>>
>>It looks like you are getting closer to a formal proof. Why does it take
>>8 seconds to find zero solutions? A formal proof would find zero solutions
>>in zero seconds.
>
>
> It takes 8 seconds because the program has to analyze 36202866
> positions. All other positions are discarded by the B&B rule and the
> symmetry discarding logic. The result is the following incomplete
> histogram:
>
> 43 5
> 44 14
> 45 35
> 46 203
> 47 830
> 48 2365
> 49 6247
> 50 13674
> 51 31684
> 52 137021
> 53 605595
> 54 1674620
> 55 3284892
> 56 9405862
> 57 11132660
> 58 6811766
> 59 2456563
> 60 559083
> 61 74414
> 62 5224
> 63 109
> 64 0
>
> This shows (together with a proof that the program, compiler, cpu, etc
> is correct) that there is no 64-solution to the problem.
>
> However, it's still quite far away from a formal proof. Analyzing
> those 36 million positions by hand and proving that the other
> 1416336714894 positions can be safely ignored, would probably take a
> human being more than a lifetime.

I don't know about that. I don't think your catching my drift, either.
The first time anything at all about a histogram or symmetry was mentioned,
it was in regards to my questions on what was originally asked for. And
during the interim of then and now, a number of people have had a number
of different inputs on just what is or isn't worthwhile, what is or isn't
symmetry, or even how many cases were actually under "formal" consideration.

Your program is *not* by any means a brute force program, rather, it is
a tool that is helping you whittle down that larger number, and you and
others have made quite a few small discoveries in what, only a week or
so? Each of those little rules is a small part of the ultimate formal
proof. I don't think you're giving yourself or the group interested in
this thread as much credit as you deserve and/or are underestimating the
combined capabilities. As a programmer you should be looking at the rules
mathematically to discover those small underlying logic clues that lead
to bigger revelations. You're not giving up, are you?

By the way, completely on a different note, did i miss something earlier
or is there a reason 63 has only 109 cases now instead of the 144? If i
missed that post, please let me know. I'd hate to find my old dog over
here had come up with 109 after a month of waiting, figure i screwed up
and... lol delete the files. Was the 144 with or without symmetry? That
still wouldn't make sense. Let me know. I understand the histogram is
incomplete, but i don't understand how it could not fill in all of the
63 coverage states and still be competent enough to say it had checked
all of the 64's. If that is correct, and the 144 still hasn't changed,
then THERE is a heap of data for checking out regarding another rule.
For example, which of the 63's has it forsaken, and WHY? Any pattern?
(even a plaid pattern for egg-heads?). Quit worrying about the 36 million
positions and pay attention to the 109. Just my two cents.

>

Date: 09 Oct 2007 21:59:59
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?

ªºª rrock <[email protected] > writes:

> Peter Osterlund wrote:
>
>> It takes 8 seconds because the program has to analyze 36202866
>> positions. All other positions are discarded by the B&B rule and the
>> symmetry discarding logic. The result is the following incomplete
>> histogram:
...
>> This shows (together with a proof that the program, compiler, cpu, etc
>> is correct) that there is no 64-solution to the problem.
>>
>> However, it's still quite far away from a formal proof. Analyzing
>> those 36 million positions by hand and proving that the other
>> 1416336714894 positions can be safely ignored, would probably take a
>> human being more than a lifetime.
>
> I don't know about that. I don't think your catching my drift, either.
> The first time anything at all about a histogram or symmetry was mentioned,
> it was in regards to my questions on what was originally asked for. And
> during the interim of then and now, a number of people have had a number
> of different inputs on just what is or isn't worthwhile, what is or isn't
> symmetry, or even how many cases were actually under "formal" consideration.
>
> Your program is *not* by any means a brute force program, rather, it is
> a tool that is helping you whittle down that larger number, and you and
> others have made quite a few small discoveries in what, only a week or
> so? Each of those little rules is a small part of the ultimate formal
> proof. I don't think you're giving yourself or the group interested in
> this thread as much credit as you deserve and/or are underestimating the
> combined capabilities. As a programmer you should be looking at the rules
> mathematically to discover those small underlying logic clues that lead
> to bigger revelations. You're not giving up, are you?

I haven't given up on making my program faster, but unfortunately I
don't see much hope in transforming my program into a formal proof
short enough to be verified by a human without computer help.

One idea I'm planning to test is to first let the program spend some
time computing more efficient B&B rules, then use those rules to
further reduce the number of positions it needs to evaluate.

> By the way, completely on a different note, did i miss something earlier
> or is there a reason 63 has only 109 cases now instead of the 144? If i
> missed that post, please let me know. I'd hate to find my old dog over
> here had come up with 109 after a month of waiting, figure i screwed up
> and... lol delete the files. Was the 144 with or without symmetry? That
> still wouldn't make sense. Let me know. I understand the histogram is
> incomplete, but i don't understand how it could not fill in all of the
> 63 coverage states and still be competent enough to say it had checked
> all of the 64's. If that is correct, and the 144 still hasn't changed,
> then THERE is a heap of data for checking out regarding another rule.
> For example, which of the 63's has it forsaken, and WHY? Any pattern?
> (even a plaid pattern for egg-heads?). Quit worrying about the 36 million
> positions and pay attention to the 109. Just my two cents.

There are indeed 144 solutions, but in some cases the program can
realize after placing all pieces except the king that there is no
point placing the king, because it is impossible to attack all 64
squares. In that case, the program doesn't test all available king
positions, even though some of those positions might lead to a
63-solution.

An example:

......R.
.......R
........
.K......
..B.....
...Q....
.B....N.
...N....

In this position, all squares except g1 are attacked. However, if you
remove the king, the squares a5, b4, b6, c5 are also unattacked. All
those five squares are black, and the program knows that a king can
only attack at most 4 black squares. Therefore it doesn't even try to
place the king, which means that it will not find the 63-solution.

--
Peter Osterlund - [email protected]
http://web.telia.com/~u89404340

Date: 14 Oct 2007 12:00:45
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?

Peter Osterlund <[email protected] > writes:

> I haven't given up on making my program faster, but unfortunately I
> don't see much hope in transforming my program into a formal proof
> short enough to be verified by a human without computer help.
>
> One idea I'm planning to test is to first let the program spend some
> time computing more efficient B&B rules, then use those rules to
> further reduce the number of positions it needs to evaluate.

I implemented this idea. The program starts by computing the following
array:

unsigned char numUnAttackedByKnights_[65536];

If the attacked squares on two adjacent rows on the board are given by
"mask" (16 bits), numUnAttackedByKnights_[mask] equals the minimum
number of remaining unattacked squares on those two rows, when the
knights are allowed to be placed anywhere on the board.

During the search, after placing BBQRR, the array is used to find out
how many more squares the king is required to attack on rows 1-2, 3-4,
5-6 and 7-8. Using the fact that the king can only attack squares in
at most two of the four regions, about 70% of the positions can be
pruned. (The old pruning rule that considered the maximum number of
white and black squares possible to attack with N knights and a king
is also used.)

With the above rule, finding all 64-solutions takes 4.4 seconds and finding
all 63-solutions takes 18.3 seconds.

I don't think I can get the program much faster, unless someone
manages to prove some property of the form Proginoskes has brought up,
such as:

"if the 8-O problem is possible, then the queen has to be on
d4 (or one of the other three central squares)"

--
Peter Osterlund - [email protected]
http://web.telia.com/~u89404340

Date: 10 Oct 2007 16:42:39
From: Laurence Reeves
Subject: Re: Source for Eight Officers Problem?

Peter Osterlund wrote:
....
> In this position, all squares except g1 are attacked. However, if you
> remove the king, the squares a5, b4, b6, c5 are also unattacked. All
> those five squares are black, and the program knows that a king can
> only attack at most 4 black squares. Therefore it doesn't even try to
> place the king, which means that it will not find the 63-solution.

A very minor point, but out of interest, have you tried placing the
knights as the the last two pieces? I suspect you will trim a little off
your timings, as it is much less likely to attempt the final knight's
57-way positioning. The constraint of all eight (nine) remaining
un-attacked squares being the same colour (bar one) should cause far
more rejections than the condition of them splitting (roughly) half and
half for the king.

As I measured earlier, the largest ratio of savings occurs at that final
test. Applying the test prior to the final three pieces saves 16%
(IIRC), the penultimate test does save a solid ratio (4 to 1), but the
final test is the important one.

And...

=================

What has just this moment occurred to me, as I typed, is that I've been
stupid. When down to that final knight, I didn't limit it properly. Once
one has made the B/W test, for the 63-cover, one has four cases
remaining: 9W, 8W+1B, 1W+8B or 9B. In the former pair, the knight MUST
go on a black square, in the latter pair, on a white. So, even when it
needs to be attempted, this chops the final loop in half. I suspect that
this will easily halve your run time.

Rule of thumb: Never try to improve your run times by percentages.
Always look for factors of improvement, preferably greater than two, but
that'll do. (See hashlife/Golly)

--
Lau AS! d-(!) a++ c++++ p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++
ASC Decoder at <http://www32.brinkster.com/ascdecode/ >

Date: 10 Oct 2007 20:42:08
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?

Laurence Reeves <[email protected] > writes:

> Peter Osterlund wrote:
> ....
>> In this position, all squares except g1 are attacked. However, if you
>> remove the king, the squares a5, b4, b6, c5 are also unattacked. All
>> those five squares are black, and the program knows that a king can
>> only attack at most 4 black squares. Therefore it doesn't even try to
>> place the king, which means that it will not find the 63-solution.
>
> A very minor point, but out of interest, have you tried placing the
> knights as the the last two pieces? I suspect you will trim a little
> off your timings, as it is much less likely to attempt the final
> knight's 57-way positioning. The constraint of all eight (nine)
> remaining un-attacked squares being the same colour (bar one) should
> cause far more rejections than the condition of them splitting
> (roughly) half and half for the king.

I did try this, but placing the king last is fastest in my program.
At 170 million positions per second, those 36 million positions in the
inner loop only amounts to about 0.2 seconds, so there is little point
optimizing the inner loop any more.

The major part of the cpu time is spent evaluating the pruning rules
and building up the partial positions. With the N,N,K placement order,
the number of times the program passes the first, second, and third
pruning rule is:

9882165 17709070 635138

With the K,N,N placement order, I instead get:

9882165 81773282 180490

Indeed, the number of positions that make it into the innermost loop
is reduced by a factor of 3.5 However, the number of positions that
make it into the second-to-innermost loop is increased by a factor of
4.6. The runtime for the K,N,N case is also about 5 times larger than
for the N,N,K case.

> What has just this moment occurred to me, as I typed, is that I've
> been stupid. When down to that final knight, I didn't limit it
> properly. Once one has made the B/W test, for the 63-cover, one has
> four cases remaining: 9W, 8W+1B, 1W+8B or 9B.

There could also be one white and one black square left. Then you
would have to try all squares for the final knight. The number of
those cases would probably be very small though, since one of my
previous runs found only 17 positions that attack 62 squares when one
knight is missing.

--
Peter Osterlund - [email protected]
http://web.telia.com/~u89404340

Date: 09 Oct 2007 17:40:40
From: =?UTF-8?B?wqrCusKqIHJyb2Nr?=
Subject: Re: Source for Eight Officers Problem?

Peter Osterlund wrote:
> ªºª rrock <[email protected]> writes:
>
>
>>Peter Osterlund wrote:
>>
>>
>>>It takes 8 seconds because the program has to analyze 36202866
>>>positions. All other positions are discarded by the B&B rule and the
>>>symmetry discarding logic. The result is the following incomplete
>>>histogram:
>
> ...
>
>>>This shows (together with a proof that the program, compiler, cpu, etc
>>>is correct) that there is no 64-solution to the problem.
>>>
>>>However, it's still quite far away from a formal proof. Analyzing
>>>those 36 million positions by hand and proving that the other
>>>1416336714894 positions can be safely ignored, would probably take a
>>>human being more than a lifetime.
>>
>>I don't know about that. I don't think your catching my drift, either.
>>The first time anything at all about a histogram or symmetry was mentioned,
>>it was in regards to my questions on what was originally asked for. And
>>during the interim of then and now, a number of people have had a number
>>of different inputs on just what is or isn't worthwhile, what is or isn't
>>symmetry, or even how many cases were actually under "formal" consideration.
>>
>>Your program is *not* by any means a brute force program, rather, it is
>>a tool that is helping you whittle down that larger number, and you and
>>others have made quite a few small discoveries in what, only a week or
>>so? Each of those little rules is a small part of the ultimate formal
>>proof. I don't think you're giving yourself or the group interested in
>>this thread as much credit as you deserve and/or are underestimating the
>>combined capabilities. As a programmer you should be looking at the rules
>>mathematically to discover those small underlying logic clues that lead
>>to bigger revelations. You're not giving up, are you?
>
>
> I haven't given up on making my program faster, but unfortunately I
> don't see much hope in transforming my program into a formal proof
> short enough to be verified by a human without computer help.
>
> One idea I'm planning to test is to first let the program spend some
> time computing more efficient B&B rules, then use those rules to
> further reduce the number of positions it needs to evaluate.

I'm unsure if it would fit, but have you considered using a neural-net?
Myself, i'm headed the opposite direction, since my goal is different.
To remain "pure" to the dog-task, my concentration is on a better
permutations algorithm as well as considering the superset question,
i.e. same question on any sized board with any number of pieces of
any type. The challenge for me is to consider every case completely
within what you would call a "reasonable" amount of time, while still
on a slow box. It may not be possible (since you are such an impatient
fellow.. j/k), but getting it "as good as it can get" by means of
algorithm is my only true goal.

>
>>By the way, completely on a different note, did i miss something earlier
>>or is there a reason 63 has only 109 cases now instead of the 144? If i
>>missed that post, please let me know. I'd hate to find my old dog over
>>here had come up with 109 after a month of waiting, figure i screwed up
>>and... lol delete the files. Was the 144 with or without symmetry? That
>>still wouldn't make sense. Let me know. I understand the histogram is
>>incomplete, but i don't understand how it could not fill in all of the
>>63 coverage states and still be competent enough to say it had checked
>>all of the 64's. If that is correct, and the 144 still hasn't changed,
>>then THERE is a heap of data for checking out regarding another rule.
>>For example, which of the 63's has it forsaken, and WHY? Any pattern?
>>(even a plaid pattern for egg-heads?). Quit worrying about the 36 million
>>positions and pay attention to the 109. Just my two cents.
>
>
> There are indeed 144 solutions, but in some cases the program can
> realize after placing all pieces except the king that there is no
> point placing the king, because it is impossible to attack all 64
> squares. In that case, the program doesn't test all available king
> positions, even though some of those positions might lead to a
> 63-solution.
>
> An example:
>
> ......R.
> .......R
> ........
> .K......
> ..B.....
> ...Q....
> .B....N.
> ...N....
>
> In this position, all squares except g1 are attacked. However, if you
> remove the king, the squares a5, b4, b6, c5 are also unattacked. All
> those five squares are black, and the program knows that a king can
> only attack at most 4 black squares. Therefore it doesn't even try to
> place the king, which means that it will not find the 63-solution.

Yes, this is where we completely part company. My program is "not-allowed"
to know such things and all pieces must be placed before any calculation
is made about attack coverage. Fortunately for you, you haven't got any
X-Ray chess reputation to live down. On the other hand, your problem is
more specific than mine since what i'm after is the permutations of the
attacks (eventually) rather than the pieces. Seems to me that is where
the underlying answer is, anyhow. The permutations of pieces have two types
of "movement", one of which has two sub-types (bishops). The attack
permutations have two types as well, but only the king is a member of
both sets.

Date: 10 Oct 2007 05:32:45
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?

ªºª rrock <[email protected] > writes:

> Peter Osterlund wrote:

>> An example:
>>
>> ......R.
>> .......R
>> ........
>> .K......
>> ..B.....
>> ...Q....
>> .B....N.
>> ...N....
>>
>> In this position, all squares except g1 are attacked. However, if you
>> remove the king, the squares a5, b4, b6, c5 are also unattacked. All
>> those five squares are black, and the program knows that a king can
>> only attack at most 4 black squares. Therefore it doesn't even try to
>> place the king, which means that it will not find the 63-solution.
>
> Yes, this is where we completely part company. My program is "not-allowed"
> to know such things and all pieces must be placed before any calculation
> is made about attack coverage.

My program is can be run in pure brute-force mode too. Just change the
"prune" variable to -1 and recompile. Then you get a program that
analyzes all 1.4e12 positions. At a speed of about 170 million
positions per second, this means that the computation takes about 2
hours and 20 minutes. If you don't want to consider symmetries, you
can remove two lines of source code and get a program that analyzes
all 1.1e13 positions. The run-time for that program would be about 18
hours and 30 minutes.

My program does have some assumptions though. First it assumes that
the board has at most 64 squares. That assumption means that "attack
bitmaps" fit in a single 64-bit integer, which can be handled very
efficiently on a 64-bit computer. Changing that assumption in the code
wouldn't be that hard, but would make the program run slower, if more
than one 64-bit integer is required to hold each "attack bitmap".

The second assumption is that pieces either have X-ray capability or
they don't. An imaginary piece that could attack through one other
piece but not through two, can't be handled by the current attack
bitmap calculation algorithm.

The key idea that makes the program so fast is that it starts by
computing all entries in the following array:

uint64_t attackShadow_[5][64][64];

The entries in that array are computed such that

attackShadow_[piece][square][otherSquare]

contains a bitmap with all squares attacked by "piece" when it is
placed on "square" and there is another piece at "otherSquare" that
potentially blocks the attacks of the first piece.

Using that array, it is possible to compute all attacked squares for
an arrangement of the 8 pieces using about 15 array lookups, 15 "and"
operations and 7 "or" operations.

Counting the number of one bits in a 64-bit integer is done with
another array, so that each array access counts 16 bits.

--
Peter Osterlund - [email protected]
http://web.telia.com/~u89404340

Date: 10 Oct 2007 10:36:29
From: =?UTF-8?B?wqrCusKqIHJyb2Nr?=
Subject: Re: Source for Eight Officers Problem?

Peter Osterlund wrote:
> ªºª rrock <[email protected]> writes:
>
>
>>Peter Osterlund wrote:
>
>
>>>An example:
>>>
>>> ......R.
>>> .......R
>>> ........
>>> .K......
>>> ..B.....
>>> ...Q....
>>> .B....N.
>>> ...N....
>>>
>>>In this position, all squares except g1 are attacked. However, if you
>>>remove the king, the squares a5, b4, b6, c5 are also unattacked. All
>>>those five squares are black, and the program knows that a king can
>>>only attack at most 4 black squares. Therefore it doesn't even try to
>>>place the king, which means that it will not find the 63-solution.
>>
>>Yes, this is where we completely part company. My program is "not-allowed"
>>to know such things and all pieces must be placed before any calculation
>>is made about attack coverage.
>
>
> My program is can be run in pure brute-force mode too. Just change the
> "prune" variable to -1 and recompile. Then you get a program that
> analyzes all 1.4e12 positions. At a speed of about 170 million
> positions per second, this means that the computation takes about 2
> hours and 20 minutes. If you don't want to consider symmetries, you
> can remove two lines of source code and get a program that analyzes
> all 1.1e13 positions. The run-time for that program would be about 18
> hours and 30 minutes.

What is the clock speed on that box, again?

> My program does have some assumptions though. First it assumes that
> the board has at most 64 squares. That assumption means that "attack
> bitmaps" fit in a single 64-bit integer, which can be handled very
> efficiently on a 64-bit computer. Changing that assumption in the code
> wouldn't be that hard, but would make the program run slower, if more
> than one 64-bit integer is required to hold each "attack bitmap".

So, when you say "at most 64 squares", are you saying that it would run
just fine on a 7x7 board?

> The second assumption is that pieces either have X-ray capability or
> they don't. An imaginary piece that could attack through one other
> piece but not through two, can't be handled by the current attack
> bitmap calculation algorithm.
>
> The key idea that makes the program so fast is that it starts by
> computing all entries in the following array:
>
> uint64_t attackShadow_[5][64][64];
>
> The entries in that array are computed such that
>
> attackShadow_[piece][square][otherSquare]
>
> contains a bitmap with all squares attacked by "piece" when it is
> placed on "square" and there is another piece at "otherSquare" that
> potentially blocks the attacks of the first piece.
>
> Using that array, it is possible to compute all attacked squares for
> an arrangement of the 8 pieces using about 15 array lookups, 15 "and"
> operations and 7 "or" operations.

i do the same, but only for kings and knights, and only a [width][height]
sized array of double-quads since the max board size for my program is
128 squares.

> Counting the number of one bits in a 64-bit integer is done with
> another array, so that each array access counts 16 bits.

do you use x&(x-1)?

Date: 10 Oct 2007 19:41:47
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?

ªºª rrock <[email protected] > writes:

> Peter Osterlund wrote:
>>
>> My program is can be run in pure brute-force mode too. Just change the
>> "prune" variable to -1 and recompile. Then you get a program that
>> analyzes all 1.4e12 positions. At a speed of about 170 million
>> positions per second, this means that the computation takes about 2
>> hours and 20 minutes. If you don't want to consider symmetries, you
>> can remove two lines of source code and get a program that analyzes
>> all 1.1e13 positions. The run-time for that program would be about 18
>> hours and 30 minutes.
>
> What is the clock speed on that box, again?

It's an Intel Core 2 Quad machine, running at 2.4GHz. My program uses
all four CPUs, so I guess you could say the effective clock speed is
9.6GHz. I'm also running a 64 bit OS (Linux, Fedora 7), which is
really great for 64-bit aware programs.

As I reported before, a 3.07GHz Intel Pentium 4 machine (not
hyperthreaded) is roughly 8 times slower than the Quad core machine,
when running this program.

>> My program does have some assumptions though. First it assumes that
>> the board has at most 64 squares. That assumption means that "attack
>> bitmaps" fit in a single 64-bit integer, which can be handled very
>> efficiently on a 64-bit computer. Changing that assumption in the code
>> wouldn't be that hard, but would make the program run slower, if more
>> than one 64-bit integer is required to hold each "attack bitmap".
>
> So, when you say "at most 64 squares", are you saying that it would run
> just fine on a 7x7 board?

It would need some small modifications, because "board size 8" is
hardcoded at a couple of places. What I meant was that the program
could quite easily be modifed to handle smaller board sizes and still
be able to process 170 million positions per second.

>> Counting the number of one bits in a 64-bit integer is done with
>> another array, so that each array access counts 16 bits.
>
> do you use x&(x-1)?

I did initially, but the table lookup method was much faster. The code
now looks like this:

inline int
BitBoard::numOneBits() const
{
int cnt = 0;
uint64_t tmp = board_;
for (int i = 0; i < 4; i++) {
cnt += bits_[tmp & 0xffff];
tmp >>= 16;
}
return cnt;
}

As you can see, 16 bits are counted at a time by a single lookup in
the bits_ array. The bits_ array is computed once when the program
starts with the following code:

void
BitBoard::init()
{
for (int i = 0; i < 65536; i++) {
int cnt = 0;
int tmp = i;
while (tmp) {
cnt++;
tmp &= (tmp - 1);
}
bits_[i] = cnt;
}
}

So, as you can see, I'm using the x&(x-1) trick only when initializing
the array.

--
Peter Osterlund - [email protected]
http://web.telia.com/~u89404340

Date: 10 Oct 2007 15:36:56
From: =?UTF-8?B?wqrCusKqIHJyb2Nr?=
Subject: Re: Source for Eight Officers Problem?

Peter Osterlund wrote:

> ªºª rrock <[email protected]> writes:
>
>
>>Peter Osterlund wrote:
>>
>>>My program is can be run in pure brute-force mode too. Just change the
>>>"prune" variable to -1 and recompile. Then you get a program that
>>>analyzes all 1.4e12 positions. At a speed of about 170 million
>>>positions per second, this means that the computation takes about 2
>>>hours and 20 minutes. If you don't want to consider symmetries, you
>>>can remove two lines of source code and get a program that analyzes
>>>all 1.1e13 positions. The run-time for that program would be about 18
>>>hours and 30 minutes.
>>
>>What is the clock speed on that box, again?
>
>
> It's an Intel Core 2 Quad machine, running at 2.4GHz. My program uses
> all four CPUs, so I guess you could say the effective clock speed is
> 9.6GHz. I'm also running a 64 bit OS (Linux, Fedora 7), which is
> really great for 64-bit aware programs.
>
> As I reported before, a 3.07GHz Intel Pentium 4 machine (not
> hyperthreaded) is roughly 8 times slower than the Quad core machine,
> when running this program.
>
>
>>>My program does have some assumptions though. First it assumes that
>>>the board has at most 64 squares. That assumption means that "attack
>>>bitmaps" fit in a single 64-bit integer, which can be handled very
>>>efficiently on a 64-bit computer. Changing that assumption in the code
>>>wouldn't be that hard, but would make the program run slower, if more
>>>than one 64-bit integer is required to hold each "attack bitmap".
>>
>>So, when you say "at most 64 squares", are you saying that it would run
>>just fine on a 7x7 board?
>
> It would need some small modifications, because "board size 8" is
> hardcoded at a couple of places. What I meant was that the program
> could quite easily be modifed to handle smaller board sizes and still
> be able to process 170 million positions per second.
>

So all of your shadow masks are already setup for both odd and even
width boards, and your permutations algorithm already handles the
differences of the positions for the bishops of both odd and even
width boards?

>>>Counting the number of one bits in a 64-bit integer is done with
>>>another array, so that each array access counts 16 bits.
>>
>>do you use x&(x-1)?
>
>
> I did initially, but the table lookup method was much faster. The code
> now looks like this:
>
> inline int
> BitBoard::numOneBits() const
> {
> int cnt = 0;
> uint64_t tmp = board_;
> for (int i = 0; i < 4; i++) {
> cnt += bits_[tmp & 0xffff];
> tmp >>= 16;
> }
> return cnt;
> }
>
> As you can see, 16 bits are counted at a time by a single lookup in
> the bits_ array. The bits_ array is computed once when the program
> starts with the following code:
>
> void
> BitBoard::init()
> {
> for (int i = 0; i < 65536; i++) {
> int cnt = 0;
> int tmp = i;
> while (tmp) {
> cnt++;
> tmp &= (tmp - 1);
> }
> bits_[i] = cnt;
> }
> }
>
> So, as you can see, I'm using the x&(x-1) trick only when initializing
> the array.

lol, so much for the old days of expensive ram. It would take the old '88
four machines just to hold that table. lololol

Date: 10 Oct 2007 21:24:21
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?

ªºª rrock <[email protected] > writes:

> Peter Osterlund wrote:
>
>> ªºª rrock <[email protected]> writes:
>>
>>>So, when you say "at most 64 squares", are you saying that it would run
>>>just fine on a 7x7 board?
>>
>> It would need some small modifications, because "board size 8" is
>> hardcoded at a couple of places. What I meant was that the program
>> could quite easily be modifed to handle smaller board sizes and still
>> be able to process 170 million positions per second.
>
> So all of your shadow masks are already setup for both odd and even
> width boards,

The shadow masks are computed at program start, and all that is
required to make them work with a smaller board is to change the
following function in the obvious way:

inline bool
BitBoard::inRange(int x, int y)
{
return (x >= 0) && (x < 8) && (y >= 0) && (y < 8);
}

> and your permutations algorithm already handles the
> differences of the positions for the bishops of both odd and even
> width boards?

Yes.

>>>>Counting the number of one bits in a 64-bit integer is done with
>>>>another array, so that each array access counts 16 bits.
>>>
>>>do you use x&(x-1)?
...
>> So, as you can see, I'm using the x&(x-1) trick only when initializing
>> the array.
>
> lol, so much for the old days of expensive ram. It would take the old '88
> four machines just to hold that table. lololol

That table is only 64KB though, because bits_ is an array of chars,
not ints. The big array is the attackShadow_ array, which is
5*64*64*8=160KB. And I actually use two attackShadow_ arrays, one
indexed like [piece][square][blockingSquare] and the other indexed
like [piece][blockingSquare][square]. That wastes another 160KB of
memory, but makes the compiler generate better assembly code in the
inner loop. Since all three arrays combined are much smaller than the
L2 cache in the CPU, the extra memory usage isn't a problem.

--
Peter Osterlund - [email protected]
http://web.telia.com/~u89404340

Date: 10 Oct 2007 18:23:14
From: =?UTF-8?B?wqrCusKqIHJyb2Nr?=
Subject: Re: Source for Eight Officers Problem?

Peter Osterlund wrote:
> ªºª rrock <[email protected]> writes:
>
>
>>Peter Osterlund wrote:
>>
>>
>>>ªºª rrock <[email protected]> writes:
>>>
>>>
>>>>So, when you say "at most 64 squares", are you saying that it would run
>>>>just fine on a 7x7 board?
>>>
>>>It would need some small modifications, because "board size 8" is
>>>hardcoded at a couple of places. What I meant was that the program
>>>could quite easily be modifed to handle smaller board sizes and still
>>>be able to process 170 million positions per second.
>>
>>So all of your shadow masks are already setup for both odd and even
>>width boards,
>
>
> The shadow masks are computed at program start, and all that is
> required to make them work with a smaller board is to change the
> following function in the obvious way:
>
> inline bool
> BitBoard::inRange(int x, int y)
> {
> return (x >= 0) && (x < 8) && (y >= 0) && (y < 8);
> }

ahhh, i see your point. I don't use x or y functions, but instead
use bit widths since there aren't any multiplications.

>
>>and your permutations algorithm already handles the
>>differences of the positions for the bishops of both odd and even
>>width boards?
>
>
> Yes.
>
>
>>>>>Counting the number of one bits in a 64-bit integer is done with
>>>>>another array, so that each array access counts 16 bits.
>>>>
>>>>do you use x&(x-1)?
>
> ...
>
>>>So, as you can see, I'm using the x&(x-1) trick only when initializing
>>>the array.
>>
>>lol, so much for the old days of expensive ram. It would take the old '88
>>four machines just to hold that table. lololol
>
>
> That table is only 64KB though, because bits_ is an array of chars,
> not ints.

okay, 1 machine then. lol. i still think it's funny how in only a few
short years... (well, okay 25 or 30 short years) ... nevermind... lol

seems to me since 256K isn't very much at all these days, you'd might
get a little better performance by making it an array of int rather than
char (if it was aligned to begin with especially).

> The big array is the attackShadow_ array, which is
> 5*64*64*8=160KB. And I actually use two attackShadow_ arrays, one
> indexed like [piece][square][blockingSquare] and the other indexed
> like [piece][blockingSquare][square]. That wastes another 160KB of
> memory, but makes the compiler generate better assembly code in the
> inner loop. Since all three arrays combined are much smaller than the
> L2 cache in the CPU, the extra memory usage isn't a problem.
>

all together it's less than a meg.

Date: 01 Oct 2007 13:12:23
From: Laurence Reeves
Subject: Re: Source for Eight Officers Problem?

Proginoskes wrote:
> ... First of all, Laurence Reeves's algorithm is branch-and-bound (which
> he originally called "heuristic"). ...

A minor "point of order". I never called my method "heuristic". I went
to some pains to explain that, to me, a "heuristic" approach would mean
"not guaranteed to find all solutions". It might find 144 solutions, but
could only EVER give that as a lower bound (unless there happened to be
some a priori reason why it was known that there were exactly 144
solutions). I use an algorithm (to find *the* solutions to the problem)
not a heuristic (to maybe find *some* solutions to the problem).

Having never come across the terminology of "branch and bound" before, I
looked it up.

Technically, I'm not sure that my algorithm is that either, as it does
not do any branching. I suppose you can interpret it that way, in that I
progress each time from one specific (branched?) layout of five, six or
seven pieces, and discard (bound) by rejecting further processing of a
partial layout if it is provably not able to produce any solutions to
the problem at hand (i.e. coverings of >= 63 squares).

Another distinction from "branch and bound" might be that my algorithm
is exact and guaranteed to terminate, whereas B&B seems not to imply
that it should go that far.
--
Lau AS! d-(!) a++ c++++ p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++
ASC Decoder at <http://www32.brinkster.com/ascdecode/ >

Date: 30 Sep 2007 06:34:34
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?

On Sep 29, 2:31 pm, Peter Osterlund <[email protected] > wrote:
> Laurence Reeves <[email protected]> writes:
> > =AA=BA=AA rrock wrote:
>
> >> Laurence Reeves wrote:
>
> >>> Finally, and this is probably the only option, it would be a huge
> >>> confirmation if, /before/ I publish the results and program,
> >>> someone else were to at least confirm the count, and maybe publish
> >>> what I say is the unique solution where just the one rook remains
> >>> unmolested.
>
> >> Well, if you hang around for another few months... (grin)
>
> > OK. I'm waiting...
>
> You shouldn't have to wait that long.
>
> My brute force program is currently running on a 2.4GHz Intel Core 2
> Quad computer in 64 bit mode at a speed of approximately 120 million
> positions per second. Since I didn't implement any symmetry detection
> at all, the search space size is about 1.13e13, which means that the
> computation should be finished in about 26 hours.
>
> The output will be the histogram data and the "maximum" positions.
> (Actually split up in 32 files because of how I implemented the
> parallel search and checkpointing, but merging should be simple.)

The code Laurence Reeves sent me took two hours (plus or minus 30
seconds) unmodified. I got a couple of basic ideas for speeding up the
process and have started another run. No information on processor
speed at the moment, though. (I got a new computer a few weeks ago.)

--- Christopher Heckman

Date: 30 Sep 2007 07:17:20
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?

Proginoskes <[email protected] > writes:

> On Sep 29, 2:31 pm, Peter Osterlund <[email protected]> wrote:
>>
>> My brute force program is currently running on a 2.4GHz Intel Core 2
>> Quad computer in 64 bit mode at a speed of approximately 120 million
>> positions per second. Since I didn't implement any symmetry detection
>> at all, the search space size is about 1.13e13, which means that the
>> computation should be finished in about 26 hours.
>>
>> The output will be the histogram data and the "maximum" positions.
>> (Actually split up in 32 files because of how I implemented the
>> parallel search and checkpointing, but merging should be simple.)
>
> The code Laurence Reeves sent me took two hours (plus or minus 30
> seconds) unmodified. I got a couple of basic ideas for speeding up the
> process and have started another run. No information on processor
> speed at the moment, though. (I got a new computer a few weeks ago.)

I might be wrong, but I thought his program was using branch and
bound, and was therefore not able to produce the histogram data.

Also, if I were to consider symmetries, I think it would be possible
to cut down the run time to about 4 hours by only considering 10
squares for the king. However, that would produce a different
histogram.

--
Peter Osterlund - [email protected]
http://web.telia.com/~u89404340

Date: 29 Sep 2007 07:30:12
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?

On Sep 28, 2:47 am, =AA=BA=AA rrock <[email protected] > wrote:
> Proginoskes wrote:
> > On Sep 27, 8:32 pm, =AA=BA=AA rrock <[email protected]> wrote:
>
> >>Proginoskes wrote:
>
> >>>On Sep 27, 2:34 pm, Laurence Reeves <[email protected]> wrote:
>
> >>>>=AA=BA=AA rrock wrote:
>
> >>>>...> If those aren't heuristics, then what is the proper terminology?
>
> >>>>...
>
> >>>>My use of the term:
>
> >>>>heuristic: an approach in problem solving where some avenues of
> >>>>exploration of the problem are never explored because the solution is
> >>>>not expected to be found there.
>
> >>>If you change "not expected to be" to "cannot be", this method is
> >>>called "branch and bound". This method also seems to have been used in
> >>>your code, based on this comment that you make later on:
>
> >>>>A second aspect is that I do not continue
> >>>>placing pieces when I can simply count that those pieces cannot bring
> >>>>the total under attack up to 63 (even if they did not block any other
> >>>>pieces and each gave rise to a fresh attack on every square they could
> >>>>possibly reach).
>
> >>>[back to the beginning:]
>
> >>>>I seem not to agree with the OED on this one. Their definition are all
> >>>>very vague and full of waffle. Maybe I should complain to them? [...]
>
> >>>A heuristic is an algorithm which solves most but not all instances of
> >>>a problem.
>
> >>>>If there were a 64 coverage solution to the "Eight Officers" problem,=
a
> >>>>heuristic approach that found at least one such solution would be fin=
e=2E
>
> >>>Actually, the final diagram would be the proof itself, regardless of
> >>>where it came from. "Whether discovered by expert, undergraduate, or
> >>>janitor, correct mathematics is correct mathematics." (butchering a
> >>>quote that appeared in a James Harris thread.)
>
> >>>>To prove that no such solution exists is another matter.
>
> >>>>Anyway, my program solves completely both questions "Is there a full
> >>>>coverage solution?", to which the answer is "no" and "How many distin=
ct
> >>>>63 square coverage solutions are there?", being 144. (I think :) )
>
> >>>Depending on how you define "different positions".
>
> >>>>The program finished its second run a while ago, with a little better
> >>>>pruning, and all optimisations turned on (but debug still in place - a
> >>>>mistake). This time it took 278 minutes, so no huge improvement over
> >>>>last night's 350 minutes. The solution list was identical (phew!).
>
> >>>Maybe you should send me your code, so that I can run it on another
> >>>machine. Getting the same result on different machines is one step
> >>>towards "reproducability"; i.e., someone else being able to derive the
> >>>same results you did.
>
> >>A different machine? Or a different architecture?
>
> > Ideally, both. But even running correctly a different machine is
> > enough to suggest that the program works.
>
> Program or algorithm? An algorithm is independent of hardware.

Using the same code will (tend to) rule out the possibility that the
compiler might be wrong. So if there's a fault, it's with the original
code, not the compiler.

Knowing this makes it easier to say that the code produces the answer
it should. Of course, the code (the program) or the algorithm, or
both, could still be faulty. And I didn't say it couldn't be. 8-)

> Good code is portable. Fast code isn't. On a particular architecture,
> running an identical executable on two different boxes won't tell
> you anything about the algorithm at all. At best, it will only
> expose environment issues and programmer "miscalculations" about
> the environment. For example, a program set up with the programmer's
> miscalculation that all people use a mouse. oops!

I'm thinking about coming up with a paper in two phases. In phase 1,
the known information is gathered together in one place, and *an*
algorithm (with the C code) is presented, most likely being posted to
xxx.lanl.gov. The algorithm allows for other people to develop their
own code, even their own algorithm, to verify that the result is true.
I'm also allowing for the possibility that someone will say, "This was
all done in **** (some specific place)", which was the original
intention of this thread. In phase 2, an algorithm with proof of
correctness will be presented, along with all the information related
to the problem, and will show up in something like the Journal of
Recreational Mathematics.

--- Christopher Heckman

Date: 29 Sep 2007 05:43:38
From: =?ISO-8859-1?Q?=AA=BA=AA_rrock?=
Subject: Re: Source for Eight Officers Problem?

Proginoskes wrote:

> On Sep 28, 2:47 am, �� rrock <[email protected]> wrote:
>
>>Proginoskes wrote:
>>
>>>On Sep 27, 8:32 pm, �� rrock <[email protected]> wrote:
>>
>>>>Proginoskes wrote:
>>
>>>>>On Sep 27, 2:34 pm, Laurence Reeves <[email protected]> wrote:
>>
>>>>>>�� rrock wrote:
>>
>>>>>>...> If those aren't heuristics, then what is the proper terminology?
>>
>>>>>>...
>>
>>>>>>My use of the term:
>>
>>>>>>heuristic: an approach in problem solving where some avenues of
>>>>>>exploration of the problem are never explored because the solution is
>>>>>>not expected to be found there.
>>
>>>>>If you change "not expected to be" to "cannot be", this method is
>>>>>called "branch and bound". This method also seems to have been used in
>>>>>your code, based on this comment that you make later on:
>>
>>>>>>A second aspect is that I do not continue
>>>>>>placing pieces when I can simply count that those pieces cannot bring
>>>>>>the total under attack up to 63 (even if they did not block any other
>>>>>>pieces and each gave rise to a fresh attack on every square they could
>>>>>>possibly reach).
>>
>>>>>[back to the beginning:]
>>
>>>>>>I seem not to agree with the OED on this one. Their definition are all
>>>>>>very vague and full of waffle. Maybe I should complain to them? [...]
>>
>>>>>A heuristic is an algorithm which solves most but not all instances of
>>>>>a problem.
>>
>>>>>>If there were a 64 coverage solution to the "Eight Officers" problem, a
>>>>>>heuristic approach that found at least one such solution would be fine.
>>
>>>>>Actually, the final diagram would be the proof itself, regardless of
>>>>>where it came from. "Whether discovered by expert, undergraduate, or
>>>>>janitor, correct mathematics is correct mathematics." (butchering a
>>>>>quote that appeared in a James Harris thread.)
>>
>>>>>>To prove that no such solution exists is another matter.
>>
>>>>>>Anyway, my program solves completely both questions "Is there a full
>>>>>>coverage solution?", to which the answer is "no" and "How many distinct
>>>>>>63 square coverage solutions are there?", being 144. (I think :) )
>>
>>>>>Depending on how you define "different positions".
>>
>>>>>>The program finished its second run a while ago, with a little better
>>>>>>pruning, and all optimisations turned on (but debug still in place - a
>>>>>>mistake). This time it took 278 minutes, so no huge improvement over
>>>>>>last night's 350 minutes. The solution list was identical (phew!).
>>
>>>>>Maybe you should send me your code, so that I can run it on another
>>>>>machine. Getting the same result on different machines is one step
>>>>>towards "reproducability"; i.e., someone else being able to derive the
>>>>>same results you did.
>>
>>>>A different machine? Or a different architecture?
>>
>>>Ideally, both. But even running correctly a different machine is
>>>enough to suggest that the program works.
>>
>>Program or algorithm? An algorithm is independent of hardware.
>
>
> Using the same code will (tend to) rule out the possibility that the
> compiler might be wrong. So if there's a fault, it's with the original
> code, not the compiler.
>
> Knowing this makes it easier to say that the code produces the answer
> it should. Of course, the code (the program) or the algorithm, or
> both, could still be faulty. And I didn't say it couldn't be. 8-)
>
>
>>Good code is portable. Fast code isn't. On a particular architecture,
>>running an identical executable on two different boxes won't tell
>>you anything about the algorithm at all. At best, it will only
>>expose environment issues and programmer "miscalculations" about
>>the environment. For example, a program set up with the programmer's
>>miscalculation that all people use a mouse. oops!
>
>
> I'm thinking about coming up with a paper in two phases. In phase 1,
> the known information is gathered together in one place, and *an*
> algorithm (with the C code) is presented, most likely being posted to
> xxx.lanl.gov. The algorithm allows for other people to develop their
> own code, even their own algorithm, to verify that the result is true.
> I'm also allowing for the possibility that someone will say, "This was
> all done in **** (some specific place)", which was the original
> intention of this thread. In phase 2, an algorithm with proof of
> correctness will be presented, along with all the information related
> to the problem, and will show up in something like the Journal of
> Recreational Mathematics.
>
> --- Christopher Heckman

I doubt you'll want my algorithm, then, because it is very, very simple,
doesn't consider relflection or symmetry, and i'm even considering at
the moment with doing away entirely with redundancy as well.

Date: 29 Sep 2007 07:21:49
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?

On Sep 28, 10:39 am, =AA=BA=AA rrock <[email protected] > wrote:
> Laurence Reeves wrote:
> > =AA=BA=AA rrock wrote:
> [procedure to count the total number of ways to place the eight officers]

The big problem here is the bishops. If you place some pieces, then
the bishops, then you have to worry not only about how many squares
are left, but also how many *of each color*. Thus it is a whole lot
easier to place the bishops first (32*32), then the rest of the pieces
(C(62,2)*C(60,2)*58*57). (Here, as throughout the thread, C(n,r) is
the binomial coefficient "n choose r", equal to n!/((n-r)! r!).) This
gives you a total of 11,330,983,342,080, where symmetry is not
accounted for. (Earlier, I had 59*58 in my formula, which is slightly
wrong.)

If you are allowing bishops on the same color, then the answer is
C(64,2)*C(62,2)*C(60,2)*58*57 =3D 22,307,873,454,720.

--- Christopher Heckman

Date: 29 Sep 2007 05:39:43
From: =?ISO-8859-1?Q?=AA=BA=AA_rrock?=
Subject: Re: Source for Eight Officers Problem?

Proginoskes wrote:
> On Sep 28, 10:39 am, �� rrock <[email protected]> wrote:
>
>>Laurence Reeves wrote:
>>
>>>�� rrock wrote:
>>
>>[procedure to count the total number of ways to place the eight officers]
>
>
> The big problem here is the bishops. If you place some pieces, then
> the bishops, then you have to worry not only about how many squares
> are left, but also how many *of each color*. Thus it is a whole lot
> easier to place the bishops first (32*32), then the rest of the pieces
> (C(62,2)*C(60,2)*58*57). (Here, as throughout the thread, C(n,r) is
> the binomial coefficient "n choose r", equal to n!/((n-r)! r!).) This
> gives you a total of 11,330,983,342,080, where symmetry is not
> accounted for. (Earlier, I had 59*58 in my formula, which is slightly
> wrong.)
>
> If you are allowing bishops on the same color, then the answer is
> C(64,2)*C(62,2)*C(60,2)*58*57 = 22,307,873,454,720.
>
> --- Christopher Heckman
>

The reason for trying to figure this out, beyond knowing if the tabulation
of the histogram is correct, is to pre-determine the amount of time that
particular algorithms i am working on will take for completion.

The current and fastest so far, is using a 46-bit number to represent the
entire board. in this fashion, each bishop has only 5 bits to represent it,
and is therefore on a "bishop relative" position of 0 to 31. In the number
of the board itself, the two bishops will necessarily have many instances
where they are the same digit (0..31) which is where the "bishop relative"
comes in to play. Each of the other pieces uses a number between 0 and 63.

The total number of possible states, then, legal, or illegal, is actually
what my newer version "considers" partially. As the number is incremented,
there will be both legal and illegal cases such as two pieces occupying the
same square. After legality is determined, the program will loop back and
increment to the next state if there is an illegal case. The total number
of partial considerations then, is from the first "legal" setup number,
to the final "legal" setup number:

FIRST_LEGAL_BOARD 0x000420C41463 = 17729590371
FINAL_LEGAL_BOARD 0x3FFBDF3BEB9C = 70351014587292

The difference is 70,333,284,996,921 so 70,333,284,996,922 cases total.

My previous version used a counting method that would force the positions
of the knights and rooks such that they met the 64*(63/2) idea, in that
the position of one knight (for example) would be forced always greater
than its mate.

I am considering doing away with those checks, though, because of the
branching involved. How exactly is it determined then INCLUDING the
redundant cases, but such that only the legal cases are considered?

Date: 28 Sep 2007 08:54:54
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?

On Sep 27, 8:32 pm, =AA=BA=AA rrock <[email protected] > wrote:
> Proginoskes wrote:
> > On Sep 27, 2:34 pm, Laurence Reeves <[email protected]> wrote:
>
> >>=AA=BA=AA rrock wrote:
>
> >>...> If those aren't heuristics, then what is the proper terminology?
>
> >>...
>
> >>My use of the term:
>
> >>heuristic: an approach in problem solving where some avenues of
> >>exploration of the problem are never explored because the solution is
> >>not expected to be found there.
>
> > If you change "not expected to be" to "cannot be", this method is
> > called "branch and bound". This method also seems to have been used in
> > your code, based on this comment that you make later on:
>
> >>A second aspect is that I do not continue
> >>placing pieces when I can simply count that those pieces cannot bring
> >>the total under attack up to 63 (even if they did not block any other
> >>pieces and each gave rise to a fresh attack on every square they could
> >>possibly reach).
>
> > [back to the beginning:]
>
> >>I seem not to agree with the OED on this one. Their definition are all
> >>very vague and full of waffle. Maybe I should complain to them? [...]
>
> > A heuristic is an algorithm which solves most but not all instances of
> > a problem.
>
> >>If there were a 64 coverage solution to the "Eight Officers" problem, a
> >>heuristic approach that found at least one such solution would be fine.
>
> > Actually, the final diagram would be the proof itself, regardless of
> > where it came from. "Whether discovered by expert, undergraduate, or
> > janitor, correct mathematics is correct mathematics." (butchering a
> > quote that appeared in a James Harris thread.)
>
> >>To prove that no such solution exists is another matter.
>
> >>Anyway, my program solves completely both questions "Is there a full
> >>coverage solution?", to which the answer is "no" and "How many distinct
> >>63 square coverage solutions are there?", being 144. (I think :) )
>
> > Depending on how you define "different positions".
>
> >>The program finished its second run a while ago, with a little better
> >>pruning, and all optimisations turned on (but debug still in place - a
> >>mistake). This time it took 278 minutes, so no huge improvement over
> >>last night's 350 minutes. The solution list was identical (phew!).
>
> > Maybe you should send me your code, so that I can run it on another
> > machine. Getting the same result on different machines is one step
> > towards "reproducability"; i.e., someone else being able to derive the
> > same results you did.
>
> A different machine? Or a different architecture?

Ideally, both. But even running correctly a different machine is
enough to suggest that the program works.

--- Christopher Heckman

Date: 28 Sep 2007 05:03:20
From: =?ISO-8859-1?Q?=AA=BA=AA_rrock?=
Subject: Re: Source for Eight Officers Problem?

In an effort to avoid any further x-ray chess (grin), i was wondering if
someone would be kind enough to point out the flaws in the following
determination of the number of possible non-redundant states. I'm not
speaking of rotation, nor reflection here, but only the number of
states that is actually possible such that no two pieces are on the
same square (legal states), and that no two identical class of piece
is set in the same position that its twin had prior.

In the latter case, the only two classes of piece that need that consideration
are the rook and the knight. So, here is where i'd like some verification:

Given two knights on the board alone, a single knight, knight 1 would only
have 63 squares to occupy, non-redundantly with its brother, and its brother,
would always be in a greater (i.e. higher (rank*8)+file) position such that
the total number of states for these two pieces alone would be 2079.

The rooks would therefore be the same.

So, then given just that, 2079^2 would be the total number of possible
states for the four pieces, rooks and knights. Since the King and Queen
both have 64 possible positions, 64^2 would be the total number of possible
states for those two pieces. Since the bishops can only occupy 32 possible
positions, and since they are unlike the rooks and knights, they like the
king and queen could be in 32^2 possible states. So it occurs to me then,
that 2079^2 * 64^2 * 32^2 would be the total possible states for consideration.

18,128,792,715,264

Date: 28 Sep 2007 13:45:13
From: Laurence Reeves
Subject: Re: Source for Eight Officers Problem?

�� rrock wrote:
> ... knights ... the total number of states for these two pieces alone would be 2079.
No. 64*63/2. I have no idea where your 2079 (3^3*7*11) has come from.

> The rooks would therefore be the same.
Yes. On their own. 64*63/2.

> So, then given just that, 2079^2 would be the total number of possible
> states for the four pieces, rooks and knights.
No. (64*63/2)*(62*61)/2. Once one pair has been placed, there are two
less squares for the second pair to use.

Since the King and Queen
> both have 64 possible positions,
Yes.

64^2 would be the total number of possible
> states for those two pieces.
No. 64*63. If they were on their own, plus they are not on the same square.

Since the bishops can only occupy 32 possible
> positions,
Yes.
and since they are unlike the rooks and knights, they like the
> king and queen could be in 32^2 possible states.
Yes (but UNLIKE the king and queen, as the bishops can never conflict
with each other, one being on black and one on white).

So it occurs to me then,
> that 2079^2 * 64^2 * 32^2 would be the total possible states for
> consideration.
>
> 18,128,792,715,264
No. Without any symmetries being taken into consideration, we will have
32*32*(62*61/2)*(60*59/2)*58*57 = 11,330,983,342,080.

Deferring symmetry considerations to a later time is a huge mistake. My
figure of (4*16+6*32)*31*(61*60/2)*(58*59/2)*57 = 1,416,372,917,760 is a
factor of eight smaller, as one can easily expect. I.e. given any
pattern with all pieces placed, that pattern CANNOT have any overall
symmetry. Hence in the full list, every distinct pattern will be
represented exactly eight times. Its four rotational positions and the
mirrors of each of those.

--
Lau AS! d-(!) a++ c++++ p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++
ASC Decoder at <http://www32.brinkster.com/ascdecode/ >

Date: 28 Sep 2007 12:39:03
From: =?ISO-8859-1?Q?=AA=BA=AA_rrock?=
Subject: Re: Source for Eight Officers Problem?

Laurence Reeves wrote:
> �� rrock wrote:
>
>> ... knights ... the total number of states for these two pieces alone
>> would be 2079.
>
> No. 64*63/2. I have no idea where your 2079 (3^3*7*11) has come from.

The formula for the number of places that knights and rooks as only
pairs would be 63+62+61...+1. which is 64*(63/2). But that number needs
to be squared then... for each place a rook could go, a knight would
also need to go in that place... they can't be disjoint, can they?

>
>> The rooks would therefore be the same.
>
> Yes. On their own. 64*63/2.
>
>> So, then given just that, 2079^2 would be the total number of possible
>> states for the four pieces, rooks and knights.
>
> No. (64*63/2)*(62*61)/2. Once one pair has been placed, there are two
> less squares for the second pair to use.

But Rook-1 and Knight-1 both need to be placed in all 63 positions... their
brother piece taking the next position upward....

> Since the King and Queen
>
>> both have 64 possible positions,
>
> Yes.
>
> 64^2 would be the total number of possible
>
>> states for those two pieces.
>
> No. 64*63. If they were on their own, plus they are not on the same square.

If I had a King and a Queen alone, and put them in all possible combinations,
you are saying that the either the King or the Queen would not be placed in
each of the positions, but only 63 of them.... i am picturing it, though...
and i know you're right... as the king moves to each of the 64 places, the
queen has 63 possible places, and she will cover that "other place" 63 times.

Ahhhh... g4wd it's been way too long...lol

>
> Since the bishops can only occupy 32 possible
>
>> positions,
>
> Yes.
> and since they are unlike the rooks and knights, they like the
>
>> king and queen could be in 32^2 possible states.
>
> Yes (but UNLIKE the king and queen, as the bishops can never conflict
> with each other, one being on black and one on white).
>
> So it occurs to me then,
>
>> that 2079^2 * 64^2 * 32^2 would be the total possible states for
>> consideration.
>>
>> 18,128,792,715,264
>
> No. Without any symmetries being taken into consideration, we will have
> 32*32*(62*61/2)*(60*59/2)*58*57 = 11,330,983,342,080.
>
> Deferring symmetry considerations to a later time is a huge mistake. My
> figure of (4*16+6*32)*31*(61*60/2)*(58*59/2)*57 = 1,416,372,917,760 is a
> factor of eight smaller, as one can easily expect. I.e. given any
> pattern with all pieces placed, that pattern CANNOT have any overall
> symmetry. Hence in the full list, every distinct pattern will be
> represented exactly eight times. Its four rotational positions and the
> mirrors of each of those.

Are you trying to take away all the "entertainment" value of me figuring
out the algorithms that have literally nothing to do with chess so that
i can get this beast of mine cut down to size? lol

Even as my other beast is plodding along on another box off to the side...
i'm working on a manner to detect 6-bit zero fields in a 46-bit number
on a 32-bit machine in as few instructions possible. I've started the
rewrite using two parallel computations and have changed the format
quite a bit. Its now 6, 6-bit fields for rooks, knights, king and queen,
with two 5-bit fields in the lower nibbles for the bishops. I'm hoping
to process any of 6 possible instances of bishop collision in parallel
without resorting to stripping the string apart serially. I've got the
fields detected, but isolating them numerically is still some work to do.

Date: 28 Sep 2007 04:47:02
From: =?ISO-8859-1?Q?=AA=BA=AA_rrock?=
Subject: Re: Source for Eight Officers Problem?

Proginoskes wrote:
> On Sep 27, 8:32 pm, �� rrock <[email protected]> wrote:
>
>>Proginoskes wrote:
>>
>>>On Sep 27, 2:34 pm, Laurence Reeves <[email protected]> wrote:
>>
>>>>�� rrock wrote:
>>
>>>>...> If those aren't heuristics, then what is the proper terminology?
>>
>>>>...
>>
>>>>My use of the term:
>>
>>>>heuristic: an approach in problem solving where some avenues of
>>>>exploration of the problem are never explored because the solution is
>>>>not expected to be found there.
>>
>>>If you change "not expected to be" to "cannot be", this method is
>>>called "branch and bound". This method also seems to have been used in
>>>your code, based on this comment that you make later on:
>>
>>>>A second aspect is that I do not continue
>>>>placing pieces when I can simply count that those pieces cannot bring
>>>>the total under attack up to 63 (even if they did not block any other
>>>>pieces and each gave rise to a fresh attack on every square they could
>>>>possibly reach).
>>
>>>[back to the beginning:]
>>
>>>>I seem not to agree with the OED on this one. Their definition are all
>>>>very vague and full of waffle. Maybe I should complain to them? [...]
>>
>>>A heuristic is an algorithm which solves most but not all instances of
>>>a problem.
>>
>>>>If there were a 64 coverage solution to the "Eight Officers" problem, a
>>>>heuristic approach that found at least one such solution would be fine.
>>
>>>Actually, the final diagram would be the proof itself, regardless of
>>>where it came from. "Whether discovered by expert, undergraduate, or
>>>janitor, correct mathematics is correct mathematics." (butchering a
>>>quote that appeared in a James Harris thread.)
>>
>>>>To prove that no such solution exists is another matter.
>>
>>>>Anyway, my program solves completely both questions "Is there a full
>>>>coverage solution?", to which the answer is "no" and "How many distinct
>>>>63 square coverage solutions are there?", being 144. (I think :) )
>>
>>>Depending on how you define "different positions".
>>
>>>>The program finished its second run a while ago, with a little better
>>>>pruning, and all optimisations turned on (but debug still in place - a
>>>>mistake). This time it took 278 minutes, so no huge improvement over
>>>>last night's 350 minutes. The solution list was identical (phew!).
>>
>>>Maybe you should send me your code, so that I can run it on another
>>>machine. Getting the same result on different machines is one step
>>>towards "reproducability"; i.e., someone else being able to derive the
>>>same results you did.
>>
>>A different machine? Or a different architecture?
>
>
> Ideally, both. But even running correctly a different machine is
> enough to suggest that the program works.
>
> --- Christopher Heckman

Program or algorithm? An algorithm is independent of hardware.
Good code is portable. Fast code isn't. On a particular architecture,
running an identical executable on two different boxes won't tell
you anything about the algorithm at all. At best, it will only
expose environment issues and programmer "miscalculations" about
the environment. For example, a program set up with the programmer's
miscalculation that all people use a mouse. oops!

Date: 28 Sep 2007 11:08:31
From: Guy Macon
Subject: Re: Source for Eight Officers Problem?

rrock wrote:

>Proginoskes wrote:
>
>>rrock wrote:
>>
>>>Proginoskes wrote:
>>>
>>>>Maybe you should send me your code, so that I can run it on another
>>>>machine. Getting the same result on different machines is one step
>>>>towards "reproducability"; i.e., someone else being able to derive the
>>>>same results you did.
>>>
>>>A different machine? Or a different architecture?
>>
>> Ideally, both. But even running correctly a different machine is
>> enough to suggest that the program works.
>
>Program or algorithm? An algorithm is independent of hardware.
>Good code is portable. Fast code isn't. On a particular architecture,
>running an identical executable on two different boxes won't tell
>you anything about the algorithm at all. At best, it will only
>expose environment issues and programmer "miscalculations" about
>the environment.

I would like to see a couple of FORTH programmers I know
take a shot at impementing the algorithm. the execution
speed differences are always interesting when going from
C/C++ to FORTH... :)

--
Guy Macon
<http://www.guymacon.com/ >

Date: 27 Sep 2007 22:50:10
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?

On Sep 27, 2:34 pm, Laurence Reeves <[email protected] > wrote:
> =AA=BA=AA rrock wrote:
>
> ...> If those aren't heuristics, then what is the proper terminology?
>
> ...
>
> My use of the term:
>
> heuristic: an approach in problem solving where some avenues of
> exploration of the problem are never explored because the solution is
> not expected to be found there.

If you change "not expected to be" to "cannot be", this method is
called "branch and bound". This method also seems to have been used in
your code, based on this comment that you make later on:

> A second aspect is that I do not continue
> placing pieces when I can simply count that those pieces cannot bring
> the total under attack up to 63 (even if they did not block any other
> pieces and each gave rise to a fresh attack on every square they could
> possibly reach).

[back to the beginning:]

> I seem not to agree with the OED on this one. Their definition are all
> very vague and full of waffle. Maybe I should complain to them? [...]

A heuristic is an algorithm which solves most but not all instances of
a problem.

> If there were a 64 coverage solution to the "Eight Officers" problem, a
> heuristic approach that found at least one such solution would be fine.

Actually, the final diagram would be the proof itself, regardless of
where it came from. "Whether discovered by expert, undergraduate, or
janitor, correct mathematics is correct mathematics." (butchering a
quote that appeared in a James Harris thread.)

> To prove that no such solution exists is another matter.
>
> Anyway, my program solves completely both questions "Is there a full
> coverage solution?", to which the answer is "no" and "How many distinct
> 63 square coverage solutions are there?", being 144. (I think :) )

Depending on how you define "different positions".

> The program finished its second run a while ago, with a little better
> pruning, and all optimisations turned on (but debug still in place - a
> mistake). This time it took 278 minutes, so no huge improvement over
> last night's 350 minutes. The solution list was identical (phew!).

Maybe you should send me your code, so that I can run it on another
machine. Getting the same result on different machines is one step
towards "reproducability"; i.e., someone else being able to derive the
same results you did.

--- Christopher Heckman

Date: 27 Sep 2007 22:32:14
From: =?ISO-8859-1?Q?=AA=BA=AA_rrock?=
Subject: Re: Source for Eight Officers Problem?

Proginoskes wrote:

> On Sep 27, 2:34 pm, Laurence Reeves <[email protected]> wrote:
>
>>�� rrock wrote:
>>
>>...> If those aren't heuristics, then what is the proper terminology?
>>
>>...
>>
>>My use of the term:
>>
>>heuristic: an approach in problem solving where some avenues of
>>exploration of the problem are never explored because the solution is
>>not expected to be found there.
>
>
> If you change "not expected to be" to "cannot be", this method is
> called "branch and bound". This method also seems to have been used in
> your code, based on this comment that you make later on:
>
>
>>A second aspect is that I do not continue
>>placing pieces when I can simply count that those pieces cannot bring
>>the total under attack up to 63 (even if they did not block any other
>>pieces and each gave rise to a fresh attack on every square they could
>>possibly reach).
>
>
> [back to the beginning:]
>
>
>>I seem not to agree with the OED on this one. Their definition are all
>>very vague and full of waffle. Maybe I should complain to them? [...]
>
>
> A heuristic is an algorithm which solves most but not all instances of
> a problem.
>
>
>>If there were a 64 coverage solution to the "Eight Officers" problem, a
>>heuristic approach that found at least one such solution would be fine.
>
>
> Actually, the final diagram would be the proof itself, regardless of
> where it came from. "Whether discovered by expert, undergraduate, or
> janitor, correct mathematics is correct mathematics." (butchering a
> quote that appeared in a James Harris thread.)
>
>
>>To prove that no such solution exists is another matter.
>>
>>Anyway, my program solves completely both questions "Is there a full
>>coverage solution?", to which the answer is "no" and "How many distinct
>>63 square coverage solutions are there?", being 144. (I think :) )
>
>
> Depending on how you define "different positions".
>
>
>>The program finished its second run a while ago, with a little better
>>pruning, and all optimisations turned on (but debug still in place - a
>>mistake). This time it took 278 minutes, so no huge improvement over
>>last night's 350 minutes. The solution list was identical (phew!).
>
>
> Maybe you should send me your code, so that I can run it on another
> machine. Getting the same result on different machines is one step
> towards "reproducability"; i.e., someone else being able to derive the
> same results you did.
>
> --- Christopher Heckman

A different machine? Or a different architecture?

>

Date: 27 Sep 2007 22:39:32
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?

On Sep 27, 6:21 am, =AA=BA=AA rrock <[email protected] > wrote:
> Laurence Reeves wrote:
> > =AA=BA=AA rrock wrote:
>
> >> Laurence Reeves wrote:
>
> >>> Proginoskes wrote:
> [...]
> > In this case, where there remain more squares still not under attack
> > than the pieces remaining can possibly cope with, I discontinue that
> > pattern without attempting any specific locations for the remaining pie=
ces.
> > Given the program, I can "prove" that it has gone through all possible
> > cases, by argument, but not by any numbers that it may print out.
>
> That would be a formal proof then, or, rather sort of a mixing of a
> formal proof and a heuristic program (i.e. not a brute force program).

And that is not uncommon. The 4CT is an example of a way to turn the
problem into a "small" number of cases, which can be exhausted by an
algorithm which is proven correct. Here, we only worry about symmetry;
it would be nice if you could say: "If the Eight Officers Problem has
a solution, then the rooks are in opposite corners."

I envision the report being (a) a sumy of what can be found on the
Internet and what has been documented, (b) how the search can be cut
down from the 12 trillion possibilities to a much smaller number, (c)
a proof of correctness of the code/algorithm, and (d) a listing of the
program itself.

Hopefully, describing the algorithm will encourage other people to
write their own programs, which is another check. (I helped out on the
new proof of the 4CT by Robertson, Sanders, Seymour, and Thomas; in
1994-1996, I debugged the C code for the "discharging" algorithm and
rewrite it in Pascal, as part of checking the "computer" aspects. This
would rule out a bad compiler and all the other things that people
point out when a computer proof has been published.)

> > If I publish the list of all 144 "solutions", someone might notice
> > patterns that enabled a direct proof that these are the only possible
> > cases. I doubt this. They seem pretty arbitrary.
>
> 144 being 12 squared, it sounds like there might be some validity to
> that. [...]

Why? 144 is also a Fibonacci number (as well as 8); should that matter
as well?

> A full histogram will eventually prove that 63 is the highest possibility=
, *BUT*
> it will also show what the WORST case coverage is as well.

That problem has also been considered. The solution seems to be 16
squares attacked, and it looks something like the following (where the
bishop is crammed up in the corner):

BQRN....
BRK.....
.N......
[and then five empty rows]

Again, there might not be documentation showing this is best (worst?)
possible.

> I'm sort of thinking
> that the histogram should be symmetrical such that if the best case is 14=
4 as
> you say, then the worst should also be the same. It's an interesting ques=
tion.

--- Christopher Heckman

Date: 27 Sep 2007 22:25:28
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?

On Sep 27, 1:21 am, =AA=BA=AA rrock <[email protected] > wrote:
> Laurence Reeves wrote:
> > Proginoskes wrote:
>
> >> ... or a report of doing brute force.
>
> >> Thank you.
>
> > According to me, there is indeed no solution to the Eight Officers prob=
lem.
>
> > In 350 minutes on a P4 1.6GHz:
>
> > There are 144 distinct solutions to the problem of all but a single
> > square being attacked (which may be anywhere on the board).
>
> > In every case the king is attacked.
>
> > In precisely one instance a rook is in the square that is not attacked.
>
> > In seven cases a bishop is not attacked. Curiously, this is always the
> > bishop on the opposite colour square to the queen, which is itself
> > always on a d4 type square.
>
> > In ten cases a knight is not attacked and also in ten cases, the queen.
>
> > Is there somewhere useful to publish the results and/or the C program?
>
> The idea of a showing a histogram for all possible solutions was so that
> the numbers could be tabulated to show for certain that all cases had been
> considered, thus proving that any programming errors or heuristic
> problems could be ruled out as affecting the final answer of 63 being the
> maximum.

That would show that the proper number of boards was considered but
(by itself) would not indicate that the code that counts the number of
squares is correct.

> Unless i misunderstood the original post (again) it was in search
> of a formal proof and/or brute force report. A brute force program needs
> to somehow prove it has gone through all possible cases.

That would be part of the report itself.

--- Christopher Heckman

Date: 27 Sep 2007 15:57:37
From: Chip Eastham
Subject: Re: Source for Eight Officers Problem?

On Sep 27, 9:21 am, =AA=BA=AA rrock <[email protected] > wrote:

> You seem to be suggesting that this problem isn't computable. I have a
> version running at the moment which should complete (worst case estimate)
> in 170 days. That, by definition, is computable.

I didn't understand that to be Laurence's point. Rather
I think that a search program which fails to find a solution
to the Eight Officers Problem cannot "report" anything that
would be especially convincing of that fact.

Instead what you might provide as evidence is the program
itself, so that others can review the code and run it for
themselves to demonstrate the absence of any solution.

regards, chip

Date: 27 Sep 2007 14:14:33
From: =?ISO-8859-1?Q?=AA=BA=AA_rrock?=
Subject: Re: Source for Eight Officers Problem?

Chip Eastham wrote:

> On Sep 27, 9:21 am, �� rrock <[email protected]> wrote:
>
>
>>You seem to be suggesting that this problem isn't computable. I have a
>>version running at the moment which should complete (worst case estimate)
>>in 170 days. That, by definition, is computable.
>
>
> I didn't understand that to be Laurence's point. Rather
> I think that a search program which fails to find a solution
> to the Eight Officers Problem cannot "report" anything that
> would be especially convincing of that fact.
>
> Instead what you might provide as evidence is the program
> itself, so that others can review the code and run it for
> themselves to demonstrate the absence of any solution.
>
> regards, chip

A program that produces the coverage counts of each of the
possible board positions, and counts those, necessarily
proves both the minimum and maximum as well as the number
of counts for anything in between. The proof that the program
actually considered each of the possible board positions can
be verified by the sum of the counts.

For example, consider only a single king. The possible positions
are 64. There are three possible coverage counts: 3, 5, and 8.
The histogram for this reduced example would be:

Coverage Instances
3 4
5 24
8 36

Add up the instances and you get 36 + 24 + 4 = 64.

A program that performs the same function, but with all 8
officers, would have coverages ranging between "min" and
"max". The max is *supposedly* 63. So, the histogram would
therefore like the above shows "8" instead show "63". Adding
up the instances of the same should give the calculable
number of possibilities and therefore, prove that there
weren't any errors in the programming of the "loop".

Date: 27 Sep 2007 08:29:14
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?

On Sep 26, 6:22 pm, Laurence Reeves <[email protected] > wrote:
> Proginoskes wrote:
> > ... or a report of doing brute force.
>
> > Thank you.
>
> According to me, there is indeed no solution to the Eight Officers problem.
>
> In 350 minutes on a P4 1.6GHz:
>
> There are 144 distinct solutions to the problem of all but a single
> square being attacked (which may be anywhere on the board).
>
> In every case the king is attacked.
>
> In precisely one instance a rook is in the square that is not attacked.
>
> In seven cases a bishop is not attacked. Curiously, this is always the
> bishop on the opposite colour square to the queen, which is itself
> always on a d4 type square.
>
> In ten cases a knight is not attacked and also in ten cases, the queen.
>
> Is there somewhere useful to publish the results and/or the C program?

Good question. A good place to post preprints is http://xxx.lanl.gov/,
under the "Computer Science --- Other" category. (They don't have one
for "recreational mathematics"; the ACM doesn't have a classification
for it, either.) The advantage would be that more people would see the
article, and someone might know of where and when the problem was
originally solved. (THAT was the main reason I had for starting the
thread, and it's why this thread has been cross-posted to so many
groups. 8-) )

If there was a "Journal for Recreational Computing", I'd think that
would be a perfect place for the article. I'll have to think about it,
though.

--- Christopher Heckman

Date: 27 Sep 2007 02:22:07
From: Laurence Reeves
Subject: Re: Source for Eight Officers Problem?

Proginoskes wrote:
> ... or a report of doing brute force.
>
> Thank you.
>
> --- Christopher Heckman
>

According to me, there is indeed no solution to the Eight Officers problem.

In 350 minutes on a P4 1.6GHz:

There are 144 distinct solutions to the problem of all but a single
square being attacked (which may be anywhere on the board).

In every case the king is attacked.

In precisely one instance a rook is in the square that is not attacked.

In seven cases a bishop is not attacked. Curiously, this is always the
bishop on the opposite colour square to the queen, which is itself
always on a d4 type square.

In ten cases a knight is not attacked and also in ten cases, the queen.

Is there somewhere useful to publish the results and/or the C program?

--
Lau AS! d-(!) a++ c++++ p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++
ASC Decoder at <http://www32.brinkster.com/ascdecode/ >

Date: 27 Sep 2007 03:21:20
From: =?ISO-8859-1?Q?=AA=BA=AA_rrock?=
Subject: Re: Source for Eight Officers Problem?

Laurence Reeves wrote:
> Proginoskes wrote:
>
>> ... or a report of doing brute force.
>>
>> Thank you.
>>
>> --- Christopher Heckman
>>
>
> According to me, there is indeed no solution to the Eight Officers problem.
>
> In 350 minutes on a P4 1.6GHz:
>
> There are 144 distinct solutions to the problem of all but a single
> square being attacked (which may be anywhere on the board).
>
> In every case the king is attacked.
>
> In precisely one instance a rook is in the square that is not attacked.
>
> In seven cases a bishop is not attacked. Curiously, this is always the
> bishop on the opposite colour square to the queen, which is itself
> always on a d4 type square.
>
> In ten cases a knight is not attacked and also in ten cases, the queen.
>
> Is there somewhere useful to publish the results and/or the C program?
>

The idea of a showing a histogram for all possible solutions was so that
the numbers could be tabulated to show for certain that all cases had been
considered, thus proving that any programming errors or heuristic
problems could be ruled out as affecting the final answer of 63 being the
maximum. Unless i misunderstood the original post (again) it was in search
of a formal proof and/or brute force report. A brute force program needs
to somehow prove it has gone through all possible cases.

Date: 27 Sep 2007 12:24:28
From: Laurence Reeves
Subject: Re: Source for Eight Officers Problem?

�� rrock wrote:
>
>
> Laurence Reeves wrote:
>> Proginoskes wrote:
>>
>>> ... or a report of doing brute force.
>>>
>>> Thank you.
>>>
>>> --- Christopher Heckman
>>>
>>
>> According to me, there is indeed no solution to the Eight Officers
>> problem.
>>
>> In 350 minutes on a P4 1.6GHz:
>>
>> There are 144 distinct solutions to the problem of all but a single
>> square being attacked (which may be anywhere on the board).
>>
>> In every case the king is attacked.
>>
>> In precisely one instance a rook is in the square that is not attacked.
>>
>> In seven cases a bishop is not attacked. Curiously, this is always the
>> bishop on the opposite colour square to the queen, which is itself
>> always on a d4 type square.
>>
>> In ten cases a knight is not attacked and also in ten cases, the queen.
>>
>> Is there somewhere useful to publish the results and/or the C program?
>>
>
> The idea of a showing a histogram for all possible solutions was so that
> the numbers could be tabulated to show for certain that all cases had been
> considered, thus proving that any programming errors or heuristic
> problems could be ruled out as affecting the final answer of 63 being the
> maximum. Unless i misunderstood the original post (again) it was in search
> of a formal proof and/or brute force report. A brute force program needs
> to somehow prove it has gone through all possible cases.

Unfortunately, there is no such thing as you seem to be describing. As
with many problems of this nature, in order to keep run times to "within
a person's lifetime", one applies some intermediate whittling down of
possibilities.

In this case, where there remain more squares still not under attack
than the pieces remaining can possibly cope with, I discontinue that
pattern without attempting any specific locations for the remaining pieces.

Given the program, I can "prove" that it has gone through all possible
cases, by argument, but not by any numbers that it may print out.

If others were to look at my code, and be convinced that I had indeed
yielded the correct results, that would be a help, but hardly
conclusive. Fallacies have a habit of "looking OK".

If I publish the list of all 144 "solutions", someone might notice
patterns that enabled a direct proof that these are the only possible
cases. I doubt this. They seem pretty arbitrary.

Finally, and this is probably the only option, it would be a huge
confirmation if, /before/ I publish the results and program, someone
else were to at least confirm the count, and maybe publish what I say is
the unique solution where just the one rook remains unmolested.

I actually /do/ have a set of histograms that the program maintained.
These show how utterly disastrous placing the final piece was, because
it blocked so many of the prior pieces' attacks. Before placing it, I
had already rejected all patterns where the squares remaining not
attacked exceeded those it could cover. There was in fact a slight flaw
in my program (which occurred to me this morning). I was actually
allowing slightly more patterns through to this stage than I needed to.
I was allowing for up to one of each colour not to be attacked. I could
say this was a subconscious attempt to allow for a d1/c3 type pair
remaining not attacked, but it was in fact a slip up, which cost me
rather a lot of run time, I suspect.

I will run the program again, with the bug fix that will trim off a few
more dead-end layouts, just to see how much quicker it might reach the
same gross of results.
--
Lau AS! d-(!) a++ c++++ p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++
ASC Decoder at <http://www32.brinkster.com/ascdecode/ >

Date: 27 Sep 2007 08:21:07
From: =?ISO-8859-1?Q?=AA=BA=AA_rrock?=
Subject: Re: Source for Eight Officers Problem?

Laurence Reeves wrote:

> �� rrock wrote:
>
>>
>>
>> Laurence Reeves wrote:
>>
>>> Proginoskes wrote:
>>>
>>>> ... or a report of doing brute force.
>>>>
>>>> Thank you.
>>>>
>>>> --- Christopher Heckman
>>>>
>>>
>>> According to me, there is indeed no solution to the Eight Officers
>>> problem.
>>>
>>> In 350 minutes on a P4 1.6GHz:
>>>
>>> There are 144 distinct solutions to the problem of all but a single
>>> square being attacked (which may be anywhere on the board).
>>>
>>> In every case the king is attacked.
>>>
>>> In precisely one instance a rook is in the square that is not attacked.
>>>
>>> In seven cases a bishop is not attacked. Curiously, this is always
>>> the bishop on the opposite colour square to the queen, which is
>>> itself always on a d4 type square.
>>>
>>> In ten cases a knight is not attacked and also in ten cases, the queen.
>>>
>>> Is there somewhere useful to publish the results and/or the C program?
>>>
>>
>> The idea of a showing a histogram for all possible solutions was so that
>> the numbers could be tabulated to show for certain that all cases had
>> been
>> considered, thus proving that any programming errors or heuristic
>> problems could be ruled out as affecting the final answer of 63 being the
>> maximum. Unless i misunderstood the original post (again) it was in
>> search
>> of a formal proof and/or brute force report. A brute force program needs
>> to somehow prove it has gone through all possible cases.
>
>
> Unfortunately, there is no such thing as you seem to be describing. As
> with many problems of this nature, in order to keep run times to "within
> a person's lifetime", one applies some intermediate whittling down of
> possibilities.

You seem to be suggesting that this problem isn't computable. I have a
version running at the moment which should complete (worst case estimate)
in 170 days. That, by definition, is computable.

> In this case, where there remain more squares still not under attack
> than the pieces remaining can possibly cope with, I discontinue that
> pattern without attempting any specific locations for the remaining pieces.

> Given the program, I can "prove" that it has gone through all possible
> cases, by argument, but not by any numbers that it may print out.

That would be a formal proof then, or, rather sort of a mixing of a
formal proof and a heuristic program (i.e. not a brute force program).

> If others were to look at my code, and be convinced that I had indeed
> yielded the correct results, that would be a help, but hardly
> conclusive. Fallacies have a habit of "looking OK".

Well, if your results are correct, a brute force program will be able
to verify that they are. I doubt they are incorrect, but that isn't
the point here.

> If I publish the list of all 144 "solutions", someone might notice
> patterns that enabled a direct proof that these are the only possible
> cases. I doubt this. They seem pretty arbitrary.

144 being 12 squared, it sounds like there might be some validity to
that. I wouldn't discount that even though they look arbitrary to me,
for any reason, that there isn't an egg-head genius out there that
could/would see patterns like you or i see flannel.

> Finally, and this is probably the only option, it would be a huge
> confirmation if, /before/ I publish the results and program, someone
> else were to at least confirm the count, and maybe publish what I say is
> the unique solution where just the one rook remains unmolested.

Well, if you hang around for another few months... (grin)

>
> I actually /do/ have a set of histograms that the program maintained.
> These show how utterly disastrous placing the final piece was, because
> it blocked so many of the prior pieces' attacks. Before placing it, I
> had already rejected all patterns where the squares remaining not
> attacked exceeded those it could cover. There was in fact a slight flaw
> in my program (which occurred to me this morning). I was actually
> allowing slightly more patterns through to this stage than I needed to.
> I was allowing for up to one of each colour not to be attacked. I could
> say this was a subconscious attempt to allow for a d1/c3 type pair
> remaining not attacked, but it was in fact a slip up, which cost me
> rather a lot of run time, I suspect.

Well, those are exactly the sort of things that make your program more
of a heuristic model than a brute force proof. The difference between
the two allows that one must accept all of your heuristic notions as
true, and therefore, in a formal proof, each of those would need to
also be proven.

> I will run the program again, with the bug fix that will trim off a few
> more dead-end layouts, just to see how much quicker it might reach the
> same gross of results.

How exactly are you going about iterating through the various states of
the board?

Myself, i'm using a 48 bit word with 6-bits that designate the position
of each piece. In that manner, any complete setup of the board (with only
the 8 officers) can be iterated numerically. Any "legal" setup would have
zero instances of 6-bit "digits" that are equal within the same number.
After the program completes, the true exact number of legal states will
be confirmed. Did you ever come up with what that exact number should
be?

Earlier you wrote:
> 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.

Is that the *total* number of cases, or is that the number of cases
whittled down due to reflection and rotation as well?

The only cases my program isn't considering are those that have already
been considered by redundancy, i.e. where the two knights or the two
rooks are simply exchanged.

A full histogram will eventually prove that 63 is the highest possibility, *BUT*
it will also show what the WORST case coverage is as well. I'm sort of thinking
that the histogram should be symmetrical such that if the best case is 144 as
you say, then the worst should also be the same. It's an interesting question.

Date: 11 Oct 2007 07:25:33
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?

On Oct 10, 4:23 pm, =AA=BA=AA rrock <[email protected] > wrote:
> Peter Osterlund wrote:
>[...]
> i still think it's funny how in only a few
> short years... (well, okay 25 or 30 short years) ... nevermind...

That's going into my "quotes to keep" file! 8-)

> [...]
> > The big array is the attackShadow_ array, which is
> > 5*64*64*8=3D160KB. And I actually use two attackShadow_ arrays, one
> > indexed like [piece][square][blockingSquare] and the other indexed
> > like [piece][blockingSquare][square]. That wastes another 160KB of
> > memory, but makes the compiler generate better assembly code in the
> > inner loop. Since all three arrays combined are much smaller than the
> > L2 cache in the CPU, the extra memory usage isn't a problem.
>
> all together it's less than a meg.

Memory, schmemory. On a problem like this, time is more important.

--- Christopher Heckman

Date: 11 Oct 2007 11:53:18
From: =?ISO-8859-1?Q?=AA=BA=AA_rrock?=
Subject: Re: Source for Eight Officers Problem?

Proginoskes wrote:

> On Oct 10, 4:23 pm, �� rrock <[email protected]> wrote:
>
>>Peter Osterlund wrote:
>>[...]
>>i still think it's funny how in only a few
>>short years... (well, okay 25 or 30 short years) ... nevermind...
>
>
> That's going into my "quotes to keep" file! 8-)
>
>
>>[...]
>>
>>>The big array is the attackShadow_ array, which is
>>>5*64*64*8=160KB. And I actually use two attackShadow_ arrays, one
>>>indexed like [piece][square][blockingSquare] and the other indexed
>>>like [piece][blockingSquare][square]. That wastes another 160KB of
>>>memory, but makes the compiler generate better assembly code in the
>>>inner loop. Since all three arrays combined are much smaller than the
>>>L2 cache in the CPU, the extra memory usage isn't a problem.
>>
>>all together it's less than a meg.
>
>
> Memory, schmemory. On a problem like this, time is more important.
>
> --- Christopher Heckman

A meg is very small (these days). But in any case, what is more important
to me is a mathematical proof because with that, time goes to nil. The problem
with setting up the shadow arrays using an X/Y bitwalk and dropping out
the out-of-bounds cases is that there isn't any mathematical rule given
for any particular piece stated as a formula that yields only the correct
results. I don't mean that as a criticism of the code, whatsoever. It gets
the job done for that program's intentions.

What i mean to say is that just as given the size of a board by w (width) and
h (height) and the number of let's say for example rooks (r=2), that there is
already a well-known and proven formula for determining the number of positions
of those pieces as: wh * ( ( wh - 1 ) / 2 ). We *should* be able to determine
the answer to the "subset" question of the 8 officers by proving a formula that
answers the superset question: Given any w and h, and any number of pieces of
the various types k, q, o, e, n, and r, (where o is an odd bishop and e an even)
and given the other side of the equation as the zone of controlled squares as a
number z, what is the formula to determine Q cases for any given value of z?
With that formula, for the 8 officers question, w=8, h=8, k=1, q=1, o=1, e=1,
n=2, r=2, z=64, Q=0; and for the same with z=63, Q=144.

Given the zones of control as sets, the algorithm is only using the basic
intersections and unions of the sets. As described, the inner loop set up
for a non-symmetry and non-hopeless sort of check, still goes through a
predictable course of intersections and unions which can be stated
mathematically.

Date: 27 Sep 2007 17:04:44
From: Laurence Reeves
Subject: Re: Source for Eight Officers Problem?

�� rrock wrote:
>
>
> Laurence Reeves wrote:
>
>> �� rrock wrote:
>>
>>>
>>>
>>> Laurence Reeves wrote:
>>>
>>>> Proginoskes wrote:
>>>>
>>>>> ... or a report of doing brute force.
>>>>>
>>>>> Thank you.
>>>>>
>>>>> --- Christopher Heckman
>>>>>
>>>>
>>>> According to me, there is indeed no solution to the Eight Officers
>>>> problem.
>>>>
>>>> In 350 minutes on a P4 1.6GHz:
>>>>
>>>> There are 144 distinct solutions to the problem of all but a single
>>>> square being attacked (which may be anywhere on the board).
>>>>
>>>> In every case the king is attacked.
>>>>
>>>> In precisely one instance a rook is in the square that is not attacked.
>>>>
>>>> In seven cases a bishop is not attacked. Curiously, this is always
>>>> the bishop on the opposite colour square to the queen, which is
>>>> itself always on a d4 type square.
>>>>
>>>> In ten cases a knight is not attacked and also in ten cases, the queen.
>>>>
>>>> Is there somewhere useful to publish the results and/or the C program?
>>>>
>>>
>>> The idea of a showing a histogram for all possible solutions was so that
>>> the numbers could be tabulated to show for certain that all cases had
>>> been
>>> considered, thus proving that any programming errors or heuristic
>>> problems could be ruled out as affecting the final answer of 63 being
>>> the
>>> maximum. Unless i misunderstood the original post (again) it was in
>>> search
>>> of a formal proof and/or brute force report. A brute force program needs
>>> to somehow prove it has gone through all possible cases.
>>
>>
>> Unfortunately, there is no such thing as you seem to be describing. As
>> with many problems of this nature, in order to keep run times to
>> "within a person's lifetime", one applies some intermediate whittling
>> down of possibilities.
>
> You seem to be suggesting that this problem isn't computable. I have a
> version running at the moment which should complete (worst case estimate)
> in 170 days. That, by definition, is computable.

I was, of course, rather exaggerating. Six months is a bit of a long
time to wait. A previous problem I ran for six weeks continuous, except
that I was wise enough to set it up so that I could restart from
checkpoints (I had a few crashes over the period, an an odd power cut,
IIRC).

>
>> In this case, where there remain more squares still not under attack
>> than the pieces remaining can possibly cope with, I discontinue that
>> pattern without attempting any specific locations for the remaining
>> pieces.
>
>
>> Given the program, I can "prove" that it has gone through all possible
>> cases, by argument, but not by any numbers that it may print out.
>
> That would be a formal proof then, or, rather sort of a mixing of a
> formal proof and a heuristic program (i.e. not a brute force program).
>

I have utterly no heuristics in the program. It is entirely brute force.
It only discards partial layouts when it knows that they cannot possibly
achieve 63 (or more!) square coverage.

>
>> If others were to look at my code, and be convinced that I had indeed
>> yielded the correct results, that would be a help, but hardly
>> conclusive. Fallacies have a habit of "looking OK".
>
> Well, if your results are correct, a brute force program will be able
> to verify that they are. I doubt they are incorrect, but that isn't
> the point here.

Indeed, my point is that I don't trust myself not to have not only made
a mistake, but also to have made a mistake in such a "clever" way, that
it will be sufficiently persuasive as to fool others into missing it.

>> If I publish the list of all 144 "solutions", someone might notice
>> patterns that enabled a direct proof that these are the only possible
>> cases. I doubt this. They seem pretty arbitrary.
>
> 144 being 12 squared, it sounds like there might be some validity to
> that. I wouldn't discount that even though they look arbitrary to me,
> for any reason, that there isn't an egg-head genius out there that
> could/would see patterns like you or i see flannel.

:)

>> Finally, and this is probably the only option, it would be a huge
>> confirmation if, /before/ I publish the results and program, someone
>> else were to at least confirm the count, and maybe publish what I say
>> is the unique solution where just the one rook remains unmolested.
>
> Well, if you hang around for another few months... (grin)

OK. I'm waiting...

>> I actually /do/ have a set of histograms that the program maintained.
>> These show how utterly disastrous placing the final piece was, because
>> it blocked so many of the prior pieces' attacks. Before placing it, I
>> had already rejected all patterns where the squares remaining not
>> attacked exceeded those it could cover. There was in fact a slight
>> flaw in my program (which occurred to me this morning). I was actually
>> allowing slightly more patterns through to this stage than I needed
>> to. I was allowing for up to one of each colour not to be attacked. I
>> could say this was a subconscious attempt to allow for a d1/c3 type
>> pair remaining not attacked, but it was in fact a slip up, which cost
>> me rather a lot of run time, I suspect.
>
> Well, those are exactly the sort of things that make your program more
> of a heuristic model than a brute force proof. The difference between
> the two allows that one must accept all of your heuristic notions as
> true, and therefore, in a formal proof, each of those would need to
> also be proven.

Again, no heuristics are involved. I just examined, in detail, a few
layouts more than I needed to.

>> I will run the program again, with the bug fix that will trim off a
>> few more dead-end layouts, just to see how much quicker it might reach
>> the same gross of results.

At present, it seems to be progressing at about twice the speed.

> How exactly are you going about iterating through the various states of
> the board?

I'm not meaning to be particularly secretive about this, but I'd like a
"second head" independently picking on an algorithm.

> Myself, i'm using a 48 bit word with 6-bits that designate the position
> of each piece. In that manner, any complete setup of the board (with only
> the 8 officers) can be iterated numerically. Any "legal" setup would have
> zero instances of 6-bit "digits" that are equal within the same number.

A reasonable approach. I keep the eight in a plain "int" array.

> After the program completes, the true exact number of legal states will
> be confirmed. Did you ever come up with what that exact number should
> be?
>
> Earlier you wrote:
>> 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.
>
> Is that the *total* number of cases, or is that the number of cases
> whittled down due to reflection and rotation as well?

I don't think I said that. My (eventual) sum was (4*16 +
6*32)*31*(61*60?2)*(59*58/2)*57

I consider the queen first. If on a main diagonal (four cases), I
reflect the bishop of the opposite colour to one side of that diagonal.

If she's not on a main diagonal (six cases), that bishop can go anywhere.

That fully sorts out all symmetries, I think.

> The only cases my program isn't considering are those that have already
> been considered by redundancy, i.e. where the two knights or the two
> rooks are simply exchanged.

Actually, I'm somewhat surprised that your program is seeming to require
only six months to complete.

> A full histogram will eventually prove that 63 is the highest
> possibility, *BUT*
> it will also show what the WORST case coverage is as well. I'm sort of
> thinking
> that the histogram should be symmetrical such that if the best case is
> 144 as
> you say, then the worst should also be the same. It's an interesting
> question.

I would strongly doubt that the worst case was anything like the same
count. It could be millions or it could be one.

<http://www.gpj.connectfree.co.uk/gpjv.htm > gives some interesting info.
It was tedious, but I've verified that the twenty solutions listed there
are in my list.

--
Lau AS! d-(!) a++ c++++ p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++
ASC Decoder at <http://www32.brinkster.com/ascdecode/ >

Date: 29 Sep 2007 21:31:31
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?

Laurence Reeves <[email protected] > writes:

> ªºª rrock wrote:
>>
>> Laurence Reeves wrote:
>>
>>> Finally, and this is probably the only option, it would be a huge
>>> confirmation if, /before/ I publish the results and program,
>>> someone else were to at least confirm the count, and maybe publish
>>> what I say is the unique solution where just the one rook remains
>>> unmolested.
>>
>> Well, if you hang around for another few months... (grin)
>
> OK. I'm waiting...

You shouldn't have to wait that long.

My brute force program is currently running on a 2.4GHz Intel Core 2
Quad computer in 64 bit mode at a speed of approximately 120 million
positions per second. Since I didn't implement any symmetry detection
at all, the search space size is about 1.13e13, which means that the
computation should be finished in about 26 hours.

The output will be the histogram data and the "maximum" positions.
(Actually split up in 32 files because of how I implemented the
parallel search and checkpointing, but merging should be simple.)

--
Peter Osterlund - [email protected]
http://web.telia.com/~u89404340

Date: 11 Oct 2007 22:20:33
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?

On Oct 11, 9:53 am, =AA=BA=AA rrock <[email protected] > wrote:
> [...]
> But in any case, what is more important
> to me is a mathematical proof because with that, time goes to nil.

Yes; that was also my intention. Even something like showing that, if
the 8-O problem is possible, then the queen has to be on d4 (or one of
the other three central squares) would be a big jump. Not to mention
the fact that if you have one result like that, then the proof of
others should be easier.

> [...]
> What i mean to say is that just as given the size of a board by w (width)=
and
> h (height) and the number of let's say for example rooks (r=3D2), that th=
ere is
> already a well-known and proven formula for determining the number of pos=
itions
> of those pieces as: wh * ( ( wh - 1 ) / 2 ). We *should* be able to dete=
rmine
> the answer to the "subset" question of the 8 officers by proving a formul=
a that
> answers the superset question: Given any w and h, and any number of piece=
s of
> the various types k, q, o, e, n, and r, (where o is an odd bishop and e a=
n even)
> and given the other side of the equation as the zone of controlled square=
s as a
> number z, what is the formula to determine Q cases for any given value of=
z?
> With that formula, for the 8 officers question, w=3D8, h=3D8, k=3D1, q=3D=
1, o=3D1, e=3D1,
> n=3D2, r=3D2, z=3D64, Q=3D0; and for the same with z=3D63, Q=3D144.

There is, of course, a formula that will work, provided that you bound
w and h. (Just use Lagrange interpolation; Q will then be a nasty
polynomial in terms of w, h, k, q, o, e, n, r, and z.)

The 8-O problem has also been looked at with non-standard pieces. An
"Amazon" is a piece which can move like a queen or a knight.
Supposedly, if you replace a queen and a knight (from the eight
officers) with an amazon, you *can* control all 64 squares. (You
should be able to modify your program slightly and verify this
statement.)

I haven't seen any results involving other "fairy" pieces (what non-
standard pieces are called).

--- Christopher Heckman

Date: 11 Oct 2007 20:35:00
From: =?ISO-8859-1?Q?=AA=BA=AA_rrock?=
Subject: Re: Source for Eight Officers Problem?

Proginoskes wrote:

> On Oct 11, 9:53 am, �� rrock <[email protected]> wrote:
>
>>[...]
>>But in any case, what is more important
>>to me is a mathematical proof because with that, time goes to nil.
>
>
> Yes; that was also my intention. Even something like showing that, if
> the 8-O problem is possible, then the queen has to be on d4 (or one of
> the other three central squares) would be a big jump. Not to mention
> the fact that if you have one result like that, then the proof of
> others should be easier.
>
>
>>[...]
>>What i mean to say is that just as given the size of a board by w (width) and
>>h (height) and the number of let's say for example rooks (r=2), that there is
>>already a well-known and proven formula for determining the number of positions
>>of those pieces as: wh * ( ( wh - 1 ) / 2 ). We *should* be able to determine
>>the answer to the "subset" question of the 8 officers by proving a formula that
>>answers the superset question: Given any w and h, and any number of pieces of
>>the various types k, q, o, e, n, and r, (where o is an odd bishop and e an even)
>>and given the other side of the equation as the zone of controlled squares as a
>>number z, what is the formula to determine Q cases for any given value of z?
>>With that formula, for the 8 officers question, w=8, h=8, k=1, q=1, o=1, e=1,
>>n=2, r=2, z=64, Q=0; and for the same with z=63, Q=144.
>
>
> There is, of course, a formula that will work, provided that you bound
> w and h. (Just use Lagrange interpolation; Q will then be a nasty
> polynomial in terms of w, h, k, q, o, e, n, r, and z.)

I've heard of it, but it's beyond my current education. What i am thinking more
along the lines of are sets, and sets of sets. I'm unsure how it is written,
but worse, especially over the internet, but each of the 5 zone of control arrays in
Peter's program is a set of sets and should be able to be written mathematically.
Every "and" operation is an intersection of two sets and every "or" operation
is a union. In such a manner, a final intersection of two sets with z=64 would
give the "empty" set (or something along those lines).

The only bounds i can think of off hand:

all variables are integers

four variables that depend on w and h alone:

Let N = w * h ; and be the total sum of squares of a board.
Let O = w & h & 1 ; and be 1 for any case where both w and h are odd, or zero otherwise

Then let:

Ne = ( N + O ) / 2
No = ( ( N + O ) / 2 ) - O

and be the number of even squares and odd squares of a board respectively.

Then the following would be the only bounds i can think of off hand:

0 < w < infinity
0 < h < infinity

0 <= k <= N
0 <= q <= N
0 <= r <= N
0 <= n <= N
0 <= o <= No
0 <= e <= Ne
0 <= z <= N

k + q + n + r <= Ne - e
k + q + n + r <= No - o
k + q + n + r + o + e <= N

> The 8-O problem has also been looked at with non-standard pieces. An
> "Amazon" is a piece which can move like a queen or a knight.
> Supposedly, if you replace a queen and a knight (from the eight
> officers) with an amazon, you *can* control all 64 squares. (You
> should be able to modify your program slightly and verify this
> statement.)
>
> I haven't seen any results involving other "fairy" pieces (what non-
> standard pieces are called).

Some folks call the knights zone of control a circle, (but be forewarned
that some people whom aren't at all familiar with discrete math could get
very upset at such a thing, stomp their feet and start name-calling, etc..)
The Amazon would be adding one more square's radius to the immediate
circle surrounding the queen.

>
> --- Christopher Heckman
>

Date: 30 Sep 2007 01:30:28
From: Laurence Reeves
Subject: Re: Source for Eight Officers Problem?

Peter Osterlund wrote:
> Laurence Reeves <[email protected]> writes:
>
>> ªºª rrock wrote:
>>> Laurence Reeves wrote:
>>>
>>>> Finally, and this is probably the only option, it would be a huge
>>>> confirmation if, /before/ I publish the results and program,
>>>> someone else were to at least confirm the count, and maybe publish
>>>> what I say is the unique solution where just the one rook remains
>>>> unmolested.
>>> Well, if you hang around for another few months... (grin)
>> OK. I'm waiting...
>
> You shouldn't have to wait that long.
>
> My brute force program is currently running on a 2.4GHz Intel Core 2
> Quad computer in 64 bit mode at a speed of approximately 120 million
> positions per second. Since I didn't implement any symmetry detection
> at all, the search space size is about 1.13e13, which means that the
> computation should be finished in about 26 hours.
>
> The output will be the histogram data and the "maximum" positions.
> (Actually split up in 32 files because of how I implemented the
> parallel search and checkpointing, but merging should be simple.)
>

Sounds good, and exactly what my program needs - a confirmed count of
144*8=1152 solutions, by a totally different algorithm.

It may be a bit late, but if you are scanning the lot, there are several
problems worth solving. For a start, minimal coverings seem like an
intractable problem, without the total brute force approach, to me. The
maximal cover allows of my "pruning" techniques, en route to the
solutions. There's no equivalent when looking for minimal cover.

Out of interest, I ran a slightly modified version of my program which
took a little longer to run, but I accumulated some further counts.

I consider all 14,522,880 layouts with five pieces (QBBRR). By "pruning"
ones that cannot achieve 63 square coverage with the remaining KNN, I
only consider placing the king for 722,197,819 of those positions. My
pruning at this level has been of no great help (it prunes a mere one in
six cases, roughly).

However, when I have positioned the king, having just the two knight
left, only 10,614,749,047 positions go through. This time, three
quarters of the pack disappear. With just one knight on the board, there
is a huge drop to 103,784,180 only going through. I.e. this knight, on
balance, does far more harm by blocking attacks, than any good it does
by attacking an odd few squares. It has 58 squares to go on, but is
nearly 6,000 to 1 against yielding a route to a solution.

The last knight has an average of 28.5 squares to go on, but drops the
solutions by a factor of over 20 million to my 144.

=====================

There has been a reason behind my waffling. I have been having a thought
that is a little of a (k)nighte...

What is the maximal covering with seven officers?

I've seen 62. I'm just slightly worried that the answer to this might be
63, and terrified that it could be 64! :)
--
Lau AS! d-(!) a++ c++++ p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++
ASC Decoder at <http://www32.brinkster.com/ascdecode/ >

Date: 30 Sep 2007 07:07:04
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?

Laurence Reeves <[email protected] > writes:

> Peter Osterlund wrote:
>> Laurence Reeves <[email protected]> writes:
>>
>>> ªºª rrock wrote:
>>>> Laurence Reeves wrote:
>>>>
>>>>> Finally, and this is probably the only option, it would be a huge
>>>>> confirmation if, /before/ I publish the results and program,
>>>>> someone else were to at least confirm the count, and maybe publish
>>>>> what I say is the unique solution where just the one rook remains
>>>>> unmolested.
>>>> Well, if you hang around for another few months... (grin)
>>> OK. I'm waiting...
>>
>> You shouldn't have to wait that long.
>>
>> My brute force program is currently running on a 2.4GHz Intel Core 2
>> Quad computer in 64 bit mode at a speed of approximately 120 million
>> positions per second. Since I didn't implement any symmetry detection
>> at all, the search space size is about 1.13e13, which means that the
>> computation should be finished in about 26 hours.
>>
>> The output will be the histogram data and the "maximum" positions.
>> (Actually split up in 32 files because of how I implemented the
>> parallel search and checkpointing, but merging should be simple.)
>>
>
> Sounds good, and exactly what my program needs - a confirmed count of
> 144*8=1152 solutions, by a totally different algorithm.

Currently the program has found 637 63-square solutions after
exploring about 37% of the search space.

> It may be a bit late, but if you are scanning the lot, there are
> several problems worth solving.

I can run it again after I have the histogram data and know what
positions are interesting to store in the log files.

> For a start, minimal coverings seem
> like an intractable problem, without the total brute force approach,
> to me. The maximal cover allows of my "pruning" techniques, en route
> to the solutions. There's no equivalent when looking for minimal
> cover.

I think a branch and bound algorithm would be possible by using some
variation of the fact that there is an upper bound on how many
attacked squares can be shadowed by adding one more piece.

For example, if you place two knights and a king in the center of the
board, there is no way you can have a minimum covering no matter where
you place the other pieces.

I have no idea how efficent that B&B rule would be though.

--
Peter Osterlund - [email protected]
http://web.telia.com/~u89404340

Date: 30 Sep 2007 10:38:31
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?

Peter Osterlund <[email protected] > writes:

> Laurence Reeves <[email protected]> writes:
>
>> Peter Osterlund wrote:
>>> Laurence Reeves <[email protected]> writes:
>>>
>>>> ªºª rrock wrote:
>>>>> Laurence Reeves wrote:
>>>>>
>>>>>> Finally, and this is probably the only option, it would be a huge
>>>>>> confirmation if, /before/ I publish the results and program,
>>>>>> someone else were to at least confirm the count, and maybe publish
>>>>>> what I say is the unique solution where just the one rook remains
>>>>>> unmolested.
>>>>> Well, if you hang around for another few months... (grin)
>>>> OK. I'm waiting...
>>>
>>> You shouldn't have to wait that long.
>>>
>>> My brute force program is currently running on a 2.4GHz Intel Core 2
>>> Quad computer in 64 bit mode at a speed of approximately 120 million
>>> positions per second. Since I didn't implement any symmetry detection
>>> at all, the search space size is about 1.13e13, which means that the
>>> computation should be finished in about 26 hours.
>>>
>>> The output will be the histogram data and the "maximum" positions.
>>> (Actually split up in 32 files because of how I implemented the
>>> parallel search and checkpointing, but merging should be simple.)
>>>
>>
>> Sounds good, and exactly what my program needs - a confirmed count of
>> 144*8=1152 solutions, by a totally different algorithm.
>
> Currently the program has found 637 63-square solutions after
> exploring about 37% of the search space.

637 was wrong. I accidentally counted some 62-square solutions too.
Now after exploring exactly 50% of the search space, the program has
found 576 solutions.

I also realized that if I handle symmetries by making sure the
white-field bishop is in one of b1,c2,d3,d1, the search space will
shrink to exactly 1/8 of the full search space, and the histograms
should be equivalent.

With that change the program should be able to finish in about 3.25
hours, so I think I'll stop the current run and start a new one with
symmetry handling implemented.

--
Peter Osterlund - [email protected]
http://web.telia.com/~u89404340

Date: 30 Sep 2007 22:18:30
From: Laurence Reeves
Subject: Re: Source for Eight Officers Problem?

Peter Osterlund wrote:

> I also realized that if I handle symmetries by making sure the
> white-field bishop is in one of b1,c2,d3,d1, the search space will
> shrink to exactly 1/8 of the full search space, and the histograms
> should be equivalent.
>
> With that change the program should be able to finish in about 3.25
> hours, so I think I'll stop the current run and start a new one with
> symmetry handling implemented.
>

This is WRONG.

In all sorts of ways.

--
Lau AS! d-(!) a++ c++++ p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++
ASC Decoder at <http://www32.brinkster.com/ascdecode/ >

Date: 30 Sep 2007 22:23:03
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?

Laurence Reeves <[email protected] > writes:

> Peter Osterlund wrote:
>
>> [ Incorrect stuff ]
>
> This is WRONG.

Yes, I realized that after posting.

New attempt. I'm now restricting the king to the a1-d1-d4 triangle and
restricting the white bishop to the lower-right half if the king is on
the a1-d4 diagonal.

That gave the following histogram:

http://web.telia.com/~u89404340/officer_hist.png

The total sum is 1416372917760, the number of 63-solutions is 144, the
number of 16-solutions is 1.

I'm going to finish the original run without the symmetry code and
compare results, because getting the symmetry stuff right turned out
to be harder than I originally thought.

--
Peter Osterlund - [email protected]
http://web.telia.com/~u89404340

Date: 03 Oct 2007 14:43:20
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?

Peter Osterlund <[email protected] > writes:

> Laurence Reeves <[email protected]> writes:
>
>> Peter Osterlund wrote:
>>
>>> [ Incorrect stuff ]
>>
>> This is WRONG.
>
> Yes, I realized that after posting.
>
> New attempt. I'm now restricting the king to the a1-d1-d4 triangle and
> restricting the white bishop to the lower-right half if the king is on
> the a1-d4 diagonal.
>
> That gave the following histogram:
>
> http://web.telia.com/~u89404340/officer_hist.png
>
> The total sum is 1416372917760, the number of 63-solutions is 144, the
> number of 16-solutions is 1.

For those who might be interested, the full histogram data is here:

http://web.telia.com/~u89404340/officer_hist.txt

The source code (in C++, compiled with gcc) is here:

http://web.telia.com/~u89404340/officer.tar.bz2

--
Peter Osterlund - [email protected]
http://web.telia.com/~u89404340

Date: 03 Oct 2007 10:58:55
From: Kerry Liles
Subject: Re: Source for Eight Officers Problem?

"Peter Osterlund" <[email protected] > wrote in message
news:[email protected]...
... snipped ...
>>
>> That gave the following histogram:
>>
>> http://web.telia.com/~u89404340/officer_hist.png
>>
>> The total sum is 1416372917760, the number of 63-solutions is 144, the
>> number of 16-solutions is 1.
>
> For those who might be interested, the full histogram data is here:
>
> http://web.telia.com/~u89404340/officer_hist.txt
>
> The source code (in C++, compiled with gcc) is here:
>
> http://web.telia.com/~u89404340/officer.tar.bz2
>
> --
> Peter Osterlund - [email protected]
> http://web.telia.com/~u89404340

Thanks for posting the source code.
That looks like a very interesting thing to study on a rainy day (coming
soon I suspect).

regards,

Kerry Liles

Date: 01 Oct 2007 00:18:11
From: Laurence Reeves
Subject: Re: Source for Eight Officers Problem?

Peter Osterlund wrote:
> Laurence Reeves <[email protected]> writes:
>
>> Peter Osterlund wrote:
>>
>>> [ Incorrect stuff ]
>> This is WRONG.
>
> Yes, I realized that after posting.
>
> New attempt. I'm now restricting the king to the a1-d1-d4 triangle and
> restricting the white bishop to the lower-right half if the king is on
> the a1-d4 diagonal.
>
> That gave the following histogram:
>
> http://web.telia.com/~u89404340/officer_hist.png
>
> The total sum is 1416372917760, the number of 63-solutions is 144, the
> number of 16-solutions is 1.
>
> I'm going to finish the original run without the symmetry code and
> compare results, because getting the symmetry stuff right turned out
> to be harder than I originally thought.
>
Excellent stuff.

A nicely lop-sided, logarithmic histogram.

I particularly like the fact that you have chosen a fairly different way
to discard symmetries.

I'd get my solution list to you, if I knew what format you'd like it in.
I can't really see us differing on the detail. At present it's in a
format that was convenient for my program and grep/sed. I'll happily
munge it to read into whatever layout you like.
Be4Bf4Qa1Rb7Rh8Kf3Nd2Nb3 e6
Be4Bf4Qa1Rb7Rh8Kf3Nb3Ne3 e6
Be4Bf4Qa1Rb7Rh8Kf3Nb3Nc5 c4
Be4Bf4Qa1Rb7Rh8Kf3Nb3Ng5 c4
Be4Bf4Qa1Rb7Rh8Kf3Nb3Nd6 e6

I suppose I'm not surprised that there's just the unique 16 solution:
BB
QRN
RK
N
(as given earlier, via the link)

Once you've verified the counts against the symmetry-keeping version, I
have another task for you. My comment on the chance of there being a
seven officer 63 covering... I seem to have verified that there isn't
such a thing, when a knight is omitted. I'll modify and check for
leaving the king out. My program is a bit fiddly for this game. I
suspect yours is more adaptable, in its "include symmetry" mode.

It might be of interest to count the seven officer 62-coverings. Some
lurk in the 63-coverings, in effect.

Another three hour run on my puny box... but I'll be asleep.

I suppose I ought to check with one or other bishop omitted, a rook and
the queen. Tedious.

--
Lau AS! d-(!) a++ c++++ p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++
ASC Decoder at <http://www32.brinkster.com/ascdecode/ >

Date: 01 Oct 2007 19:35:49
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?

Laurence Reeves <[email protected] > writes:

> I have another task for you. My comment on the chance of there being a
> seven officer 63 covering... I seem to have verified that there isn't
> such a thing, when a knight is omitted. I'll modify and check for
> leaving the king out. My program is a bit fiddly for this game. I
> suspect yours is more adaptable, in its "include symmetry" mode.
>
> It might be of interest to count the seven officer 62-coverings. Some
> lurk in the 63-coverings, in effect.
>
> Another three hour run on my puny box... but I'll be asleep.
>
> I suppose I ought to check with one or other bishop omitted, a rook
> and the queen. Tedious.

I got the following results with my program:

Missing piece Max covering number of coverings
Knight 62 17 (full symmetry elimination)
Bishop 62 3 (incomplete symmetry elimination)
King 61 96 (no symmetry elimination)
Rook 59 74 (full symmetry elimination)
Queen 57 84 (full symmetry elimination)

"full symmetry elimination" means king in a1-d1-d4 and white bishop in
b1-h1-h7.

"Incomplete symmetry elimination" means king in a1-d1-d4 and bishop in
a1-h1-h8 (bishop allowed on both black and white squares), but that
doesn't eliminate all symmetries when both pieces are on the big
diagonal. I checked the 3 bishop cases manually and there are 2 unique
solutions if taking all symmetries into account.

The 96 "king" cases would translate to 12 cases if all symmetries were
eliminated.

Each seven officer run takes only about 6 minutes in the full symmetry
elimination case, because the search space is much smaller, and the
amount of work to do for each position decreases when there are fewer
pieces on the board.

The eight officer run is now down to 3 hours after I figured out a way
to make the compiler generate better code in the inner loop at the
expense of using some extra L2 cache. (Maybe it also makes the L2
cache access pattern better, I don't know.)

--
Peter Osterlund - [email protected]
http://web.telia.com/~u89404340

Date: 01 Oct 2007 16:20:14
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?

Laurence Reeves <[email protected] > writes:

> Peter Osterlund wrote:
>>
>> New attempt. I'm now restricting the king to the a1-d1-d4 triangle and
>> restricting the white bishop to the lower-right half if the king is on
>> the a1-d4 diagonal.
>>
>> That gave the following histogram:
>>
>> http://web.telia.com/~u89404340/officer_hist.png
>>
>> The total sum is 1416372917760, the number of 63-solutions is 144, the
>> number of 16-solutions is 1.
>>
> Excellent stuff.
>
> A nicely lop-sided, logarithmic histogram.
>
> I particularly like the fact that you have chosen a fairly different
> way to discard symmetries.
>
> I'd get my solution list to you, if I knew what format you'd like it
> in. I can't really see us differing on the detail. At present it's in
> a format that was convenient for my program and grep/sed. I'll happily
> munge it to read into whatever layout you like.
> Be4Bf4Qa1Rb7Rh8Kf3Nd2Nb3 e6
> Be4Bf4Qa1Rb7Rh8Kf3Nb3Ne3 e6
> Be4Bf4Qa1Rb7Rh8Kf3Nb3Nc5 c4
> Be4Bf4Qa1Rb7Rh8Kf3Nb3Ng5 c4
> Be4Bf4Qa1Rb7Rh8Kf3Nb3Nd6 e6

That format would be fine with me. Or you can do the check yourself
against my result file, which is here:

http://web.telia.com/~u89404340/officer_63.txt

The format is much more verbose, because it was convenient when I
wrote the program and wanted to manually verify the solutions it
found. After that I didn't bother to change it. It looks like this:

R.......
......R.
........
.....N..
....QN..
...B....
..K.....
......B.

********
********
*****.**
********
********
********
********
********

> Once you've verified the counts against the symmetry-keeping version,

That run is finished now, and I'm happy to report that every entry in
the histogram is exactly eight times larger than in the
symmetry-discarding version. I haven't checked all individual
solutions though.

--
Peter Osterlund - [email protected]
http://web.telia.com/~u89404340

Date: 27 Sep 2007 14:40:44
From: =?ISO-8859-1?Q?=AA=BA=AA_rrock?=
Subject: Re: Source for Eight Officers Problem?

Laurence Reeves wrote:

> �� rrock wrote:
>
>>
>>
>> Laurence Reeves wrote:
>>
>>> �� rrock wrote:
>>>
>>>>
>>>>
>>>> Laurence Reeves wrote:
>>>>
>>>>> Proginoskes wrote:
>>>>>
>>>>>> ... or a report of doing brute force.
>>>>>>
>>>>>> Thank you.
>>>>>>
>>>>>> --- Christopher Heckman
>>>>>>
>>>>>
>>>>> According to me, there is indeed no solution to the Eight Officers
>>>>> problem.
>>>>>
>>>>> In 350 minutes on a P4 1.6GHz:
>>>>>
>>>>> There are 144 distinct solutions to the problem of all but a single
>>>>> square being attacked (which may be anywhere on the board).
>>>>>
>>>>> In every case the king is attacked.
>>>>>
>>>>> In precisely one instance a rook is in the square that is not
>>>>> attacked.
>>>>>
>>>>> In seven cases a bishop is not attacked. Curiously, this is always
>>>>> the bishop on the opposite colour square to the queen, which is
>>>>> itself always on a d4 type square.
>>>>>
>>>>> In ten cases a knight is not attacked and also in ten cases, the
>>>>> queen.
>>>>>
>>>>> Is there somewhere useful to publish the results and/or the C program?
>>>>>
>>>>
>>>> The idea of a showing a histogram for all possible solutions was so
>>>> that
>>>> the numbers could be tabulated to show for certain that all cases
>>>> had been
>>>> considered, thus proving that any programming errors or heuristic
>>>> problems could be ruled out as affecting the final answer of 63
>>>> being the
>>>> maximum. Unless i misunderstood the original post (again) it was in
>>>> search
>>>> of a formal proof and/or brute force report. A brute force program
>>>> needs
>>>> to somehow prove it has gone through all possible cases.
>>>
>>>
>>>
>>> Unfortunately, there is no such thing as you seem to be describing.
>>> As with many problems of this nature, in order to keep run times to
>>> "within a person's lifetime", one applies some intermediate whittling
>>> down of possibilities.
>>
>>
>> You seem to be suggesting that this problem isn't computable. I have a
>> version running at the moment which should complete (worst case estimate)
>> in 170 days. That, by definition, is computable.
>
>
>
> I was, of course, rather exaggerating. Six months is a bit of a long
> time to wait. A previous problem I ran for six weeks continuous, except
> that I was wise enough to set it up so that I could restart from
> checkpoints (I had a few crashes over the period, an an odd power cut,
> IIRC).
>
>>
>>> In this case, where there remain more squares still not under attack
>>> than the pieces remaining can possibly cope with, I discontinue that
>>> pattern without attempting any specific locations for the remaining
>>> pieces.
>>
>>
>>
>>> Given the program, I can "prove" that it has gone through all
>>> possible cases, by argument, but not by any numbers that it may print
>>> out.
>>
>>
>> That would be a formal proof then, or, rather sort of a mixing of a
>> formal proof and a heuristic program (i.e. not a brute force program).
>>
>
> I have utterly no heuristics in the program. It is entirely brute force.
> It only discards partial layouts when it knows that they cannot possibly
> achieve 63 (or more!) square coverage.
>

I thought you had mentioned only considering non-rotational, non-reflective,
non-redundant cases... did you change your mind about that?

>>
>>> If others were to look at my code, and be convinced that I had indeed
>>> yielded the correct results, that would be a help, but hardly
>>> conclusive. Fallacies have a habit of "looking OK".
>>
>>
>> Well, if your results are correct, a brute force program will be able
>> to verify that they are. I doubt they are incorrect, but that isn't
>> the point here.
>
>
> Indeed, my point is that I don't trust myself not to have not only made
> a mistake, but also to have made a mistake in such a "clever" way, that
> it will be sufficiently persuasive as to fool others into missing it.
>

exactly.

>
>>> If I publish the list of all 144 "solutions", someone might notice
>>> patterns that enabled a direct proof that these are the only possible
>>> cases. I doubt this. They seem pretty arbitrary.
>>
>>
>> 144 being 12 squared, it sounds like there might be some validity to
>> that. I wouldn't discount that even though they look arbitrary to me,
>> for any reason, that there isn't an egg-head genius out there that
>> could/would see patterns like you or i see flannel.
>
>
> :)
>
>
>>> Finally, and this is probably the only option, it would be a huge
>>> confirmation if, /before/ I publish the results and program, someone
>>> else were to at least confirm the count, and maybe publish what I say
>>> is the unique solution where just the one rook remains unmolested.
>>
>>
>> Well, if you hang around for another few months... (grin)
>
>
> OK. I'm waiting...

My next step is to do two steps in parallel. If i can write that
in under 85 days (grin) then would you be willing to try and stay
alive a little longer?

>
>>> I actually /do/ have a set of histograms that the program maintained.
>>> These show how utterly disastrous placing the final piece was,
>>> because it blocked so many of the prior pieces' attacks. Before
>>> placing it, I had already rejected all patterns where the squares
>>> remaining not attacked exceeded those it could cover. There was in
>>> fact a slight flaw in my program (which occurred to me this morning).
>>> I was actually allowing slightly more patterns through to this stage
>>> than I needed to. I was allowing for up to one of each colour not to
>>> be attacked. I could say this was a subconscious attempt to allow for
>>> a d1/c3 type pair remaining not attacked, but it was in fact a slip
>>> up, which cost me rather a lot of run time, I suspect.
>>
>>
>> Well, those are exactly the sort of things that make your program more
>> of a heuristic model than a brute force proof. The difference between
>> the two allows that one must accept all of your heuristic notions as
>> true, and therefore, in a formal proof, each of those would need to
>> also be proven.
>
>
> Again, no heuristics are involved. I just examined, in detail, a few
> layouts more than I needed to.

Maybe i'm using the incorrect terminology. If there are certain cases that
you aren't considering, then, you are necessarily using your own cleverness
rather than the computer using pure computation. There is a difference
between *you* proving something and a computer proving it. The former is
along the lines of a formal proof. The latter is proven by brute force.

>
>>> I will run the program again, with the bug fix that will trim off a
>>> few more dead-end layouts, just to see how much quicker it might
>>> reach the same gross of results.
>
>
> At present, it seems to be progressing at about twice the speed.
>
>
>> How exactly are you going about iterating through the various states of
>> the board?
>
>
> I'm not meaning to be particularly secretive about this, but I'd like a
> "second head" independently picking on an algorithm.
>
>
>> Myself, i'm using a 48 bit word with 6-bits that designate the position
>> of each piece. In that manner, any complete setup of the board (with only
>> the 8 officers) can be iterated numerically. Any "legal" setup would have
>> zero instances of 6-bit "digits" that are equal within the same number.
>
>
> A reasonable approach. I keep the eight in a plain "int" array.

The performance gain using a compact 48-bit number is in the addition of the next
increment.

>> After the program completes, the true exact number of legal states will
>> be confirmed. Did you ever come up with what that exact number should
>> be?
>>
>> Earlier you wrote:
>>
>>> 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.
>>
>>
>> Is that the *total* number of cases, or is that the number of cases
>> whittled down due to reflection and rotation as well?
>
>
> I don't think I said that. My (eventual) sum was (4*16 +
> 6*32)*31*(61*60?2)*(59*58/2)*57

http://groups.google.com/group/alt.math.recreational/msg/9e8aaf8069328cae

> I consider the queen first. If on a main diagonal (four cases), I
> reflect the bishop of the opposite colour to one side of that diagonal.
>
> If she's not on a main diagonal (six cases), that bishop can go anywhere.
>
> That fully sorts out all symmetries, I think.
>

If those aren't heuristics, then what is the proper terminology?

>
>> The only cases my program isn't considering are those that have already
>> been considered by redundancy, i.e. where the two knights or the two
>> rooks are simply exchanged.
>
>
> Actually, I'm somewhat surprised that your program is seeming to require
> only six months to complete.

If all goes well, i should be able to knock it down to 40 days or so.
Its written in C, but only for the cosmetics, the actual computation
is in assembler. As mentioned earlier, i'm pretty sure i can cut it
in half by computing two steps in parallel.

>
>> A full histogram will eventually prove that 63 is the highest
>> possibility, *BUT*
>> it will also show what the WORST case coverage is as well. I'm sort of
>> thinking
>> that the histogram should be symmetrical such that if the best case is
>> 144 as
>> you say, then the worst should also be the same. It's an interesting
>> question.
>
>
> I would strongly doubt that the worst case was anything like the same
> count. It could be millions or it could be one.

The histogram is not symmetrical, but it does have a nicely plump center.
I thought it might have the normal curve to it, but at this point it is
still too early to make any guesses about it.

>
> <http://www.gpj.connectfree.co.uk/gpjv.htm> gives some interesting info.
> It was tedious, but I've verified that the twenty solutions listed there
> are in my list.

Date: 27 Sep 2007 22:34:05
From: Laurence Reeves
Subject: Re: Source for Eight Officers Problem?

�� rrock wrote:
...
> If those aren't heuristics, then what is the proper terminology?
...

My use of the term:

heuristic: an approach in problem solving where some avenues of
exploration of the problem are never explored because the solution is
not expected to be found there.

I seem not to agree with the OED on this one. Their definition are all
very vague and full of waffle. Maybe I should complain to them?

Chess playing programs are full of heuristic elements. E.g. one does not
bother to analyse what happens if one sacrifices half of one's pieces
before taking any of the opponent's pieces, because it is not expected
to form part of a winning strategy. In fact, sacrifices were always the
bane of early programs. The computer had trouble even contemplating
using them itself, and ignored the possibility that a human player might
use one.

A heuristic always implies that there is some possibility of a solution
being missed. E.g. "heuristic" approaches occur in finding the minimum
of a function. You can use a "hill descent" techniques, but you may find
only a local minimum. "Hill descent" is (generally) a heuristic.
Randomising the start for hill descent is another heuristic. Again, you
may be horribly unlucky and never find the minimum, only a series of
local minima.

Imagine the function defined mostly as y = x^2 on the range -1 <= x <=
1, but with y continuous and going down to -1 in the range
0.499999999999999999999999999 <= x <= 0.5000000000000000000000001. The
simple hill descent, plus randomised start, heuristic approach will be
rather unlikely to ever find the true minimum.

However, using a simple descent technique on what you knew to be a plain
quadratic is NOT a heuristic approach, as you can prove that you will
find THE minimum, to any degree of precision you require.

Other cases where heuristic approaches are perfectly acceptable are when
you either are only interested in establishing the existence of a
solution, or possibly you know exactly how many solutions there are,
hence you can reliably stop when you have found them all.

If there were a 64 coverage solution to the "Eight Officers" problem, a
heuristic approach that found at least one such solution would be fine.
To prove that no such solution exists is another matter.

Anyway, my program solves completely both questions "Is there a full
coverage solution?", to which the answer is "no" and "How many distinct
63 square coverage solutions are there?", being 144. (I think :) ) If I
change a "1" to a "2" in the code, I can get it to solve the "How many
distinct 62 square coverage solutions are there?" question as well.
There are quite a few, I would imagine. I suspect it would take rather a
lot longer to solve that question. I suppose I could leave it doing it
for a while.

I have in part described the algorithms I am using in the program. One
aspect of those algorithms is that I carefully avoid examining symmetric
cases right from the start. A second aspect is that I do not continue
placing pieces when I can simply count that those pieces cannot bring
the total under attack up to 63 (even if they did not block any other
pieces and each gave rise to a fresh attack on every square they could
possibly reach).

Another point to make is that I ensure that the innermost loops I use
are as efficient as I can make them. That innermost loop is executed 57
times for each time the next loop is taken. I.e. when I come to placing
the eighth piece on the board, everything must be already unpacked,
pre-calculated, etc, to make that operation as painless as can be.

=============================
The program finished its second run a while ago, with a little better
pruning, and all optimisations turned on (but debug still in place - a
mistake). This time it took 278 minutes, so no huge improvement over
last night's 350 minutes. The solution list was identical (phew!).
--
Lau AS! d-(!) a++ c++++ p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++
ASC Decoder at <http://www32.brinkster.com/ascdecode/ >

Date: 27 Sep 2007 19:24:28
From: Laurence Reeves
Subject: Re: Source for Eight Officers Problem?

Laurence Reeves wrote:
> <http://www.gpj.connectfree.co.uk/gpjv.htm> gives some interesting info.
> It was tedious, but I've verified that the twenty solutions listed there
> are in my list.
>
PS. The above page is slightly badly worded. The twentieth solution
shown has a footnote that mentions that there is a second position for
the king. Indeed there is. The page should really be stating that is
shows twenty-one distinct solutions.

PPS. I also forgot to mention that I now have noticed that arrangement 3
on that page is in fact the one that I mentioned as being the unique
solution with all but a rook attacked.
--
Lau AS! d-(!) a++ c++++ p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++
ASC Decoder at <http://www32.brinkster.com/ascdecode/ >

Date: 25 Sep 2007 14:37:39
From: Laurence Reeves
Subject: Re: Source for Eight Officers Problem?

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
>

First, with regard to your addendum problems, where solutions are known
to attack 63 squares, where the un-attacked squares are eight of the ten
distinct cases, there might be a third possibility.

If it transpires that there are NO solutions for attacking all 63 except
one, where that one is c3 or d1, it could then be the case that there
exist one or more solutions where a combined pair of such squares are
the only ones not attacked. I.e. the four cases of d1 with any of c3,
c5, f3 or f5.

============

Anyway, before wading in with yet another flawed attempt at an
algorithm, the post by Simon Waters prompts me to the following analysis
of symmetry reduction:

Place the queen first. She is either on or off a main diagonal.

There are six distinct off-main-diagonal positions for the queen. These
are immediately non-symmetric. The bishop of the opposite colour to the
square the queen is on has its full 32 options open to it.

For the queen on one of the four on-main-diagonal positions, again
consider the bishop of the opposing colour to that diagonal. Reflection
about the main diagonal containing the queen means we have just 16
distinct cases for it.

In both cases, the other bishop is going on a square of the same colour
as that that the queen is on, so has 31 possible places to go.

So, does that sound like (6*32+4*16)*31*(61*60/2)*(59*58/2)*57 =
1,416,372,917,760 possible distinct layouts?

===========

An algorithm which now starts to make sense to me would be get the
symmetry out of the way first, by placing the queen and the opposing
colour bishop.

Then place the other bishop and the rooks. There will now be some
arrangements where there is no use even looking at the knights or king,
as blocks will already mean that there remain more than 24 squares
needing to be attacked (QRR/-BB in a corner, e.g., leaves 35 - the
maximum?).

At this point, we have only needed to look at 14,522,880 cases - child's
play! It will be interesting to see what percentage of these are
discarded, due to not achieving the necessary 40 attacks.

Which piece to position next? I did incline towards the knights, because
they will tend to block pieces that attack squares the knight itself
will not attack, and hence are more likely to worsen the overall situation.

However, placing the king next may allow another swathe of abandonments.
What remains to be attacked by the remaining pair of knights must be no
more than sixteen squares ALL THE SAME COLOUR, or at most eight each of
opposing colours.

--
Lau AS! d-(!) a++ c++++ p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++
ASC Decoder at <http://www32.brinkster.com/ascdecode/ >

Date: 25 Sep 2007 07:01:00
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?

On Sep 19, 4:03 pm, Proginoskes <[email protected] > 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.

Now I have two related problems, one of which is solvable, and the
other not (yet).

(1) In the olden days, the moves of the bishop and queen were limited.
Bishops could jump over pieces (like knights do nowadays) but could
only move two squares diagonally. The queen could only move one square
diagonally. (Pawns, for the record, could only move one square per
move, even on their first move.) Using these rules, show that the
chessboard cannot be covered with the 8 pieces; i.e. the Eight
Officers problem here is impossible. [Solution at the end of this
post.]

(2) Several "near solutions" for the Eight Officers problem are given
at http://www.gpj.connectfree.co.uk/gpjv.htm (under "Near
Domination"). Any configuration can be rotated or reflected so that
the square which is not under attack is a1, b1, b2, c1, c2, c3, d1,
d2, d3, or d4. Eight of these ten possibilities are realized; two are
left. In other words:

(a) Is there a way to arrange the 8 officers so that all squares
except c3 are attacked?

(b) Is there a way to arrange the 8 officers so that all squares
except d1 are attacked?

--- Christopher Heckman

S
P
O
I
L
E
R
.
B
E
L
O
W
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Solution to (1): A rook can attack 14 squares; a knight and a king 8;
a bishop and a queen can attack 4. If we add up the number of squares
each piece can attack, we get a total of 14+14+8+8+8+4+4+4 = 64. Thus,
the Eight Officers problem is possible if no piece attacks a square
attacked by another piece, and no piece blocks any other. But two
rooks in the same row (or column) only attack 8+7+7 = 22 squares, not
the 28 needed, and two rooks not in the same row or column attack two
squares twice (unless the "path of attack" is blocked off). In any
case, the total falls short of the 64 required. QED.

Date: 27 Sep 2007 00:37:49
From: Laurence Reeves
Subject: Re: Source for Eight Officers Problem?

Proginoskes wrote:
> (b) Is there a way to arrange the 8 officers so that all squares
> except d1 are attacked?

R=======
=======R
==Q=====
========
====B===
===NBK==
===N====
===/====

Running a little slower toward the end. Five hours CPU so far. A couple
of queen positions to finish off. Four d1 solutions so far.

--
Lau AS! d-(!) a++ c++++ p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++
ASC Decoder at <http://www32.brinkster.com/ascdecode/ >

Date: 26 Sep 2007 21:00:35
From: Laurence Reeves
Subject: Re: Source for Eight Officers Problem?

Proginoskes wrote:
> (a) Is there a way to arrange the 8 officers so that all squares
> except c3 are attacked?

=====Q==
========
==K=N===
===BN===
=====B==
==/=====
R=======
=======R

This is not the only distinct solution for c3. I already have another
three. The program is churning slowly through the possibilities. It is
on the fourth and last of its edge positions for the queen with the six
non-edge positions to do, and has taken nearly two hours of my 1.6GHz
machine's time so far. I estimate another three hours to completion. It
has found 22 distinct solutions that attack all but one square.
--
Lau AS! d-(!) a++ c++++ p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++
ASC Decoder at <http://www32.brinkster.com/ascdecode/ >

Date: 25 Sep 2007 06:29:25
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?

On Sep 24, 6:31 am, Laurence Reeves <[email protected] > wrote:
> =AA=BA=AA rrock wrote:
> > Proginoskes wrote:
> >> On Sep 23, 2:11 am, =AA=BA=AA rrock <[email protected]> wrote:
> >>> Proginoskes wrote:
>
> >>>> Last night, I googled the Web for information about the Eight Office=
rs
> >>>> problem. (Put two rooks, two knights, two bishops, a queen, and a ki=
ng
> >>>> 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.
>
> > 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. [...]

This isn't always possible. If you rotate the board, the black squares
end up on (old) white squares and vice versa!

--- Christopher Heckman

Date: 25 Sep 2007 04:28:27
From: Simon Waters
Subject: Re: Source for Eight Officers Problem?

On Mon, 24 Sep 2007 22:52:36 +0000, Proginoskes wrote:

>
> Without reducing the number of cases due to symmetry, the answer is
> clearly 32*32*C(62,2)*C(60,2)*59*58, which turns out to be 12 trillion
> (I did this calculation last week with Maple), about 8 times larger than
> the number above.

Funny, I pondered placing the king first, and thus allow for reflection,
rotation and symmetry, by recognising there are only 10 distinct cases
for placing a king on such a board. I suspect we can without loss of
generality we can always place the king on a square of the same colour
(rotate board 90 degrees), thus one Bishop only has 31 choices.

10 32 31 C(61,2) C(59,2) 57 if your maths is right.

The problem is well within the reach of modern computing, the interesting
question is how to solve it without brute force.

If I was just looking for a solution (assuming the ancients are wrong),
I'd leave the king on the edge, and Knights on the same colour squares
(as that would leave 3 pieces only threatening squares of one colour),
cases till last when doing the brute force search.

Date: 24 Sep 2007 22:52:36
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?

On Sep 24, 6:31 am, Laurence Reeves <[email protected] > wrote:
> =AA=BA=AA rrock wrote:
>
> > Proginoskes wrote:
>
> >> On Sep 23, 2:11 am, =AA=BA=AA rrock <[email protected]> wrote:
>
> >>> Proginoskes wrote:
>
> >>>> Last night, I googled the Web for information about the Eight Office=
rs
> >>>> problem. (Put two rooks, two knights, two bishops, a queen, and a ki=
ng
> >>>> 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.
>
> > 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.

Without reducing the number of cases due to symmetry, the answer is
clearly 32*32*C(62,2)*C(60,2)*59*58, which turns out to be 12 trillion
(I did this calculation last week with Maple), about 8 times larger
than the number above.

> 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.

If you could also limit where certain other pieces have to go, you
could make the program faster.

> 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.

One of the things that makes this problem harder is that pieces can
block other pieces. rrock's example (elsewhere in the thread) isn't
really a solution then.

--- Christopher Heckman

> 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/>

Date: 24 Sep 2007 22:45:15
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?

On Sep 24, 2:54 pm, Mike <[email protected] > wrote:
> In article <[email protected]>, [email protected]=
nfo says...
>
> > =AA=BA=AA rrock wrote:
>
> > > Proginoskes wrote:
>
> > >> Last night, I googled the Web for information about the Eight Office=
rs
> > >> problem. (Put two rooks, two knights, two bishops, a queen, and a ki=
ng
> > >> 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
>
> > > How about this?
>
> > > +------+------+------+------+------+------+------+------+
> > >

Date: 24 Sep 2007 15:37:36
From: jeepyjay
Subject: Re: Source for Eight Officers Problem?

On Sep 24, 8:20 pm, =AA=BA=AA rrock <[email protected] > 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.
>
> > --- Christopher Heckman
>
> How about this?
>
> +------+------+------+------+------+------+------+------+
>

Date: 24 Sep 2007 14:20:57
From: =?ISO-8859-1?Q?=AA=BA=AA_rrock?=
Subject: Re: Source for Eight Officers Problem?

Date: 24 Sep 2007 22:16:51
From: Laurence Reeves
Subject: Re: Source for Eight Officers Problem?

�� 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.
>>
>> --- Christopher Heckman
>
> How about this?
>
> +------+------+------+------+------+------+------+------+
>

Date: 25 Sep 2007 09:54:44
From: Mike
Subject: Re: Source for Eight Officers Problem?

In article <[email protected] >, [email protected] s=
ays...
> =AA=BA=AA rrock wrote:
> >=20
> >=20
> > Proginoskes wrote:
> >=20
> >> 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
> >=20
> > How about this?
> >=20
> > +------+------+------+------+------+------+------+------+
> >

Date: 25 Sep 2007 01:48:14
From: =?ISO-8859-15?Q?=AA=BA=AA_rrock?=
Subject: Re: Source for Eight Officers Problem?

Mike wrote:
> In article <[email protected]>, [email protected] says...
>
>>�� 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.
>>>>
>>>> --- Christopher Heckman
>>>
>>>How about this?
>>>
>>>+------+------+------+------+------+------+------+------+
>>>

Date: 24 Sep 2007 05:25:46
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?

On Sep 23, 2:11 am, =AA=BA=AA rrock <[email protected] > 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

Date: 24 Sep 2007 01:51:01
From: =?ISO-8859-1?Q?=AA=BA=AA_rrock?=
Subject: Re: Source for Eight Officers Problem?

Proginoskes wrote:

> On Sep 23, 2:11 am, �� rrock <[email protected]> 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.

Date: 24 Sep 2007 14:31:07
From: Laurence Reeves
Subject: Re: Source for Eight Officers Problem?

�� rrock wrote:
>
>
> Proginoskes wrote:
>
>> On Sep 23, 2:11 am, �� rrock <[email protected]> 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/ >

Date: 24 Sep 2007 10:38:06
From: =?ISO-8859-1?Q?=AA=BA=AA_rrock?=
Subject: Re: Source for Eight Officers Problem?

Laurence Reeves wrote:

> �� rrock wrote:
>
>>
>>
>> Proginoskes wrote:
>>
>>> On Sep 23, 2:11 am, �� rrock <[email protected]> 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

I wasn't as lazy in the brunt of it, but lazier in the design:

I'm using short unsigned words for squares and an array of 768 for an over-sized board.
Rather than consuming time comparing/clipping moves that are out-of-bounds, i'm rendering
the moves onto the over-sized board and then using SSE parallel ops to do the counting
operation. Each word has a format using the sign-bit to denote it is under attack and
the lower 4 bits to denote what piece (if any) resides. This scheme would *probably*
run faster using full 32-bit dwords, but, then the SSE parallel ops would require more
memory fetches.

I finished it this morning and have one of my faster boxes ( relatively slow compared
to the "real world" ) running it.

Rather than trying to "cheat" the redundant cases, the program is a full-fledged
worst-case scenario brute force beast. The only cases that aren't considered are
when the placement of a piece would produce a collision (another piece being in
that square).

For testing, i have macros set to use any of 1 to 8 pieces and i was hoping to see
a pattern develop regarding the number of actual cases under consideration (redundancy
included).

Here's the tail-end output of using 5 pieces (King, Queen, Bishops, and a Knight):

Total squares attacked: 54
+------+------+------+------+------+------+------+------+

Date: 23 Sep 2007 04:11:47
From: =?ISO-8859-1?Q?=AA=BA=AA_rrock?=
Subject: Re: Source for Eight Officers Problem?

Date: 23 Sep 2007 08:55:47
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?

On Sep 22, 9:53 am, JillBones <[email protected] > wrote:
> On Sep 19, 4:03 pm, Proginoskes <[email protected]> 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

Date: 22 Sep 2007 09:53:20
From: JillBones
Subject: Re: Source for Eight Officers Problem?

Date: 21 Sep 2007 23:17:34
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?

On Sep 21, 9:18 am, "M Winther" <[email protected] > wrote:
> Den 2007-09-20 01:03:03 skrev Proginoskes <[email protected]>:
>
> > 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

Date: 22 Sep 2007 09:41:02
From: M Winther
Subject: Re: Source for Eight Officers Problem?

Den 2007-09-22 01:17:34 skrev Proginoskes <[email protected] >:

> On Sep 21, 9:18 am, "M Winther" <[email protected]> wrote:
>> Den 2007-09-20 01:03:03 skrev Proginoskes <[email protected]>:
>>
>> > 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

Date: 21 Sep 2007 18:18:23
From: M Winther
Subject: Re: Source for Eight Officers Problem?

Den 2007-09-20 01:03:03 skrev Proginoskes <[email protected] >:

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

Date: 20 Sep 2007 08:42:39
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?

On Sep 19, 6:49 pm, Proginoskes <[email protected] > wrote:
> On Sep 19, 6:35 pm, "Dan in NY" <[email protected]> wrote:
>
>
>
> > "Proginoskes" <[email protected]> wrote in messagenews:[email protected]...
>
> > > 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/chessforum.pl?kpage=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

Date: 20 Sep 2007 01:49:43
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?

On Sep 19, 6:35 pm, "Dan in NY" <[email protected] > wrote:
> "Proginoskes" <[email protected]> wrote in message news:[email protected]...
>
> > 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/chessforum.pl?kpage=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

Date: 19 Sep 2007 21:35:52
From: Dan in NY
Subject: Re: Source for Eight Officers Problem?

"Proginoskes" <[email protected] > wrote in message
news:[email protected]...
>
> 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

&&&
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/chessforum.pl?kpage=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.
--
Dan in NY
(for email, exchange y with g in
dKlinkenbery at hvc dot rr dot com)