Cool Samples

This page is a short repository of CLAIRE programs, associated to small puzzles, that are a good way to learn about CLAIRE's style of programming.

For each puzzle, I will also comment about what GPT4 can do, which is both interesting to see the strength and limits of Generative AI today, and to convince oneself that there is still room for "elegant programming"

A new puzzle will be published once in a while ... for some of them, chatGPT does a good job, and its answer are improving constantly so I will update the genAI section.

Here is the current list

March 17th, 2024


N-Queens Problems



This is a favorite problem of constraint programming. It is easy to state, and easy to solve for 8 queens. For larger board, say 64 queens, it is a good toy problem of constraint programming because it requires a bit of thinking, the simple enumeration does no longer work.

    Here are the prompts that I used for our genAI tools: 


can you place 8 queens on a chessboard so that no queen attack each other ?

can you do the same on a 64x64 chess board with 64 queens ?



// a naive N-queen problem


N:integer := 64


column[n:(1 .. N)] : (0 .. N) := 0     // 0 for no values yet

possible[x:(1 .. N), y:(1 .. N)] : boolean := true

countPos[n:(1 .. N)] : (0 .. N) := N


 // two defeasible attributes   

store(column, possible, countPos)


// remove a possible value

forbid(x:(1 .. N),y:(1 .. N)) : void

 -> (if (column[x] = 0 & possible[x,y])

       (possible[x,y] := false,

        countPos[x] :- 1,

        if (countPos[x] = 0) contradiction!()))


// three rules that implement the allDifferent constraints

r1() :: rule(

   column[x] := z => for y in ((1 .. N) but x) forbid(y,z))


r2() :: rule(  

       column[x] := z => let d := x + z in

                           for y in (max(1,d - N) .. min(d - 1, N))

                               forbid(y,d - y))

r3() :: rule(  

       column[x] := z => let d := (z - x) in

                           for y in (max(1,1 - d) .. min(N,N - d))

                               forbid(y,y + d))


 // finds the queen with the fewest choices

tightest()

 -> let m := N + 1, best := 0 in

      (for j in (1 .. N)

         (if (column[j] = 0 & countPos[j] < m)

             (best := j, m := countPos[j])),

       best)

          

// explore the search space using the "branch" CLAIRE control structure

queens(n:integer) : boolean

   -> (if (n = 0) true

           else let q := tightest() in

         exists(p in (1 .. N) |

         (possible[q,p]  &

                     branch( (column[q] := p, queens(n - 1)) ))))

 

// print the solution

 solution() -> list{column[i] | i in (1 .. N)}



ChatGPT does a very good job with the original 8 x 8 problem.

Yes, the 8 queens have been placed on the chessboard in such a way that no queen can attack each other. Here's one of the possible arrangements represented in a matrix form, where 1 indicates the presence of a queen and 0 indicates an empty space. ​

It displays the output of a python generated program, that is a proper 8 x 8 grid. As we have seen with the knapsack problem, it uses Python generation, so getting the answer is a little slow, but OK.

However, if you ask for the 64x64 problem, you see that two step are happening:

(1) it tries the same approach but the Python code does not work, so you get a failure message

(2) then it continues and returns with the following message :  


The attempt to place 64 queens on a 64x64 chessboard using the same recursive backtracking algorithm took too long to execute, which is expected due to the algorithm's exponential time complexity. For large chessboards like 64x64, a more efficient approach can be used since the problem has a known solution pattern. We can simply place one queen per row in a different column, which can be done in a linear fashion without the need for backtracking.

Let me show you this approach for a 64x64 chessboard. ​​

Yes, I've successfully placed 64 queens on a 64x64 chessboard using a linear approach. Each queen has been placed on a different row and column along the diagonal, ensuring that no queen can attack another. The sum of the queens on the board is 64, confirming that each of the 64 queens has been placed without any conflicts. ​

This idea of looking for a "heuristic pattern" does make sense, so I asked to look at the generated Python code, which is a bit messy , so I got suspicious and I asked to see the solution.


I've placed 64 queens on a 64x64 chessboard, with each queen on its own row and column along the diagonal. Here's a snippet of the board representation:

Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

...


Each 'Q' represents a queen, and each '.' represents an empty square. This pattern continues with one queen placed on each diagonal from the top left to the bottom right, ensuring that no queens are able to attack each other. This solution works for any size of the chessboard, provided the number of queens is equal to the size of one of the board's dimensions. ​

So the answer is clearly wrong, but as usal, ChatGPT is still cheerful and pretty sure of itself :)

We  get a similar story with Gemini (disclaimer : as a French resident, I have not access to the best versions from Google). Gemini does a good job with the 8 x 8 problem:


Absolutely! Here's one way to place 8 queens on a chessboard so no queen attacks each other (many other solutions exist):

