Re: The n-knights problem

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

Relevant Pages

  • 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)
  • 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
    ... }> Given just a description of an 8x8 chess board and the rules for ... need to deduce that knights can}> only threaten squares of the ... I peeked ahead in "Prolog ... knights only threaten squares of the opposite color. ...
    (comp.lang.prolog)