Search code examples
prologclpfd

What does it mean by express this puzzle as a CSP

What is meant by the below for the attached image. 

By labelling each cell with a variable, express the puzzle as a CSP. Hint:
recall that a CSP is composed of three parts.

I initially thought just add variables to each cell like A, B, C etc to each cell and then constrain those cells, but I do not believe that is correct. I do not want the answer just an explanation of what is required. in terms of CSP.

enter image description here

Solution

  • In my opinion, a CSP is best divided into two parts:

    1. State the constraints. This is called the modeling part or model.
    2. Search for solutions using enumeration predicates like labeling/2.

    These parts are best kept separate by using a predicate which we call core relation and which has the following properties:

    • It posts the constraints, i.e., it expresses part (1) above.
    • Its last argument is the list of variables that still need to be labeled.
    • By convention, its name ends with an underscore _.

    Having this distinction in place allows you to:

    • try different search strategies without the need to recompile your code
    • reason about termination properties of the core relation in isolation of any concrete (and often very costly) search.

    I can see how some instructors may decompose part (1) into:

    1a. stating the domains of the variables, using for example in/2 constraints
    1b. stating the other constraints that hold among the variables.

    In my view, this distinction is artificial, because in/2 constraints are constraints like all other constraints in the modeling part, but some instructors may teach this separately also for historical reasons, dating back to the time when CSP systems were not as dynamic as they are now.

    Nowadays, you can typically post additional domain restrictions any time you like and freely mix in/2 constraints with other constraints in any order.

    So, the parts that are expected from you are likely: (a) state in/2 constraints, (b) state further constraints and (c) use enumeration predicates to search for concrete solutions. It also appears that you already have the right idea about how to solve this concrete CSP with this method.