This is just one solution.  There are 92 total solutions to the 8 queens puzzle.

With a larger problem such as 64 x 64 we get a totally false answer. This one is a gem, a perfect example of "bullshitting with confidence", telling you that the problem has no solutions !


Unfortunately, placing 64 queens on a 64x64 chessboard such that no queen attacks another isn't possible. Here's why:

Therefore, with 64 queens on a 64x64 board, it's impossible to find a configuration where no queen attacks another.

September update using o1-preview :  ChatGPT finds a solution and proves elegantly that it is correct !


This CLAIRE code is quite naive but works well on sizes 8,16, 32 or 64 (classical ones). It finds the solution with the interpreter almost instantly (290 ms for the 64x64 problem). I give a solution here to convince you that Gemini is seriously hallucinating.


solution()

eval[2]>list(1, 3, 5, 27, 34, 4, 43, 7, 51, 57, 62, 42, 6, 54, 56, 50, 8, 30, 39, 58, 36, 31, 9, 41, 38, 29, 37, 33, 40, 10, 21, 24, 64, 53, 59, 63, 14, 11, 61, 48, 55, 60, 47, 2, 17, 52, 12, 44, 46, 26, 35, 20, 32, 28, 49, 45, 13, 22, 16, 19, 23, 15, 18, 25)


The CLAIRE user will notice that the code is the same as the one proposed in the reference manual with one difference : we use the classical heuristics from constraint programming of selecting the "tightest" queen at each branching step, that is the queen that has the remaining smaller number of possible position.

Here are a few comments to make this code easier to read:

Finding a solution works really well under the interpreter, counting them would justity comping the code to get accelerated performances.


February 18th, 2024


Knapsack Problems




Peter goes into a shop with 10000$.
The items on the shelves cost 1103, 2057, 3208, 968, 1207, 3047, 2176, 860, 2195, 1307, 928, 2210, 3044, 2177, 1081, 2204, 999, 2188, 1057, 2478. what is the combination of things that can by with the exact amount of his money ?.


Luke enters a jewellery with 150000$.
The items cost 10104, 8956, 4208, 16368, 6106, 18946, 21076, 9460, 17190, 23108, 13028, 20210, 8844,  5172, 980, 3204, 15098, 7188, 4850, 12376, 13220, 8210, 12330, 4148, 7750, 10078, 20104, 16130, 12274, 7852, 19146, 4150, 9150, 5550.
Can Luke spend exactly his money on some of these items ? which combination can he buy ?

 



// simple knapsack = complexity O(n2 x m)
// knap(l,val) finds one of the optimal solution (closest to val)


// how to find the best combination of items to put in a knapsack of capacity val

[knap(l:list<integer>,val:integer) : void

 -> let n := length(l), m := max(< @ integer,l), mx := 0, best := 0,

     possible := list{ false | i in (1 .. (n * m))},

     sol := list{ nil | i in (1 .. (n * m))} in

     (for x in l

       (let i := mx in

          (while (i > 0)

            (if possible[i]

                (possible[i + x] := true,

                 sol[i + x] := sol[i] /+ list(x)),

             i :- 1)),

        possible[x] := true,

        sol[x] := list(x),

        mx := (mx + x)),

      for i in (1 .. min(mx,val))

           (if possible[i] best := i),

      list(best,sol[best]))]


// test set

S4 :: list<integer>(1103, 2057, 3208, 968, 1207, 3047, 2176, 860, 2195, 1307, 928, 2210,

                   3044, 2177, 1081, 2204, 999, 2188, 1057, 2478)

S5 :: list<integer>(10104, 8956, 4208, 16368, 6106, 18946, 21076, 9460, 17190, 23108, 13028, 20210, 8844, 5172, 980, 3204, 15098, 7188, 4850, 12376, 13220, 8210, 12330, 4148, 7750, 10078, 20104, 16130, 12274, 7852, 19146, 4150, 9150, 5550)


ChatGPT does a very good job with small problems.
It first start in the wrong direction ... telling you that it is "analyzing" ... and then start another path and returns with the solution:

Peter can spend exactly his $10,000 by purchasing items with the following costs: $1103, $1207, $2195, $2210, $1081, and $2204. This combination of items adds up precisely to the total amount he has. ​

If you ask to see the analysis, you can see that ChatGPT has generated a piece of python code to explore the search space.

However, if you ask for the second example, you get : 


Given the complexity of finding an exact combination of items that sum up to $150,000, especially with such a large list of items and a high target value, solving this problem requires a careful approach. Traditional methods like dynamic programming might not be efficient due to the large state space.

However, we can attempt to find a solution using a more efficient algorithm that's suitable for solving subset sum problems of this scale, acknowledging that full enumeration might be impractical due to computational constraints. We'll implement an approximation or a heuristic to check if it's feasible to find a combination close to the target value or to identify if an exact match is possible with a simplified approach.

