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

• N-Queens

• Knapsack

• Sudoku

• Who Owns the Zebra ?

• SEND+MORE=MONEY

• Mr Sum and Mr Product

March 17th, 2024

N-Queens Problems

1. Problem Statement
   
   
   The N-Queens problem is the generalization to a NxN board of one of the oldest and most famous chess puzzle : how to place 8 queens on a chess board so that no queen attack another, that is, they are all on different rows, columns and diagonals. For 8 queens, there are 92 solutions, the problem was generalized to N queens by Franz Nauck, who proposed the first solution in 1850.
   
   

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 ?

2. Claire Code

// 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)}

3. ChatGPT  results

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):

• Place a queen on the first square (top left corner - row 1, column 1).

• Since queens can't attack each other horizontally or vertically, place the next queen on any square in row 4 (avoiding the first column). Let's place it on column 3 (row 4, column 3).

• Now, consider diagonals. No queen can be placed on diagonals where the queens already are. Looking at the first queen, diagonals going down and to the right are occupied for 3 squares (including the queen's position). Similarly, diagonals going down and to the left are occupied for 2 squares. So, we need to place the next queen in a row that avoids these occupied diagonals. Row 7 is a safe choice (avoiding column 1 and 3). Let's place it on column 6 (row 7, column 6).

• Continue using the same logic to place the remaining queens. One approach is to focus on avoiding diagonals occupied by existing queens. Here's a possible placement for the remaining queens:

  • Queen 4: Row 2, Column 8

  • Queen 5: Row 5, Column 2

  • Queen 6: Row 8, Column 4

  • Queen 7: Row 3, Column 5

  • Queen 8: Row 6, Column 7

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:

• Queens can move horizontally, vertically, and diagonally. This means any queen on the board creates a zone of attack that covers all squares along those lines (rows, columns, and diagonals) for an infinite distance.

• On a standard 8x8 chessboard, queens can avoid attacking each other by strategically placing them on squares that don't share rows, columns, or diagonals. However, on a larger board like 64x64, this strategy becomes impossible.

• No matter where you place a queen, it will always attack squares along its rows, columns, and diagonals, inevitably creating overlaps with other queens' zones of attack.

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 !

4. Implementation notes

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:

• The code is based on expanding the three "AllDifferent" constraints into 3 propagation rules. Note that a constraint programming language would be much more concise here, since you would simply need to express the three constraints : AllDifferent(columns), AllDifferent(Diagonal 1 = line+column), AllDifferent(Diagonal 2 = line-column)

• What makes CLAIRE a good programming language for puzzles is the built-in support for exploring search trees (backtracking). Defeasible knowledge structures (object, arrays) are defined with store(...), so that in this example the values of column, possible and countPos are reset automatically when there is a backtrack.

• The core feature here is branch(X) which creates a backtrack point, executes X and returns true, unless a contradiction exception is triggered, then branch backtracks and returns false.

• We triger a contradiction when we have removed all possible positions for a queen that has not been placed on the chessboard

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

1. Problem Statement
   
   
   Knapsack problems are amongst the oldest and better-known combinatorial problems. You are given a total amount (size or money) and a list of objects (defined by their size, weight or cost) and your goal is to put as many in your knapsack while respecting the total constraint.  Here are two examples that we will use today.

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 ?

2. Claire Code

// 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)

3. ChatGPT  results

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 !

4. Implementation notes

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:

• possible : integers that can be obtained from the subset that that is considered (which we grow by adding each integer x from the list l)

• sol: list of components that are used to reach i.

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

• Each iteration expands the possible and sol lists by adding the possible choice of x

• we iterate on all previous combinations backwards (i = mx down to 1) so that we can directly add a new combination without damaging the iteration process.

• mx is the maximal combination (sum) found so far, that is computed dynamically during the iterations

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

1. Problem Statement
   
   
   Sudoku  is a  very  well-known problem where the player is given a grid  that needs to be completed with digits.
   Here is how ChatGPT describes the problem :

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:

• Grid Structure: The Sudoku grid is 9x9, made up of 3x3 subgrids.

• Given Numbers: Some of the cells are already filled with numbers. These are the 'givens' or 'clues.' The difficulty of the puzzle depends on which numbers are given and their distribution across the grid.

• Objective: The player must fill in the empty cells with digits from 1 to 9. Each number must appear exactly once in each row, each column, and each 3x3 subgrid.

• Logical Deduction: Players use logical reasoning and deduction to determine which numbers belong in which cells. Guessing is not required to complete a Sudoku puzzle, as they are designed to be solved purely through logic.

• Difficulty Levels: Sudoku puzzles vary in difficulty. Simple puzzles usually provide more numbers and place them in positions that make the puzzle easier to solve. Harder puzzles provide fewer initial numbers and may require more complex logical strategies to solve.

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)

2. Claire Code

// 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)))

3. ChatGPT  results

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:

• Incorrect or incomplete starting grid: Double-check the provided grid for any errors or missing numbers. Even a single misplaced digit can render a Sudoku puzzle unsolvable.

• Multiple solutions: In rare cases, a Sudoku puzzle might have multiple valid solutions. The backtracking algorithm might have found one solution, but it might not be the one you expected.

