Re: The n-knights problem

Lash Rambo <lr@xxxxxxxxxxxx> wrote:
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!

Only if they want to prove (in the mathematical sense) that something
is correct. :)

A "proof" is not just a "demonstration", despite the translation of QED. :)

Non-mathematicians tend to confuse finding "a" solution to a problem --
something that may be easy -- with an answer that is
*provably* (in this case) the one with the maximum number of knights.

If you find "a" solution (e.g. -- from inspection we know there
are at least 32 of them on the board; you also can tell the answer is
not 64, 63 or 62, etc), how do you *prove* it is the
"best" configuration?

You somehow have to be able to "go through"
(perhaps not explicitly, but -- still -- *somehow*) each configuration
with more knights than your "found" solution, and prove that all these
other possibilities are not actually a legal solution.

That's the difference between a "proof" (what I'm talking about, above,
is a type of proof by induction), and a "guess" or "estimate" of the answer.

If you're after a proof-by-computer, you must somehow make the program
eliminate all possibilities except the one the program is claiming is
the "answer". And, technically, if you are trying to show a "proof" then
you must then prove the program is correctly written and can not possibly have
a mistake in it or have made a mistake when running. Proving a program is
correct can be a very, very tedious business, and typically takes an order of
magnitude more paper and pencil time than writing that program in the first place.

One way out of these tedia -- as I've indicated -- is to actually have a program
enumerate "all" possibilities explicitly, perhaps trimmed using futility
heuristics that are provably correct
(i.e. do not actually trim off anything that *may* be the answer),
to come up with some maximum number.

Just out of curiosity, a small program along these lines for this
particular problem enermates a maximum of 10^9 possible knight configurations,
finds the one with the largest number of knights, and terminates in well
under 2 seconds. Because the method is simple (enumeration) I know the
program is right and the answer is right. While a program that does
"mechanical induction" is also
reasonably straightforward (it's just another kind of branch-and-bound
problem, after all :), debugging it and getting it to run in reasonable
time, and having
confidence that it actually is working right might be a bit harder
to arrange than "enuermation of all the not-obviously-wrong possibilities".
.