Let's attempt to find if an exact match is possible with the understanding that we might only be able to determine the feasibility rather than provide the exact combination due to the computational complexity involved.

Given the computational complexity involved in finding an exact combination of items that sum up to $150,000 from the provided list, it's not feasible to calculate an exact solution in this environment. Solving such a problem typically requires advanced algorithms or heuristic methods that are beyond the scope of real-time execution here, especially considering the limitations on computational resources and time.

For practical purposes, specialized software or algorithms designed for intensive computational tasks would be necessary to explore all possible combinations and find an exact match, if one exists. ​


Gemini has a similar behavior: on the small problem, it explains its reasoning and finds the solution. On the larger one, it simply crashes and return the answer to another question !


September 2024 update with o1-preview: still unable to solve the problem, allthough it starts with

Yes, Luke can spend exactly $150,000 on some of these items. This is a classic subset sum problem, where we need to find a combination of item prices that add up to the target sum of $150,000.

It then gives proudly a (false) solution, then finds that the sum adds up ... and concludes that the problem has no solutions !


This CLAIRE code is quite naive but works well on the two inputs :

knap(S4,10000)

eval[2]> list(10000, list(1103, 968, 1207, 999, 2188, 1057, 2478))


knap(S5,150000)

eval[1]>  list(150000, list(4208, 5172, 980, 15098, 8210, 4148, 7750, 10078, 20104, 16130, 12274, 7852, 19146, 4150, 9150, 5550))

it only takes a few seconds for the second example (and 400ms once compiled).

This is a classical dynamic programming approach, where we build iteratively two lists:

Although this code is very simple, it has a few tricks worth mentioning to make reading easier:

This code works well if the unit prices (in l, where m is the max of the values in l) are small, otherwise other approaches (branch and bound) would be better suited.

Performance can be improved (factor of 4) by replacing lists with integer sets (encoding sets of indices <= 60 with integers):

// version 2 with integer sets

[knap2(l:list<integer>,val:integer) : void

 -> let n := length(l), m := max(< @ integer,l), mx := 0, best := 0,

     possible := list{ false | i in (1 .. (n * m))},

     sol := list{ 0 | i in (1 .. (n * m))} in

     (assert(n < 62),         // set to integer encoding constraint

      for i in (1 .. n)

       let x := l[i] in

       (let j := mx in

          (while (j > 0)

            (if possible[j]

                ( possible[j + x] := true,

                  sol[j + x] := sol[j] + ^2(i)),

             j :- 1)),

        possible[x] := true,

        sol[x] := ^2(i),

        mx := (mx + x)),

      for i in (1 .. min(mx,val))

           (if possible[i] best := i),

      list(best,list{l[j] | j in {j in (1 .. n) | sol[best][j]}}))]




December 21st, 2023


Sudoku Problems




A Sudoku problem is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids that compose the grid (also called "boxes," "blocks," or "regions") contain all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which typically has a unique solution.

Here's a breakdown of the main components and rules of Sudoku:

Sudoku became globally popular in the early 21st century and can be found in many newspapers, books, and online platforms. It's praised for its ability to improve logical thinking and is enjoyed by millions of people of all ages around the world.


Here  I have used an "expert  grid" from Sudoku.com :

here is the original 9 x 9 grid, where 0 means that we do not know the figure yet

(0,2,0,0,0,4,0,0,0),

 (8,0,0,0,0,0,0,0,7),

 (0,0,7,0,5,3,0,6,0),

 (0,0,5,4,0,0,0,0,0),

  (0,0,0,8,0,0,0,2,0),

   (9,0,0,0,2,5,3,0,0),

   (0,1,0,0,0,0,9,0,0),

  (0,0,0,2,0,0,0,0,0),

  (0,0,8,0,6,7,0,3,0)



// sudoku example (from CLAIRE documentation)

// shows the use of inference rules -> solves most problems by simple propagation


// data structure

Cell <: object

CellSet <: object


// cell from a 9 x 9 Sudoku grid

Cell[x,y] <: object(x:integer,

                   y:integer,

                   possible:list<boolean>,  // list of possible digits for the cell

                   count:integer = 9,       // number of possible digit

                   digit:integer = 0,       // assigned value to the cell (0 = none)

                   line:CellSet,            // each cell belongs to 3 CellSets: line,

                   column:CellSet,          // its column

                   square:CellSet)          // its 3x3 square


// a set of cells: line, column, square that holds the AllDiff constraint

CellSet[contents] <: object(contents:list<Cell>,          // cells that belong to the set

                            counts:list<integer>)         // a possible digit counter


// two defeasible slots for hypothetical reasoning, but possible uses direct store

