Re: The n-knights problem

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

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

Relevant Pages

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