• Algorithm limitations: While backtracking is a common Sudoku-solving technique, it's not foolproof. There might be more advanced algorithms or techniques that could find a solution where backtracking fails.

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

• Using a different Sudoku solver: There are many Sudoku solvers available online or as mobile apps. These solvers might use different algorithms or approaches that could find a solution.

• Seeking help from a human expert: Experienced Sudoku players often have strategies and techniques that go beyond algorithmic approaches. They might be able to spot patterns or clues that a computer solver might miss.

4. Implementation notes

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:

• The core of the program is the Grid structure, that is a set of cells organized into lines, columns and subsquare.
  It is not the most concise way to solve the problem, but it is very powerful and could be extended in many ways, or translated to other board games. This is why this program is selected as part of the documentation.

  • The creation of the lines and the columns in "makeGrid()" is straightforward, but there is a small arithmetic trick to defined the 9 sub-squares

• CLAIRE implements simple "forward" rules of the kind:

  • <rule name > () :: rule( <condition> => <action>)

  • for readers familiar with constraint propagation tools, the first use here is the implementation of the "All digits in a line, column or sub-square) must be different.

• CLAIRE has native support for banch&bound algorithms : Not really useful here, but it will come handy in the future examples to come

  • this is why you see the store(digit, count) declarations at the beginning of the program : changes related to these "slots" are defeasible = wi

December 3rd, 2023

Who Owns the Zebra ?

1. Problem Statement
   
   
   This is a very famous logical puzzle that used to be a classical benchmark for rule-based systems in the 80s. The CLAIRE code was produced by reproducing a benchmark file from the CLIPS (version 6.0) rule system.

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 ?

2. Claire Code

// 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)))

3. ChatGPT  results

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:

• House Order: Norwegian (1st) → Blue (2nd) → Middle (Milk, 3rd) → Green (4th) → Red (5th)

• House Colors: Red, Green, Ivory, Yellow, Blue

• Nationalities: English, Spanish, Ukrainian, Norwegian, Japanese

• Pets: Dog, Snail, Fox, Horse, Zebra (unknown)

• Drinks: Coffee, Tea, Milk, Orange Juice, Water (unknown)

• Professions: Engineer, Diplomat, Doctor, Teacher, Carpenter

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:

• 1st House: Norwegian, Yellow (Diplomat), Water, Fox, Doctor

• 2nd House: Blue, Ukrainian (Tea), Horse, Carpenter

• 3rd House: Ivory, Milk, Snail, Engineer

• 4th House: Green, Coffee, Dog, Spanish

• 5th House: Red, English, Orange Juice, Teacher

Now, to answer the questions:

• Who owns the zebra?

  • The Norwegian in the first house (the only pet left).

• Who drinks the water?

  • The Diplomat in the yellow house (the only drink left).

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 ?"

4. Implementation notes

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:

• CLAIRE implements simple "forward" rules of the kind:

  • <rule name > () :: rule( <condition> => <action>)

• CLAIRE has native support for banch&bound algorithms (exploring a search tree)

  • "Defeasible" data stuctures on which hypothesis can be made  that are later backtracked

  • A tree exploration construct called "branch" (see the solve method)

    • branch( <stratement>) creates a "world" (that is a backtrack point), executes <statement> and returns to the orginal state if a contradiction exception has been raised.

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

1. Problem Statement
   
   This is a very classical puzzle, used to  illustrate naive exploration, because the search space is small.

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 

2. Claire Code

// 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). 

3. ChatGPT  results

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:

• M must be 1 because when you add two numbers together, the sum cannot have more digits than the numbers added unless there's a carry from the last addition. Since MONEY has one more digit than SEND or MORE, the only digit that can be carried over is 1 (to make the sum a five-digit number).

• O cannot be 0 or 1. It cannot be 0 because then both MORE and MONEY would start with 0, which is not usual for numbers, and it cannot be 1 because M is 1. Moreover, the carryover from adding N+R or N+R+1 (if there's a carry from the addition of E+O in the previous place) would make O + 1 equal to the first digit of a sum in the thousands, which is again M or 1. This implies O is contributed to by a carry from the hundreds place, making O equal to 0 + carry(1), which is not possible as M already has the value of 1, so the carryover into the thousands place must be from O + something = 1 + something.

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).

4. Implementation notes

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.

• contradiction!() raises an exception

• try ... catch <exception handler>  is the usual construct to catch a contriction exception if one is raised.

• we use a "Bucket "object (where we can add additional inferences about each letter) because this is the simpler version of an extensible code.

• If you compile the CLAIRE program, the solution is found in 20ms.

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

1. Problem Statement
   
   
   

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 ?

2. Claire Code

// 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).

3. ChatGPT  results

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):

• explores the possible values of S

• for eah S looks at the possible P

• express the viewpoints of Mr and Mr P as mathematical conditions about S and P ...

• checks all values that satisfy all conditions (what we do with the CLAIRE code).

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 !

4. Implementation notes

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

• (x .. y) is the "integer interval", the set of integers between x and y

• (x mod y) is "x modulo y" (x % y in C)

• In CLARE, assignment is :=, equality is =, and logical and is &.

• Set expressions, such as {x in S | P(x)} which is the subset of x in a set S that satisfy a predicate P(x), are first-class citizens of the CLAIRE language, a nice feature for this example.

Stay tuned.