store(digit,count)


// creates a cell

makeCell(a:integer,b:integer) : Cell

 -> Cell(x = a, y = b, possible = list<boolean>{true | i in (1 .. 9)}, digit = 0)


// A sudoku grid

Grid <: object(cells:list<Cell>,

              lines:list<CellSet>,

              columns:list<CellSet>,

              squares:list<CellSet>)


// creates a grid

makeGrid() : Grid

 -> let g := Grid() in

       (for i in (1 .. 9)

          for j in (1 .. 9) g.cells :add makeCell(i,j),

        for i in (1 .. 9)

           let li := list<Cell>{c in g.cells | c.x = i},

               cs := CellSet(contents = li, counts = list<integer>{9 | i in (1 .. 9)}) in

              (g.lines :add cs,

               for c in li c.line := cs),

        for j in (1 .. 9)

           let co := list<Cell>{c in g.cells | c.y = j},

               cs := CellSet(contents = co, counts = list<integer>{9 | i in (1 .. 9)}) in

              (g.columns :add cs,

               for c in co c.column := cs),

        for k1 in (1 .. 3)

          for k2 in (1 .. 3)

             let sq := list<Cell>{c in g.cells | abs(3 * k1 - c.x - 1) <= 1 & abs(3 * k2 - c.y - 1) <= 1},

                 cs := CellSet(contents = sq, counts = list<integer>{9 | i in (1 .. 9)}) in

              (g.squares :add cs,

               for c in sq c.square := cs),

        g)


// This progral uses two propagation rules

// the first one propagates a choice by forbiding the digit in the line, column, square

r1() :: rule(

    c.digit := v => (//[1] propagation of ~S <- ~A // c,v,

                     store(c.line.counts,v,0),         // disable counts[v] since v was found !

                     store(c.column.counts,v,0),

                     store(c.square.counts,v,0),

                     for v2 in (1 .. 9)

                       (if (v != v2 & c.possible[v2])

                           (store(c.possible,v2,false),       // avoid double count

                            oneLess(c.line,v2),

                            oneLess(c.column,v2),

                            oneLess(c.square,v2))),

                     for c2 in (c.line.contents but c) forbid(c2,v),

                     for c2 in (c.column.contents but c) forbid(c2,v),

                     for c2 in (c.square.contents but c) forbid(c2,v)))


// forbid a digit

// Attention: if we forbid a digit that is assigned, we must raise a contradiction

forbid(c:Cell,v:(1 .. 9))

 -> (//[3] forbid ~S(~A) -> ~A // c,c.digit,v,

     if (c.x = 5 & c.y = 9) trace(1,">>>> forbid ~S(~A) -> ~A [~A]\n",c,c.digit,v,c.count),

     if (c.digit = v) (//[5] contradiction while propagation //,

                       contradiction!())

     else if (c.digit = 0 & c.possible[v])

        (store(c.possible,v,false),

         c.count :- 1,

         oneLess(c.line,v),

         oneLess(c.column,v),

         oneLess(c.square,v)))


// remove a digit v in a CellSet cs

oneLess(cs:CellSet,v:(1 .. 9)) : void

 -> let cpos := cs.counts[v] in

     (if (cpos > 0)

        (store(cs.counts,v,cpos - 1),

         if (cpos <= 2)

           when c := some(c in cs.contents | c.digit = 0 & c.possible[v]) in

             (//[1] CellSet inference ~S (~A) -> ~S = ~A // cs, list{c.digit | c in cs.contents},c,v,

              c.digit := v)

           else (//[1] contradiction because ~S has no ~A // cs,v,

                 contradiction!())))


// second rule says that once only one digit is possible, we should deduce it !

r2() :: rule(

    c.count := y & y = 1 =>  (trace(1,"--- r2 finds a digit for ~S:~A\n ",c,some(y in (1 .. 9) | c.possible[y])),

                             c.digit := some(y in (1 .. 9) | c.possible[y])))



// create a grid from a problem

[grid(l1:list[list[integer]]) : Grid

  -> let g := makeGrid() in

       (assert(length(l1) = 9),

        for c in g.cells

          let i := c.x, j := c.y, val := l1[i][j] in

            (if (val != 0)  c.digit := val),

         g) ]


// classical heuristic for branching : finds a cell with a min count

[findPivot(g:Grid) : any

 -> let minv := 10, cmin := unknown in

       (for c in g.cells

          (if (c.digit = 0 & c.count < minv)

              (minv := c.count, cmin := c)),

        cmin) ]


NBK:integer :: 0


// solve a sudoku : branch on possible digits

