Re: The n-knights problem

russell kym horsell <kym@xxxxxxxxxxxxxxxxxxx> wrote in
news:ecu1sk$eu5$2@xxxxxxxxxxxxxxxx:

Lash Rambo <lr@xxxxxxxxxxxx> wrote:
} Lash Rambo <lr@xxxxxxxxxxxx> wrote in
} news:Xns982BC5DD04ED2lrfakeaddrcom@xxxxxxxxxxxx:
} > Given just a description of an 8x8 chess board and the rules for
how a } > knight can move, I want to write a Prolog program to
compute, through } > logic alone, the maximum number of knights that
can be placed on the } > board such that no knight attacks any other.
I don't care about } > specific configurations (as in the classical
8-queens problem), but } > would like a "proof" that the number it
comes up with is correct. } > I figure that first, the program would
need to deduce that knights can } > only threaten squares of the
opposite color. The program would then } > "realize" this property
applies no matter how many knights there are } > on the same color of
square. Then it'd come up with the answer: 32. } > There'd
undoubtedly be more steps, but that's the gist of it. Part of } > the
"proof" I'd like to see is those deductions it comes up with. } > It
sounds easy enough, but I've no idea how to even start. Any ideas } >
of how to set this up? } Hmm.... I peeked ahead in "Prolog
Programming for Artificial } Intelligence" and the last chapter deals
with "pattern-directed } programming" as applied to a simple automated
theorem prover. Both seem } very useful to the n-knights problem.
} Any other leads/suggestions would still be much appreciated!

A "proof" of correctness is not really part of a Prolog program --
more like something you do with a pencil & paper and concepts like
induction. :)

I figured the proof would be the easy part--the program just shows the
sequence of resolution steps used. What I foresee as the hard part is
getting the program to find, on its own, key deductions (inductions?)
that lead to a reasonably-sized proof. I suspect the big one for this
problem is: knights only threaten squares of the opposite color.

Another kind of proof of correctness -- and one ideally suited to
computation, but maybe not Prolog -- would be an exhaustive search.
I.e. there are 2^64 ways of positioning knights on a chessboard.
This is a rather large number, but you can use symmetry and futility
heuristics to eliminate a good proportion. Of the rest work backwards
from the upper bound on the number of knights until you find the first
config that works. :)

It *may* be possible to do something like this in Prolog.

Write a predicate that answers "can I place N knights on an 8x8
board?" and then try it with argument 64, 63, 62, ... 1 and the first
"yes" is what you're looking for.

Right. Those are the kinds of things I'm hoping to avoid by sticking to
logic and reasoning. After all, humans don't need to look at all those
possibilities to see the correct answer!
.

Relevant Pages

  • Re: The n-knights problem
    ... Lash Rambo wrote: ... }> Given just a description of an 8x8 chess board and the rules for how a ... the program would need to deduce that knights can ... but maybe not Prolog -- would be an exhaustive search. ...
    (comp.lang.prolog)
  • The n-knights problem
    ... Given just a description of an 8x8 chess board and the rules for how a ... the program would need to deduce that knights can only ... threaten squares of the opposite color. ...
    (comp.lang.prolog)
  • Re: The n-knights problem
    ... knight can move, I want to write a Prolog program to compute, through ... the program would need to deduce that knights can ... only threaten squares of the opposite color. ...
    (comp.lang.prolog)
  • Re: The n-knights problem
    ... alone, the maximum number of knights that can be placed on the board such ... the program would need to deduce that knights can only ... threaten squares of the opposite color. ...
    (comp.lang.prolog)