CODEWITHSUNDEEP
clips
Aleksander
Aleksander

Reputation: 13

Looping defrule in CLIPS

I am trying to solve a problem, where I have to fill a 5x5 matrix with letters A, B, C, D, and E. Each letter cannot occur more than once in each row and in each column. With some initial letter positions given. I created every position as separate facts eg. "M 1 1 X". I am struggling how to loop a defrule in way to assert a fact with correct letter and check the conditions again.

(defrule solveA5
?a <-(M 5 ?c X)
(not (M ?x ?c A))
=>
(retract ?a)
(assert (M 5 ?c A))
)

Code above for example is only to check presence of A in every position of 5th row, but the problem is that conditions are checked at the beginning only and instead of asserting correct fact and checking again it asserts A in every position.

I've tried using deffunction to loop defrule.

(deffunction solve (?letter)
(loop-for-count (?x 1 5) do
    (loop-for-count (?y 1 5) do
        (build (str-cat"defrule costam
            ?a <-(M ?x ?y X)
            (not (and(M ?x ?a ?letter) (M ?b ?y ?letter))
            =>
            (retract ?a)
            (assert (M ?x ?y ?letter))")
        )
    )
)
)

Unfortunately running

(solve A)

returns "FALSE" and doesn't modify any facts.

Upvotes: 1

Views: 2994

Answers (1)

Gary Riley
Gary Riley

Reputation: 10757

To handle iteration within rules, you must assert the iteration information as facts to allow the rules to match and modify this information. In the placement, it's not essential to do this in any particular order, so you can just assert information containing the rows, columns, and letters to place and allow the rules fire arbitrarily:

CLIPS> 
(deftemplate element
   (slot row)
   (slot column)
   (slot value))
CLIPS>    
(deftemplate print
   (slot row)
   (slot column)
   (slot end-of-row))
CLIPS>    
(deffacts initial
   (rows 1 2 3 4 5)
   (columns 1 2 3 4 5)
   (letters A B C D E))
CLIPS>    
(defrule place
   (rows $? ?r1 $?)
   (columns $? ?c1 $?)
   (letters $? ?l $?)
   (not (element (row ?r1) (column ?c1)))
   (not (and (element (row ?r2)
                      (column ?c2)
                      (value ?l))
             (test (or (= ?r1 ?r2) (= ?c1 ?c2)))))
   =>
   (assert (element (row ?r1) (column ?c1) (value ?l))))
CLIPS>          
(defrule print-start
   (declare (salience -10))
   (rows ?r $?)
   (columns ?c $?rest)
   =>
   (assert (print (row ?r) 
                  (column ?c)
                  (end-of-row (= (length$ ?rest) 0)))))
CLIPS>    
(defrule print-next-column
   (declare (salience -10))
   ?f <- (print (column ?c))
   (columns $? ?c ?nc $?rest)
   =>
   (modify ?f (column ?nc)
              (end-of-row (= (length$ ?rest) 0))))
CLIPS> 
(defrule print-next-row
   (declare (salience -10))
   ?f <- (print (column ?c) (row ?r))
   (columns $?first ?c)
   (rows $? ?r ?nr $?)
   =>
   (if (= (length$ ?first) 0)
      then
      (bind ?eor TRUE)
      (bind ?nc ?c)
      else
      (bind ?eor FALSE)
      (bind ?nc (nth$ 1 ?first)))
   (modify ?f (row ?nr)
              (column ?nc)
              (end-of-row ?eor)))
CLIPS>    
(defrule print-placed
   (print (row ?r) (column ?c) (end-of-row ?eor))
   (element (row ?r) (column ?c) (value ?l))
   =>
   (if ?eor
      then
      (printout t ?l crlf)
      else
      (printout t ?l " ")))
CLIPS> 
(defrule print-unplaced
   (print (row ?r) (column ?c) (end-of-row ?eor))
   (not (element (row ?r) (column ?c)))
   =>
   (if ?eor
      then
      (printout t "?" crlf)
      else
      (printout t "? ")))
CLIPS> (reset)
CLIPS> (run)
E D C B A
? C D A B
? B A D C
? A B C D
A ? ? ? E
CLIPS>

In this example, the print rules iterate over the rows and columns by storing the iteration information in facts. You can see how much more complicated this is than the place rule which assigns the elements in an arbitrary manner.

Whether you assign the values arbitrarily or in a specific order, it's possible to assign values that prevent a solution, so you must implement backtracking in order to guarantee finding the solution if one exists. In this example, the facts store information about the order of the value placements and the values that have been tried:

CLIPS> (clear)
CLIPS> 
(deftemplate element
   (slot row)
   (slot column)
   (slot value (default unset))
   (multislot values)
   (slot placement))
CLIPS>       
(deffacts initial
   (placement 0)
   (rows 1 2 3 4 5)
   (columns 1 2 3 4 5)
   (letters A B C D E))
CLIPS>    
(defrule prime
   (placement ?p)
   (rows $? ?r $?)
   (columns $? ?c $?)
   (letters $?l)
   (not (element (placement ?p)))
   (not (element (row ?r) (column ?c)))
   =>
   (assert (element (placement ?p) (values ?l) (row ?r) (column ?c))))
CLIPS>    
(defrule place-good
   ?f1 <- (placement ?p)
   ?f2 <- (element (placement ?p)
                   (value unset)
                   (row ?r1)
                   (column ?c1)
                   (values ?v $?rest))
   (not (and (element (row ?r2)
                      (column ?c2)
                      (value ?v))
             (test (or (= ?r1 ?r2) (= ?c1 ?c2)))))
   =>
   (retract ?f1)
   (assert (placement (+ ?p 1)))
   (modify ?f2 (value ?v) (values ?rest)))
CLIPS>    
(defrule place-bad
   (placement ?p)
   ?f2 <- (element (placement ?p)
                   (value unset)
                   (row ?r1)
                   (column ?c1)
                   (values ?v $?rest))
   (element (row ?r2)
            (column ?c2)
            (value ?v))
   (test (or (= ?r1 ?r2) (= ?c1 ?c2)))
   =>
   (modify ?f2 (values ?rest)))
CLIPS>    
(defrule backtrack
   ?f1 <- (placement ?p)
   ?f2 <- (element (placement ?p)
                   (value unset)
                   (values))
   ?f3 <- (element (placement =(- ?p 1))
                   (value ~unset))
   =>
   (retract ?f1)
   (assert (placement (- ?p 1)))
   (retract ?f2)
   (modify ?f3 (value unset)))
CLIPS>       
(defrule print
   (declare (salience -10))
   (rows $?rows)
   (columns $?columns)
   =>
   (progn$ (?r ?rows)
      (progn$ (?c ?columns)
         (if (not (do-for-fact ((?f element)) 
                               (and (= ?r ?f:row) (= ?c ?f:column))
                     (printout t ?f:value " ")))
            then
            (printout t "? ")))
      (printout t crlf)))
CLIPS> (reset)
CLIPS> (run)
B C D E A 
A B C D E 
C A E B D 
D E A C B 
E D B A C 
CLIPS>

The print rules have been simplified into a single rule that iterates over the row and columns in the actions of the rule and uses the fact query functions to retrieve values that have been assigned.

The program also works if you preassign some of the values:

CLIPS> (reset)
CLIPS> (assert (element (row 1) (column 1) (value A)))
<Fact-5>
CLIPS> (assert (element (row 3) (column 3) (value C)))
<Fact-6>
CLIPS> (assert (element (row 5) (column 4) (value E)))
<Fact-7>
CLIPS> (run)
A C E D B 
B A D C E 
D E C B A 
E D B A C 
C B A E D 
CLIPS>

Upvotes: 1

Related Questions