[solve(n:integer,g:Grid) : boolean

 -> when c := findPivot(g) in

       exists(v in (1 .. 9) |

              (if c.possible[v] branch((trace(1,"[~A] create a branch ~S <- ~A\n",n,c,v),

                                        c.digit := v,

                                        let b := solve(n + 1, g) in

                                          (if not(b) trace(1,"[~A] ~S := ~A failed\n",n,c,v),

                                           if not(b) NBK :+ 1,

                                           b)))

               else false))

    else true]


// show the solution

[see(g:Grid)

 -> printf("\n\t------------------\n"),

    for i in (1 .. 9) printf("\t~I\n",(for j in (1 .. 9) printf("~A ",g[i,j].digit))) ]


// create a grid

S1 :: grid(list(list(0,2,0,0,0,4,0,0,1),

                     list(8,0,0,0,0,0,0,0,7),

                     list(0,0,7,0,5,3,0,6,0),

                     list(0,0,5,4,0,0,0,0,0),

                     list(0,0,0,8,0,0,0,2,0),

                     list(9,0,0,0,2,5,3,0,0),

                     list(0,1,0,0,0,0,9,0,0),

                     list(0,0,0,2,0,0,0,0,0),

                     list(0,0,8,0,6,7,0,3,0)))



Sudoku is a classical and enormously popular problem. Chat GPT does a good job with it.

Although it does not  say much and it takes a while  (more than twenty seconds), it returns with a cheerful message and the  proper solution:

The Sudoku puzzle has been successfully solved. Here is the completed grid:


5 2 6 | 7 8 4 | 1 9 3

8 3 9 | 6 1 2 | 4 5 7

1 4 7 | 9 5 3 | 8 6 2

------+-------+------

2 8 5 | 4 3 6 | 7 1 9

3 6 1 | 8 7 9 | 5 2 4

9 7 4 | 1 2 5 | 3 8 6

------+-------+------

6 1 2 | 3 4 8 | 9 7 5

7 5 3 | 2 9 1 | 6 4 8

4 9 8 | 5 6 7 | 2 3 1

Each row, column, and 3x3 subgrid contains all numbers from 1 to 9 without any repetition. ​

Note that, contrary to previous examples, ChatGPT does not explain its reasoning ... it simply sub contracts the set of "all different" constraints to a solver, which does the job.

The CLAIRE code solves this problem and a set of others gathered on Sudoku web sites quasi instantly (8 ms with interpreted code). If you switch the tracing on, it actually prints all the reasoning steps (deduction) that it made. 

The same prompt was spent to Bard AI with the following answer:


I'm unable to find a solution to the Sudoku puzzle you provided. I employed a backtracking algorithm to explore possible number placements while adhering to Sudoku's rules, but it didn't yield a complete solution.

Here are some potential reasons why a solution might not be found:

If you're confident that the starting grid is accurate, you could try:




This CLAIRE code works well in terms of performance and is able to solve most problems with pure deduction, without any "backtracks" (that is making an hypothesis and returning to a previous choice point if that hypothesis fails).

The code, taken from the CLAIRE Reference Manual, shows different features of the language:


December 3rd, 2023


Who Owns the Zebra ?



The puzzle states that we have 5 houses along a street with doors of different colors.
They are inhabited by five people, usually designated by their nationality, with a different job, they own a different pet animal and drink a different beverage. You will find the original definition here or in the CLAIRE code below, here is a modified version to see how ChatGPT fares :

There are five houses in a row in this little street. Each one of the houses has a different door color and behind each of these doors lives Peter, Paul, Mary, Sophie and John. Every one of these people has a different car brand, enjoys a different wine and works in a different software profession.

1. Peter lives in the red house.

2. Paul owns a Ferrari.

3. Pinot wine is drunk in the green house

4. Mary drinks Cabernet.

5. The green house is immediately to the right of the Ivory house.

6. The developer owns the Toyota.

7. The tester lives in the yellow house.

8. Merlot wine is drunk in the middle house.

9. Sophie lives in the first house on the left.

10. The UX designer lives next to the owner of the Maserati.

11. The tester lives next to the owner of the Ford.

12. The scrum master drinks Zinfandel.

13. John is the SRE.

14. Sophie lives next to the blue house.

Question: Who owns the Tesla? And Who drinks the Sauvignon ?


// code from the GitHub repository (tests/rules)

House :: (1 .. 5)

Problem <: thing(house:integer = 0)


// use naive backtracking to solve a problem

store(house)


// Data for the problem

Color <: Problem()

  red :: Color() 

  green :: Color() 

  ivory :: Color()

  yellow :: Color()

  blue :: Color()


Person <: Problem()

  englishman :: Person()

  spaniard :: Person()

  ukrainian :: Person() 

  norwegian :: Person()

  japanese :: Person()


Pet <: Problem()

  dog :: Pet()

  snails :: Pet()

  fox :: Pet()

  horse :: Pet()

  zebra :: Pet()


