Re: The n-knights problem

Lash Rambo <lr@xxxxxxxxxxxx> wrote:
russell kym horsell <kym@xxxxxxxxxxxxxxxxxxx> wrote in
news:ed0i72$nev$1@xxxxxxxxxxxxxxxx:
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.
Really? That's quite a prune down from 2^64!


C'mon. The problem can be solved by inspection. :)

Although I don't like to produce any proofs of my own -- I'm more into
demanding others to do that :) :) -- I'll attached a little Prolog program
that "proves" the solution to this puzzle. I put the proves in (") because
part of the proof -- the most important part -- are the considerations
that go into writing the program.

If you want to do this automatically -- then you need to write a Prolog
program that can write this program. Meta-programming is close(r?) to AI,
as they say.


Because the comments in the program are a bit obscure, let me try to
short-circuit any niggling compolaints about cheating or being an "***"
with the following.


We know that a knight on a white square does not attack any knight except those
on black squares. We therefore immediately know the maximum number of knights
that can be placed "amicably" on a std chessboard is >= 32.

We then ask -- is there a larger number?

I'll introduce 2 concepts -- "safe" and "maybe safe". A "safe" config
is one where DEFINTELY no 2 knights threaten each other. A "maybe safe"
config is one where we *think* the config maybe safe. But the main point is --
if a config is not "maybe safe" there is no way it could be "safe".

So is there a way to determine which values >32 and <= 64
are not "maybe safe" -- and hence not "safe"?

The program does this. Since it proves there is no config [33..64] which is
"maybe safe", there is no config [33,64] that is "safe". Hence 32 is the
maximum value. QEI.

Now, just write a program that will produce this:

(I apologise for the crappy style and format, most of which I blame
on windblows cut & paste and all those who sail with her.)

--- snippage ---
% The Knight Problem -- a "proof" by computer + human.
%
% This program finds the "provably correct" answer to the question: what
% is the maximum number of knights that can sit on a std chessboard
% without any knight threatening another?
%
% Since a knight on a white sq can only attack knights on black sqs we
% immediately see the minimum value for the number sought is 32 --
% i.e. the number of black (white) sq.
%
% In the terminology used here, we call such a value "known safe".
%
% To determine the maximum safe value it is sufficient to find a known
% safe value which is not exceeded by even a "maybe safe" value. A
% value is "maybe safe" if there may be a configuration of knights
% that occupy different sections of the chessboard where each section is
% "maybe safe".
%
% As before, we can say that (say) a 4x4 region of the chessboard is
% "safe" if it contains no more than 8 knights -- i.e. sitting on just
% the white squares.
%
% This program therefore tests values from 64 downto 32 and determines
% whether any are "maybe safe". The first "maybe safe" value is of
% interest. If no safe value exceeds the "known safe" value -- even by this
% weaker version of "safe" -- we are sure the known safe value is the
% largest possible value.
%
% The rest of the program is not explicitly documents as it is
% well-known the Prolog language does not admit programs that are not
% self-documenting, clear, and concise.
%
downto(X,Max,Min) :-
X is Max,
X>=Min.
downto(X,Max,Min) :-
Max1 is Max-1,
Max1 >= Min,
downto(X,Max1,Min).

maybe_safe(N,L,R,T,B) :-
NS is (B-T)*(R-L),
N =< NS/2,
!.
maybe_safe(N,L,R,T,B) :-
N>0,
Width is R-L,
Width > 4,
downto(I,N,0), %% i.e. for i from 0..N -- why write another predicate?
Rest is N-I,
Mid is (L+R)//2,
maybe_safe(I,L,Mid,T,B),
maybe_safe(Rest,Mid,R,T,B).
maybe_safe(N,L,R,T,B) :-
N>0,
Width is B-T,
Width > 4,
downto(I,N,0),
Rest is N-I,
Mid is (T+B)//2,
maybe_safe(I,L,R,T,Mid),
maybe_safe(Rest,L,R,Mid,B).

maybe_safe(X) :-
maybe_safe(X,0,8,0,8).

known_safe(32).


writeln(X) :- write(X), nl.


proof :-
downto(X,64,32),
maybe_safe(X),
writeln(maybe_safe(X)),
( known_safe(X) ->
writeln('since that is also know to be safe,'),
writeln('it must also be the maximum safe value'),
writeln('I thank you for your attention...')
),
!.

:- proof, halt.
--- end snippage ---



.