Zeroth Order Theories (ZOT's)
Jon Awbrey
jawbrey at oakland.edu
Wed Jan 30 16:00:30 CET 2002
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Let us continue to examine the properties of the cactus language
as a minimal style of declarative programming language. Even in
the likes of this zeroth order microcosm one can observe, and on
a good day still more clearly for the lack of other distractions,
many of the buzz worlds that will spring into full bloom, almost
as if from nowhere, to become the first order of business in the
latter day logical organa, plus combinators, plus lambda calculi.
By way of homage to the classics of the art, I can hardly pass
this way without paying my dues to the next sample of examples.
N Queens Problem
I will give the ZOT that describes the N Queens Problem for N = 5,
since that is the most that I and my old 286 could do when last I
wrote up this Example.
The problem is now to write a "zeroth order program" (ZOP) that
describes the following objective: To place 5 chess queens on
a 5 by 5 chessboard so that no queen attacks any other queen.
It is clear that there can be at most one queen on each row
of the board and so by dint of regal necessity, exactly one
queen in each row of the desired array. This gambit allows
us to reduce the problem to one of picking a permutation of
five things in fives places, and this affords us sufficient
clue to begin down a likely path toward the intended object,
by recruiting the following phalanx of 25 logical variables:
Lexical Input File: Q5.Lex
o---------------------------------------o
| |
| q1_r1, q1_r2, q1_r3, q1_r4, q1_r5, |
| q2_r1, q2_r2, q2_r3, q2_r4, q2_r5, |
| q3_r1, q3_r2, q3_r3, q3_r4, q3_r5, |
| q4_r1, q4_r2, q4_r3, q4_r4, q4_r5, |
| q5_r1, q5_r2, q5_r3, q5_r4, q5_r5. |
| |
o---------------------------------------o
Thus we seek to define a function, of abstract type f : %B%^25 -> %B%,
whose fibre of truth f^(-1)(%1%) is a set of interpretations, each of
whose elements bears the abstract type of a point in the space %B%^25,
and whose reading will inform us of our desired set of configurations.
Logical Input File: Q5.Log
o------------------------------------------------------------o
| |
| ((q1_r1 ),(q1_r2 ),(q1_r3 ),(q1_r4 ),(q1_r5 )) |
| ((q2_r1 ),(q2_r2 ),(q2_r3 ),(q2_r4 ),(q2_r5 )) |
| ((q3_r1 ),(q3_r2 ),(q3_r3 ),(q3_r4 ),(q3_r5 )) |
| ((q4_r1 ),(q4_r2 ),(q4_r3 ),(q4_r4 ),(q4_r5 )) |
| ((q5_r1 ),(q5_r2 ),(q5_r3 ),(q5_r4 ),(q5_r5 )) |
| |
| ((q1_r1 ),(q2_r1 ),(q3_r1 ),(q4_r1 ),(q5_r1 )) |
| ((q1_r2 ),(q2_r2 ),(q3_r2 ),(q4_r2 ),(q5_r2 )) |
| ((q1_r3 ),(q2_r3 ),(q3_r3 ),(q4_r3 ),(q5_r3 )) |
| ((q1_r4 ),(q2_r4 ),(q3_r4 ),(q4_r4 ),(q5_r4 )) |
| ((q1_r5 ),(q2_r5 ),(q3_r5 ),(q4_r5 ),(q5_r5 )) |
| |
| (( |
| |
| (q1_r1 q2_r2 )(q1_r1 q3_r3 )(q1_r1 q4_r4 )(q1_r1 q5_r5 ) |
| (q2_r2 q3_r3 )(q2_r2 q4_r4 )(q2_r2 q5_r5 ) |
| (q3_r3 q4_r4 )(q3_r3 q5_r5 ) |
| (q4_r4 q5_r5 ) |
| |
| (q1_r2 q2_r3 )(q1_r2 q3_r4 )(q1_r2 q4_r5 ) |
| (q2_r3 q3_r4 )(q2_r3 q4_r5 ) |
| (q3_r4 q4_r5 ) |
| |
| (q1_r3 q2_r4 )(q1_r3 q3_r5 ) |
| (q2_r4 q3_r5 ) |
| |
| (q1_r4 q2_r5 ) |
| |
| (q2_r1 q3_r2 )(q2_r1 q4_r3 )(q2_r1 q5_r4 ) |
| (q3_r2 q4_r3 )(q3_r2 q5_r4 ) |
| (q4_r3 q5_r4 ) |
| |
| (q3_r1 q4_r2 )(q3_r1 q5_r3 ) |
| (q4_r2 q5_r3 ) |
| |
| (q4_r1 q5_r2 ) |
| |
| (q1_r5 q2_r4 )(q1_r5 q3_r3 )(q1_r5 q4_r2 )(q1_r5 q5_r1 ) |
| (q2_r4 q3_r3 )(q2_r4 q4_r2 )(q2_r4 q5_r1 ) |
| (q3_r3 q4_r2 )(q3_r3 q5_r1 ) |
| (q4_r2 q5_r1 ) |
| |
| (q2_r5 q3_r4 )(q2_r5 q4_r3 )(q2_r5 q5_r2 ) |
| (q3_r4 q4_r3 )(q3_r4 q5_r2 ) |
| (q4_r3 q5_r2 ) |
| |
| (q3_r5 q4_r4 )(q3_r5 q5_r3 ) |
| (q4_r4 q5_r3 ) |
| |
| (q4_r5 q5_r4 ) |
| |
| (q1_r4 q2_r3 )(q1_r4 q3_r2 )(q1_r4 q4_r1 ) |
| (q2_r3 q3_r2 )(q2_r3 q4_r1 ) |
| (q3_r2 q4_r1 ) |
| |
| (q1_r3 q2_r2 )(q1_r3 q3_r1 ) |
| (q2_r2 q3_r1 ) |
| |
| (q1_r2 q2_r1 ) |
| |
| )) |
| |
o------------------------------------------------------------o
The vanguard of this logical regiment consists of two
stock'a'block platoons, the pattern of whose features
is the usual sort of array for conveying permutations.
Between the stations of their respective offices they
serve to warrant that all of the interpretations that
are left standing on the field of valor at the end of
the day will be ones that tell of permutations 5 by 5.
The rest of the ruck and the runt of the mill in this
regimental logos are there to cover the diagonal bias
against attacking queens that is our protocol to suit.
And here is the issue of the day:
Sense Output: Q5.Sen
o-------------------o
| q1_r1 |
| q2_r3 |
| q3_r5 |
| q4_r2 |
| q5_r4 | <1>
| q2_r4 |
| q3_r2 |
| q4_r5 |
| q5_r3 | <2>
| q1_r2 |
| q2_r4 |
| q3_r1 |
| q4_r3 |
| q5_r5 | <3>
| q2_r5 |
| q3_r3 |
| q4_r1 |
| q5_r4 | <4>
| q1_r3 |
| q2_r1 |
| q3_r4 |
| q4_r2 |
| q5_r5 | <5>
| q2_r5 |
| q3_r2 |
| q4_r4 |
| q5_r1 | <6>
| q1_r4 |
| q2_r1 |
| q3_r3 |
| q4_r5 |
| q5_r2 | <7>
| q2_r2 |
| q3_r5 |
| q4_r3 |
| q5_r1 | <8>
| q1_r5 |
| q2_r2 |
| q3_r4 |
| q4_r1 |
| q5_r3 | <9>
| q2_r3 |
| q3_r1 |
| q4_r4 |
| q5_r2 | <A>
o-------------------o
The number at least checks with all of the best authorities,
so I can breathe a sigh of relief on that account, at least.
I am sure that there just has to be a more clever way to do
this, that is to say, within the bounds of ZOT reason alone,
but the above is the best that I could figure out with the
time that I had at the time.
References: [BaC, 166], [VaH, 122], [Wir, 143].
[BaC] Ball, W.W. Rouse, & Coxeter, H.S.M.,
'Mathematical Recreations and Essays',
13th ed., Dover, New York, NY, 1987.
[VaH] Van Hentenryck, Pascal,
'Constraint Satisfaction in Logic Programming,
MIT Press, Cambridge, MA, 1989.
[Wir] Wirth, Niklaus,
'Algorithms + Data Structures = Programs',
Prentice-Hall, Englewood Cliffs, NJ, 1976.
http://mathworld.wolfram.com/QueensProblem.html
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000170
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
More information about the SeqFan
mailing list