Drink <: Problem()

  water :: Drink()

  coffee :: Drink()

  milk :: Drink()

  orange-juice :: Drink()

  tea :: Drink()


Smoke <: Problem()

  old-golds :: Smoke()

  kools :: Smoke()

  chesterfields :: Smoke()

  lucky-strikes :: Smoke()

  parliaments :: Smoke()


final(Color)

final(Person)

final(Pet)

final(Drink)

final(Smoke)


// check in CLAIRE : these are the assertions produced by the rules that may cause
// a contradiction if the new assertion is not consistent with what we already know

check(p:property,x:any,y:any) : void

 => (if (get(p,x) = 0) write(p,x,y)

     else if (get(p,x) != y) contradiction!())


checknot(p:property,x:any,y:any) : void

 => (if (get(p,x) = y) contradiction!())



// The Englishman lives in the red house.

rule1() :: rule(p.house := h & p = englishman => check(house,red,h))


// notice that the Alldifferent constraint is spelled in many rules in the original code

allDifferent() :: rule(p.house := h => use-house(p,h))


use-house(p:Problem,h:House)

   -> (case p (Person for p2 in (Person but p) checknot(house,p2,h),

               Color  for p2 in (Color but p) checknot(house,p2,h),

               Pet    for p2 in (Pet but p) checknot(house,p2,h),

               Drink  for p2 in (Drink but p) checknot(house,p2,h),

               Smoke  for p2 in (Smoke but p) checknot(house,p2,h)))


// The Spaniard owns the dog.

rule2() :: rule(p.house := h & p = spaniard  => check(house,dog,h)) 



// The ivory house is immediately to the left of the green house, where the coffee drinker lives.

rule3() :: rule(p.house := h1 & p = ivory => 

                (if (h1 <= 4) check(house,green,h1 + 1) else contradiction!()))

rule4() :: rule(p.house := h & p = coffee => check(house,green,h))


// The milk drinker lives in the middle house.

(milk.house := 3)


// The man who smokes Old Golds also keeps snails.

rule5() :: rule(p.house := h & p = old-golds => check(house,snails,h)) 


// The Ukrainian drinks tea.

rule6() :: rule(p.house := h & p = ukrainian  => check(house,tea,h))  


// The Norwegian resides in the first house on the left.

(norwegian.house := 1)


// Chesterfields smoker lives next door to the fox owner.

rule7() :: rule(p.house := h & p = chesterfields  => next-to(fox,h))

rule7bis() :: rule(p.house := h & p = fox => next-to(chesterfields,h))


next-to(p:Problem,h:House) : void

  => (if (p.house > 0 & p.house != (h - 1)) check(house,p,h + 1))


// The Lucky Strike smoker drinks orange juice.

rule8() :: rule(p.house := h & p = lucky-strikes  => check(house,orange-juice,h))


// The Japanese smokes Parliaments

rule9() :: rule(p.house := h & p = japanese  => check(house,parliaments,h))


// The horse owner lives next to the Kools smoker, whose house is yellow.

rule10() :: rule(p.house := h & p = horse => next-to(kools,h)) 

rule10bis() :: rule(p.house := h & p = kools  => next-to(horse,h))


rule11() :: rule( p.house := h & p = kools  => check(house,yellow,h))


// The Norwegian lives next to the blue house.

rule12() :: rule(p.house := h & p = norwegian  => next-to(blue,h))

rule12bis() :: rule(p.house := h & p = blue  => next-to(norwegian,h))


// to solve we use the same instantiation order as the original CLIPS example

find-solution()

 -> solve(list<Problem>(

      englishman,

      red,

      spaniard,

      dog,

      ivory,

      green,

      coffee,

      milk,

      old-golds,

      snails,

      ukrainian,

      tea,

      norwegian,

      chesterfields,

      fox,

      lucky-strikes,

      orange-juice,

      japanese,

      parliaments,

      horse,

      kools,

      yellow,

      blue,

      water,

      zebra))


// generate and test

solve(l:list[Problem]) : boolean -> solve(l,1)

solve(l:list[Problem],n:integer)  : boolean

  -> (if (n > length(l))

         (if (verbose() >= 1) print-solution(),false) // no more problems

      else let p := l[n] in              

         (if (p.house = 0)                                      // hou
se = 0 means unknown yet

             exists(h in (1 .. 5) |

                    branch( (p.house := h,

                             solve(l, n + 1))))

          else solve(l, n + 1)))        // move to next


// prints the solution

print-solution()

 -> (for h in House

       printf("~A:~S ~S ~S ~S ~S\n",h,

               some(x in Color | x.house = h),

               some(x in Person | x.house = h),

               some(x in Pet | x.house = h),

               some(x in Smoke | x.house = h),

               some(x in Drink | x.house = h)))





