NetNews Usenet Archive 1992 #19/NN_1992_19.iso/spool/comp/ai/3239

Internet Message Format | 1992-08-27 | 1.9 KB

Path: sparky!uunet!know!mips2!bull.bull.fr!lvbull.lv.bull.fr!lvbull!sanders
From: [e-mail] (Pablo.Sanders)
Newsgroups: comp.ai
Subject: Re: Knight's Tour
Message-ID: <[e-mail]>
Date: 26 Aug 92 09:56:36 GMT
References: <[e-mail]>
Sender: [e-mail]
Distribution: comp.ai,comp.theory
Organization: /atelier/sanders/.organization
Lines: 40
Nntp-Posting-Host: 129.181.184.211
In-reply-to: [e-mail]'s message of 12 Aug 92 19:51:40 GMT


I recently got flamed for talking about Constraint Programming
(CP) in this group, as it sounded like commercial advertising.
Let's make it clear: I am not trying to sell you anything, but
the 2 problems you quote (Knight and N-queens) are 2 classic
examples of CP, and you might be interested in knowing how
it is done:

Here is the complete code for the N queens problem, written
in the Charme programming language, a language that has a
C-like syntax.

define queens(N)
{
  array Q :: [1..N] of 1..N ; /* an array of integer values        */
  alldiff(Q);                 /* ...all elements must be different */
  for I in 1..N-1 do          /* ...constraints on the diagonals   */
    for J in I+1..N do {
      Q[I] + I != Q[J] + J;
      Q[I] + J != Q[J] + I;
    }
  generate (Q) ;              /* generates solution (s)    */
}

Constraint Propagation ensures that there is *very little*
backtrack involved in this program.

For the Knight tour problem, we first enumerate a graph of
of neighbours and then explore it after setting the constraints.

Do you like it ?


--
+------------------------o-------------------------+
| Pablo SANDERS          | Bull CEDIAG             |
| [e-mail] | 68, route de Versailles |
| phone: [phone] | 78430 Louveciennes      |
| fax  : [phone] | FRANCE                  |
+------------------------o-------------------------+