• Week by week
• Library including
• TD exercises and solutions
• Getting started with CHIP
• CHIP online documentation
• Project [Team Work]
• Evaluation [pdf | xls] marks proposed to the jury
• CLP final test 23 May 2006
• Prolog and Constraint Industry [CUC2006]

Week by week

• Week 1 : Wednesday 25 January 2006 repeated 1 February 2006
• Week 2 : Wednesday 8 February 2006
• Week 3 : Wednesday 22 February 2006 - Dr. Idir Gouachi, from Cosytec
• Week 4 : Wednesday 1 March 2006
• Week 5 : Wednesday 8 March 2006
• Week 6 : Wednesday 15 March 2006
• Week 7 : Wednesday 22 March 2006
• Week 8 : Wednesday 5 April 2006
• Week 9 : Wednesday 12 April 2006
• Week 10: Wednesday 26 April 2006

Week 1 : Wednesday 25 January 2006 repeated 1 February 2006

Lecture 1: Introduction to the module. Presentation of web information (Library, Prolog and Constraint Industry). [Printed version of Slides and Exercise list is available from Ms Françoise Verdier, computer science secretary: these are old versions, but very close to Library documents.]

Evaluation: based upon classical 2 hour final test, with or without taking project into account (?). Motivation: Sudoku problem.

Beginning of: LP, introduction, functional versus relational programming, first order logic syntax and semantics, validity of formulas,

lp.html slides 1--12.

Week 2 : Wednesday 8 February 2006

lp.html slides 24--46.

Week 3 : Wednesday 22 February 2006

Presentation by Dr. Idir Gouachi, from Cosytec:

• Part 1: CHIP, syntactic constraints, global constraints, with application examples;
• Part 2:  industrial applications with demonstrations.

Week 4 : Wednesday 1 March 2006

• n: function of arity 0, representing the empty list;
• c: function of arity 2, representing the "cons" function; c(E,L) represents the cons of element E and list L.

Week 5 : Wednesday 8 March 2006

Lecture 5: Very brief overview of CHIP constraints or builtin predicates needed for the N-queen puzzle:

• length(L, N): L is a list of length N;
• CLP(FD), Finite Domain constraints (::, #=, #\=, #>, #<, ...)
• X::1..N :  X is declared as a FD variable whose domain consists of the natural number interval [1, N],
• X #\= Y :  X and Y have different values; note that X and Y must have been declared as a FD variable;
• X #\= Y+n :  The values of X and Y+n are different; this extends the previous syntax: n must be a natural number;
• X #\= Y+N:  The values of X and Y+N are different; this generalizes previous syntax: N must be a rational variable which has been instantiated to some natural number;
• Remark: N could also be a FD variable already bound to some natural number, or a tree-domain variable bound to some natural number;
• 3*X + 4*Y #= 5*Z + U + 45, FD-equality (linear expressions, more tolerant syntax than for #\=);
• indomain(X): instantiate X in its domain (value generation); note that "indomain" may take and additional parameter to specify domain value selection ordering;
• labeling(Variables, 0, most_constrained, indomain): generalization of "indomain" to a list of FD variables: third and fourth argument respectively allow heuristic control over variable selection order and domain value selection order;
• CLP(Q), linear rational constraints ( ^=, ^\=, ^>, ^<, ...)
• 3*X + 4*Y ^= 5*Z + U + 45,
• X+1 ^= Y.
• useful for parameterizing a FD problem;
• CLP(trees), equivalent to pure Prolog;
• f(X, a) = f(b, Y),
• X = f(X, a)   has a solution in CHIP! see blackboard on photo at top of page (Infinite regular trees);
• These constraint languages communicate to some (weak) extent..

Week 6 : Wednesday 15 March 2006

• Operational semantics of LP (Pure Prolog): resolution, unification, search trees, see lp.htm slides 12--29, 47--50;
• Operational semantics of CLP:  search trees, CLP efficiency vs LP inefficiency, see clp.htm, slides 3--7;

• Students must form teams of three and send me a mail with team members (only 3 declared teams, so far);
• Suggestion for N²*N² Sudoku grid representation:
• A N*N matrix of N*N digit matrices
  [[m_1,1, ..., m_1,N],
  ...,
   [m_N,1, ..., m_N,N]],
• Each matrix m_i,j, with 1<=i, j <= N has the (similar) form:
  [[(m_i,j)_1,1, ..., (m_i,j)_1,N],
  ...,
   [(m_i,j)_N,1, ..., (m_i,j)_N,N]],
  and is composed of FD variables on domain 1..N;
• With emphasis on list structure as suggested above, one may avoid the manipulation of numbers to generate constraints; generating constraints essentially becomes list manipulation with appropriate predicates.

• read exercise XI from sheet (pdf | doc);
• copy ~gloess/chip/clp/exercises/money.pl template in your own directory;
• dont'look at ~gloess/chip/clp/solutions/money.pl until you have come up with your own solution!

Week 7 : Wednesday 22 March 2006

• Graphic interface:
• use CHIP 5.7 graphic environment (study documentation, XGIP, GAELLE, ...),
• or, use Java (web interface) and text file communication with CHIP;
• It is interesting to explain and compare both approaches.
• Interactive solver:
• Some interactive Sudoku solvers warn the user when he fills a box with a wrong number: this makes it too easy! CHIP can do better by warning the user only if the selected number is outside of the current domain of the corresponding variable. Let the user do the "labeling", and control the current domain of variables using "dom" or "dom2" builtin predicates;
• Sudoku grid generator:
• a parameter may be the desired percentage of empty boxes;
• There is a Sudoku generator written in Java which randomly fills a certain percentage of boxes until it comes up with a valid Sudoku (available on Internet). Does it really check that the generated grid yields only one solution?
• How do you measure the difficulty of Sudoku? Look for ideas on the web ...
• Some useful CHIP builtin primitives:
• "dom" and "dom2" predicates for consulting the domain of a finite domain variable;
• "random" and "seed" predicates for generation of random numbers.

TD 7: Mystery exercise:

• read exercise V from sheet (pdf | doc); we use "m" for "mystery", "c" for "cons", "n" for "nil", and "a", "b" instead of "1", "2";
• dont'look at the search tree of the "m(X, c(a, c(b, n)))" until you have drawn it yourself! 
• SLD resolution snapshots are also available (but SLD resolution proofs were not done in class this year).

Back to Week by Week or Top

Week 8 : Wednesday 5 April 2006

1. A flat list of N²*N² variables, together with access predicates relating an index to the corresponding line, column, or N*N square, or a pair of indexes to the corresponding box;
2. A list of N² lines, where each line is a list of N² variables.

Some student questions

1. Student: How can I check that a given Sudoku, more generally, a given query, has one solution and nomore?
1. Professor: CHIP (like most Prolog systems) provide two meta-predicates for collecting solutions of a query into a list:
1. set_of: duplicate solutions are eliminated from the list; the drawback is that "set_of" fails if there is no solution, instead of yielding the empty list;
2. findall: similar to set_of, but never fails; however, duplicate solutions may be collected in the list;
3. see ~gloess/chip/clp/solutions/findall.pl for the definition of a "findall_once" predicate that never fails and eliminates duplicate solutions;
2. Professor: The above solution is not practical, especially in the context of the Sudoku problem, because there may be a huge number of solutions, and we just want to know whether there are two or more. Deciding (efficiently) whether a query has at least two distinct solutions probably requires the use of the dirty "cut" construction, denoted "!". I did not talk about the "cut" in class, because it was mainly introduced for providing "negation by failure" in old Prolog, whereas CLP comes with clean and declarative negative constraints which are sufficient for most purposes. For more information, look at:
1. ~gloess/chip/clp/exercises/howManyPQ.pl, which implements efficient predicates related to this issue (for a specific "p(X)" or "q(X)" query); this can be easily generalized to any query, using some higher order logic available in CHIP and other Prolog systems;
2. search tree semantics of the cut slide, for a graphic explanation of  the "pruning" effect of the "cut";
2. Student: Do all teams have to write a general N²*N² Sudoku solver? Did not you say that teams could work on different aspects?
1. Professor: The general N²*N²Sudoku solver is not very difficult to write. I think all teams should work on it. But I also encourage teams to cooperate and work on different complementary aspects (see Week 6 for an outline); it is also true that a team could work on a completary aspect (such as a Sudoku grid generator) before having completed the general N²*N² Sudoku solver, because my specific general 3²*3² Sudoku solver is available for testing purposes;
3. Students: What do you expect from us as a deliverable?
1. Professor: I will write a precise description of what I expect from you. This will include:
1. a directory containing
1. an "index.html" file with links to a report (html or pdf) and CHIP and/or Java implementation;
2. a "report" directory containing the report;
   
3. a "chip" directory containing all the source CHIP files;
4. some other directories if needed (for example if there is a Java development);
2. a presentation and demonstration (30 minutes per team including questions and answers);
3. I intend to save student directories on this page.

Some useful CHIP programs

• ~gloess/chip/solutions/findall.pl (already mentioned);
• ~gloess/chip/clp/solutions/howManyPQ.pl (already mentioned);
• ~gloess/chip/clp/solutions/nth.pl (vector and matrix access).

Back to Week by Week or Top

Week 9 : Wednesday 12 April 2006

• random numbers in CHIP: look at "random" (and maybe "seed") in CHIP documentation.

Some useful CHIP programs or examples

• ~gloess/chip/solutions/findall.pl (already mentioned);
• ~gloess/chip/clp/solutions/howManyPQ.pl (already mentioned);
• ~gloess/chip/clp/solutions/nth.pl (vector and matrix access);
• ~gloess/chip/clp/solutions/sudokuExamples.pl (some sudoku examples and representation tests);
• ~gloess/chip/clp/solutions/transposeExamples.pl (some tests for "matrix transposition");

Back to Week by Week or Top

Week 10 : Wednesday 26 April 2006

• Explanations on the compiler:
• the technique used is now called "DCG" for "Definite Clause Grammars" rather than "metamorphosis grammars" as suggested in the CHIP compiler.pl program. Each terminal or non terminal in the original grammar is turned into a predicate. Predicates corresponding to terminals ("a", "b", "c", "+", "*", "(", ")" in the exemple under consideration) are defined using one clause only; predicates corresponding to non terminals are defined using as many clauses as there are in the grammar, for each one of them. The predicates take 3 arguments: the first two arguments are syntactic; the third one is semantic and represents the compiled code.
• Assuming p is a predicate corresponding to a terminal or non terminal p in the grammar, then:
• p(X, Y, P) means that:
• X and Y are lists of words (terminals),
• Y is a tail of X,
• the difference X-Y (that is, the list Z such that append(Z, Y, X) holds, note that it is a prefix of X) has the syntactic class p,
• P is the compiled code (we also say, translation, or semantic translation) corresponding to the source text X-Y.
• In other words, p(X, Y, P) means that X starts with a text of syntactic class p, which compiles into P, and ends with Y.
• It is easy to encode each terminal into a Prolog clause, e.g.:
• a([a | Y], Y, a).      % The sentence [a | Y] starts with terminal a and ends with Y; the translation is simply a itself, here.
• For non terminals, it is easy to encode each rule of the grammar into a Prolog clause, at least if one ignores the semantic translation (third argument), in a first approach, which we will assume here. The key idea is to use as many intermediate syntactic variables (-1) as there are elements in the right member of the rule.  Then the Chasle relation applies, e.g., X-Z = X-Y + Y-Z.
• For instance, the rule
      sumSequence ::=   + factor sumSequence
  will be turned into the Prolog clause:
• sumSequence(X, W) :- +(X, Y), factor(Y, Z), sumSequence(Z, W).
• A rule with empty right member, such as
      sumSequence ::= epsilon
  becomes a fact, here:
• sumSequence(X, X).  % X-X, the empty text [] has the syntactic class sumSequence.

• difficulties with "two or more solutions" in ~gloess/chip/clp/solutions/howManyPQ.pl wrt Sudoku project. Recall the definition (inspired from "twoP" predicate):
       twoSudokus(Sudoku1, Sudoku2) :- sudoku(Sudoku1), sudoku(Sudoku2), Sudoku1 \= Sudoku2, !.
  If in a goal of the form "twoSudokus(S1, S2)", sudoku grids S1 and S2 share variables, the query may artificially fail, although there may be two distinct solutions to the original Sudoku grid! Hence one should carefully separate S1 and S2 by letting them share only the original grid, e.g.:
• Assume the Grid is given as a list of the form [[i1, j1 | v1], ..., [iK, jK | vK]] where i1, j1, ..., iK, jK are coordinates and v1, ..., vK the corresponding mumerical values in the grid;
• Define a predicate emptySudoku such that "emptySudoku(N, S)" means that S is an empty sudoku grid of dimension N (that is, with N**4 elements);
• Define a fillSudoku predicate such that "fillSudoku(N, Grid, S)" means that S is a Sudoku grid of dimension N which agrees with Grid;
• Then, define twoSudokus (twoSudokus(N, Grid) means that there are at least two distinct complete sudoku  solutions to the Grid of dimension N) as follows:
• twoSudokus(N, Grid) :-
      emptySudoku(N, S1), fillSudoku(N, Grid, S1),
      emptySudoku(N, S2), fillSudoku(N, Grid, S2),
      sudoku(N, S1),
      sudoku(N, S2),
      S1 \= S2, !.
• Note that the "!" is here for efficiency (to force CHIP to stop at the first pair of distinct solutions), but is not useful if one uses twoSudokus inside a "not", because the "not" already performs a "!";
• A variant of the above idea may me used to define a "onlyOneSudoku" predicate for efficiently testing the existence of a unique Sudoku compatible with a Grid of dimension N,.

Recall some useful CHIP programs or examples.

Back to Week by Week or Top

Library

* Use ghostview with Landscape orientation and letter format.

Acrobat Reader: for easy access through your navigator, edit your preferences and associate "acroread %s" handler with "Portable Document Format" application.

Back to Top

---

Project

• Build a general size sudoku solver 
• + a general size sudoku generator
• with graphic and web interface
• ... and on line payment by credit card!
• see Week 4, Week6, Week 7, Week 8, Week 9 for more information on project.

Student teams and work.

Deliverable see additional ".htaccess" request 16 May 2006!

• Each team will notify me by e-mail (cc to all team members) of the address (URL) of the project directory, which should be under the "public_html" of one of the team member; no later than Monday 15 May 2006, 11:59pm;
• The project directory should contain:
• an "index.html" file with links to a report (html or pdf) and CHIP and/or Java implementation;
• a "report" directory containing the report;
  
• a "chip" directory containing all the source CHIP files, together with a ".htaccess" file containing the lines (added May 16, 2006):
      RemoveHandler .pl
      AddType text/plain   pl PL
• some other directories if needed (for example if there is a Java development);
• The report may be short (2 or 4 pages, for instance). It should:
• clearly identify the team members;
• start with a brief introduction;
• describe the state of achievement: is the general size sudoku solver operational? What other features have been provided among the suggested ones (generator, graphic and/or interface, ...) and what is the state of achievement of each such feature;
• give the essential ideas underlying the implementation of each feature (for those who have used XGIP or GAELL for graphics, some explanation of what has been used, and some comparison with other known tools, is welcome);
• describe the purpose of each CHIP file (and its main predicates);
• give some assessment of the efficiency of your tool: size of the sudokus you can solve or generate (dimension and number of blank boxes in the sudoku grids you can generate, time needed for solving or generating sudokus, ...);
• not give the detail of each predicate;
• end with some conclusion and perspective.
• The CHIP source code should consist of one or more ".pl" files located in the "chip" directory. Each file should be composed of
• A banner identifying the authors (the team members), their school (ENSEIRB), ..., the date, the general purpose of the file;
• The predicate definitions. For each predicate p of arity N, there should be
• A comment explaining the precise meaning of the predicate, in the form:
• /*   p(X1, ..., XN)
        --------------
            means that  <some sentence referring to X1, ..., XN>
  */
• Note that X1, ..., XN should be well chosen (meaningful) distinct symbols;
• The name of the predicate should also be meaningful;
• the clauses defining the predicate p of arity N. [It is usually not necessary to include comments with clauses; variable names should be carefully chosen, and compatible with those used in the comment defining the predicate meaning.].
• A commented zone containing queries:
• Each query should start with a brief comment related to the query;
• Each query should be runnable as the first one in a CHIP session (do not assume that anything has been "reconsulted" prior to the query).
• If you have used Java or other programming languages, you know the rules better than I do ...;
• I intend to save your directories on this CHIP 2005-2006 page. Bon courage!

Public defence

• 20 minutes per team, mostly for a demo (prepare a demo on a terminal); whiteboard will be available for a brief explanation of the work (if necessary): no slide presentation is required;
• teams will defend their project in the order of the list;
• teams are not requested to attend other team defence; teams should prepare their demo ahead of time on a terminal;
• as always, there may be some delay ... so that you may have to wait!
• See you!

Back to Top

Prolog and Constraint Industry

• Cosytec
• ILog
• PROLOGIA
• AFPLC (association)
• ALP (association)

© Copyright 1999-3000 Paul Y Gloess