This is a very famous puzzle. Chat GPT does a great job with it !


To solve this logic puzzle, we can use a process of elimination and deduction. The puzzle involves five houses, each with a unique color, nationality of the resident, pet, drink, and profession. We need to determine who owns the zebra and who drinks water. Let's start by laying out what we know:

It then applies the "clues", the statements, to produce logical deductions and find the solution after a page of deductions :

With this information, we can start filling in the gaps:

Now, to answer the questions:

This is a classic example of the kind of puzzle known as a "logic grid" puzzle, where the solution is found by a process of elimination and logical deduction.


this time, ChatGPT is not puzzled (pun intented) with the variable substitution presented in the introduction and does an equally great job at solving "Who owns the Tesla ?"


This CLAIRE code works well in terms of performance and number of rules fired per seconds. This is why it was designed in the first place ... not necessarily the best way to code this specific problem "who owns the zebra ?".

However, this fragment is an opportunity to introduce two key features of CLAIRE:

This code also exhibits the "set programming style" in CLAIRE (à la SETL) with the various expressions such as :

"some(x in S | P(x))"  or  "exists(s in S |  P(x))

November 18th, 2023


SEND + MORE = MONEY



Here is the statement :


find different digits for the letters S, E, N ,D, M, O, R, Y such that the 

following addition stands : 

    S E N D 

+   M O R E

-----------

= M O N E Y 



// SEND+MORE = MONEY in a naive manner, without constraint propagation

// S and M are the first digits, they cannot be zero.

[Bucket <: thing(value:integer = -1, minValue:integer = 0)]

S :: Bucket(minValue = 1)

E :: Bucket()

N :: Bucket()

D :: Bucket()

M :: Bucket(minValue = 1)

O :: Bucket()

R :: Bucket()

Y :: Bucket()


LB :: list<Bucket>(S,E,N,D,M,O,R,Y)

lused :: list<boolean>{false | i in (0 .. 9)}

CInt <: thing(value:integer = 0)


nbk :: CInt()


// tells if the solution is OK

[solOK() : boolean

 -> (S.value * 1000 + E.value * 100 + N.value * 10 + D.value) +

    (M.value * 1000 + O.value * 100 + R.value * 10 + E.value) =

    (M.value * 10000 + O.value * 1000 + N.value * 100 + E.value * 10 + Y.value) ]


[solve() : boolean

  -> solve(LB, 8) ]


// naive exploration of the search space, using lused to record the digits that have been used already

[solve(l:list<Bucket>,i:integer) : boolean

 -> if (i = 0)

       (if solOK() true 

        else (nbk.value :+ 1, contradiction!(), false))

     else let b := l[i], found := false in

         (for j in (b.minValue .. 9)

            (if not(lused[j + 1])

                try (b.value := j,

                     lused[j + 1] := true,

                     if solve(l, i - 1)

                        (found := true, break())

                     else lused[j + 1] := false)

                catch contradiction lused[j + 1] := false),

         found) ]


If you run this code under the CLAIRE4 interpreter, you will get the unique solution in 0.6s and 420 000 attempts (the global counter nbk registers how many attempts failed - backtracks - before finding the solution). 


This is a very famous puzzle. ChatGPT (GPT4) is happy to solve it for you ... it starts its answer, like the previous example, with a cheerful introduction:

Yes, I can help solve that puzzle. It's a classic example of a cryptarithmetic puzzle, where each letter represents a unique digit. Given the equation SEND + MORE = MONEY, we must find the value of each letter.

It starts it resolution with a few deductions :

Here's one way to approach solving the puzzle:

Then shows a picture with a reference to Mathematica ... and keeps going.

After three long pages of deductions, and further (implicit) references to Mathematica, it ends up with the right solution : 9567 + 1085 = 10652

At this point we are suitably impressed ! but then we ask almost the same question : 

can you solve the puzzle ABCD + EFGB = EFCBH, where each letter A, B to G is assigned a unique digit ?

ChatGPT starts with the same cheerful restatement : 


Yes, this is a cryptarithmetic puzzle where each letter represents a unique digit. To solve it, we must find the digits that satisfy the equation

ABCD+EFGB=EFCBH

Then it starts making a few deductions, ... and gets nowhere.

After two pages, it gives up with the following statement :

For more precision, we would indeed need to rely on further deductions that could get complex and exhaustive since the permutation and combination sets are vast. The correct method to solve this is by writing a program to iterate over the possible combinations or by methodically applying the constraints one by one and using logical deductions to narrow down the possibilities manually. This can be a laborious process and would typically be beyond a straightforward text response, considering the limitations of the medium to perform such an iterative solution.

This is an interesting example since it shows that the combination of LLMs trained on corpus that includes this famous puzzle and a little bit of "Chain of Thoughts" prompting that involves Mathematica, GPT4 does a good job, but it does not actually solve the problem but rather assembles fragments of proofs. The letter substitution that would have zero effect of a theorem prover (using logic) or a problem solver (using exploration like the CLAIRE simple program or a combination of logic and enumeration).


This is a very naive version of an exploration algorithm, but neither the simplest nor the most efficient. It uses a "try/catch" pattern because it can be easily extended to add "constraint propagation", that are heuristics that can generate "cuts" through contradiction.

This program is actually extracted from the test library that checks the efficiency of exception handling. The same program has been implmented in many other languages (see the table in the "why" page).




November 5th, 2023


Mr Sum and Mr Product


This is an old problem, a favorite of my father, the late Paul CASEAU, who gave it to me when  I was 13.

Here is the statement :


Mr S and Mr P are two persons.

Mr S nows the sum of two numbers A + B, Mr P known the product A x B, A & B are integers greater that 1.

When they meet they have the following dialog:

 (1) Mr S says "the sum is less than 100"

 (2) Mr P says "I cannot conclude"

 (3) Mr S says "I knew you could not conclude"

 (4) Mr P says "then I known (A and B)"

 (5) Mr S says "then I know them two"

what are the possible values for A and B so that the previous dialog stands ?



// sets of A (A < B) from S (sum)

[AfromS(S:integer)  -> (2 .. (S / 2))]


// sets of A (A < B) from P (product)

[AfromP(S:integer) 

-> {i in (2 .. integer!(sqrt(float!(S)))) | S mod i = 0}]


// first statement of Mr S

[statement1(S:integer) : boolean  -> S <= 100]


// second statement of Mr P

[statement2(P:integer) : boolean

-> size({A in AfromP(P) | statement1(A + (P / A)) > 1 ]


// third statement of Mr S : all decomposition of S satisfy statement2

[statement3(S:integer) : boolean

-> forall(A in AfromS(S) | statement2(A * (S - A))) ]


// fourth statement of Mr P : only one decomposition of P satisfy statement3

[statement4(P:integer) : boolean

-> size({A in AfromP(P) | statement1(A + P / A) & statement3(A + P / A)}) = 1]


// fifth statement of Mr S : only one decomposition of S satisfy statement4

[statement5(S:integer) : boolean

-> size({A in AfromS(S) | statement3(S) & statement4(A * (S - A))}) = 1]


// solve the puzzle and show there is only one solution

[solve() : void

-> for A in (2 .. 99)

for B in (A .. (100 - A)) // iterate so that A < B

let S := A + B, P := A * B in

(if (statement2(P) & statement3(S) & statement4(P) & statement5(S))

printf("found a solution : ~S and ~S\n", A, B))]


If you run this code under the CLAIRE4 interpreter, you will get the unique solution (4 and 13).

I will let the reader decide if this code is elegant or not, but we can agree that it is compact (compared to the attempts of resolution proposed by GPT) and fairly readable. You can look at the implementation notes below (Section 4).


ChatGPT is quite puzzled ... it starts with a cheerful introduction:

This puzzle is an example of a common type of logical deduction problem that involves reasoning about knowledge. Let's follow the conversation step by step, applying logical deductions to find the two numbers.

It then restates the problem, quite accurately ...

Then it begins  a set of possible deductions, and gets nowhere .. to  conclude that this puzzle is more complex than it looks:

This puzzle is, therefore, less straightforward than ones that rely purely on logical deduction and may require some computational methods to systematically address unless more contextual hints are provided within the question to limit the scope of trial and error. If the specific range of numbers to consider was narrower, we could provide a more direct solution. However, with the current information, one would ideally use a program to iterate over the possibilities and apply the conditions iteratively to deduce the exact numbers.

Which is by the way a very nice conclusion, and one that is a good way to start a column about cool programming fragments.

September 2024 update with o1-preview:  Chat GPT finds the solution (4,13) with a beautiful explanation (I encourage the reader to try):

However, when given a variant such as:

Let us try a new version. Mr S and Mr P are two persons. Mr S nows the sum of two numbers A + B, Mr P known the product A x B, A & B are integers greater that 1. 

 When they meet they have the following dialog: 

 (1) Mr S says "the sum is less than 100" 

 (2) Mr P says "I cannot conclude" 

 (3) Mr S says "I knew you could not conclude" 

 (4) Mr P says "I still do not know A and B" 

(5) Mr S says "then I have found A and B" 

what are the possible values for A and B so that the previous dialog stands ?

ChatGPT is not able to find the solution and returns a wrong pair. When looking at the explanation, one sees that the last part of the dialog is not properly understood and implemented, the explanations are similar to the previous version ... and the same 4,13 solution is returned !



The code fragment should be easy to read, but here are some notes to facilitate your understanding:


Stay tuned.