CLIPS 8 皇后 defrule

Question

我正在尝试使用 CLIPS 解决 8 皇后问题。我的代码解决了其中的一部分。只有水平和垂直检查，所以你可以说它解决了 8 车问题。我无法得到的是如何进行对角线检查。 CLIPS 不允许对事实进行任何检查，例如 (not (queen ?i-1 ?j-1)), (not (queen ?i-2 ?j-2)) 等等...

(assert (cur 1 1))
(assert (placed 0))

(defrule placer "Placer"
?a <- (cur ?i ?j)
?b <- (placed ?placed)
(test (<= ?i 8))
(test (<= ?j 8))
(test (< ?placed 8))
(not (queen ?i 1|2|3|4|5|6|7|8))
(not (queen 1|2|3|4|5|6|7|8 ?j))
(not (queen (?i-1)| //diagonal check there
=>
(assert (queen ?i ?j))
(assert (placed (+ ?placed 1)))
(retract ?b)
(if (< ?j 8)
then (assert (cur ?i (+ ?j 1)))
else (assert (cur (+ ?i 1) 1)))
(retract ?a)
(printout t "Placing queen" crlf)
)

(defrule horiz "Check-hor"
?a <- (cur ?i ?j)
?b <- (placed ?placed)
(test (<= ?i 8))
(test (<= ?j 8))
(test (< ?placed 8))
(queen ?i 1|2|3|4|5|6|7|8)
=>
(if (< ?j 8)
then (assert (cur ?i (+ ?j 1)))
else (assert (cur (+ ?i 1) 1)))
(retract ?a)
(printout t "Horiz" crlf)
)

(defrule vert "Check-vert"
?a <- (cur ?i ?j)
?b <- (placed ?placed)
(test (<= ?i 8))
(test (<= ?j 8))
(test (< ?placed 8))
(queen 1|2|3|4|5|6|7|8 ?j)
=>
(if (< ?j 8)
then (assert (cur ?i (+ ?j 1)))
else (assert (cur (+ ?i 1) 1)))
(retract ?a)
(printout t "Vert" crlf)
)

Answer 1

return值约束就是你要用的：

(queen =(- ?i 1) =(- ?j 1))

但是，我建议像这样完全约束女王：

(queen ?i2 ?j2)
(test (or (eq ?i ?i2)
          (eq ?j ?j2)
          (= (abs (- ?i2 ?i)) (abs (- ?j2 ?j))))))

如果您修改规则，现在可以获得部分解决方案：

CLIPS> 
(deffacts initial 
   (cur 1 1)
   (placed 0))
CLIPS> 
(defrule place
   ?a <- (cur ?i ?j)
   ?b <- (placed ?placed)
   (test (<= ?i 8))
   (test (<= ?j 8))
   (test (< ?placed 8))
   (not (and (queen ?i2 ?j2)
             (test (or (eq ?i ?i2)
                       (eq ?j ?j2)
                       (= (abs (- ?i2 ?i)) (abs (- ?j2 ?j)))))))
   =>
   (assert (queen ?i ?j))
   (assert (placed (+ ?placed 1)))
   (retract ?b)
   (if (< ?j 8)
      then (assert (cur ?i (+ ?j 1)))
      else (assert (cur (+ ?i 1) 1)))
   (retract ?a)
   (printout t "Placing queen " (+ ?placed 1) crlf))
CLIPS> 
(defrule skip
   ?a <- (cur ?i ?j)
   ?b <- (placed ?placed)
   (test (<= ?i 8))
   (test (<= ?j 8))
   (test (< ?placed 8))
   (exists (queen ?i2 ?j2)
           (test (or (eq ?i ?i2)
                     (eq ?j ?j2)
                     (= (abs (- ?i2 ?i)) (abs (- ?j2 ?j))))))
   =>
   (if (< ?j 8)
      then (assert (cur ?i (+ ?j 1)))
      else (assert (cur (+ ?i 1) 1)))
   (retract ?a))
CLIPS> (reset)
CLIPS> (run)
Placing queen 1
Placing queen 2
Placing queen 3
Placing queen 4
Placing queen 5
CLIPS> (facts)
f-0     (initial-fact)
f-3     (queen 1 1)
f-15    (queen 2 3)
f-27    (queen 3 5)
f-34    (queen 4 2)
f-46    (queen 5 4)
f-47    (placed 5)
f-76    (cur 9 1)
For a total of 8 facts.
CLIPS>

只放置了5个皇后。因为您没有在您的程序中实现任何回溯，所以可以有效地放置一个防止所有 8 个皇后都被放置的皇后。

这是 https://sites.google.com/site/drriggsnewsite/Home/half-baked-essays/composing-thoughts-an-introduction-to-rules/eight-queens-problem 中实现回溯的 N Queens 程序：

CLIPS> 
(deffunction shareDiag (?row1 ?col1 ?row2 ?col2)
  (= (abs (- ?row1 ?row2))
     (abs (- ?col1 ?col2))))
CLIPS> 
(deffacts queens
   (queen 1 1)
   (queen 2 1)
   (queen 3 1)
   (queen 4 1)
   (queen 5 1)
   (queen 6 1)
   (queen 7 1)
   (queen 8 1))
CLIPS> 
(defrule moveBadlyPlacedQueen 
   (queen ?row1 ?col1)
   ?f <- (queen ?row2 ?col2)
   (test (< ?row1 ?row2))
   (test (or (= ?col1 ?col2)
             (shareDiag ?row1 ?col1 ?row2 ?col2)))
   =>
   (retract ?f)
   (assert (queen ?row2 (+ 1 ?col2))))
CLIPS> 
(defrule backTrack  
   (declare (salience 100))
   ?g <- (queen ?row1 ?col1)
   ?f <- (queen ?row2 9)
   (test (= (+ ?row1 1) ?row2))
   =>
   (retract ?f ?g)
   (assert (queen ?row1 (+ ?col1 1))
           (queen ?row2 1)))
CLIPS> (deffacts otpt (print 1)) 
CLIPS>    
(defrule visualize 
   (declare (salience -10))
   ?f <- (print ?row)
   (queen ?row ?col)
   =>
   (retract ?f)
   (printout t ?row ":")
   (loop-for-count (- ?col 1) (printout t "|_"))
   (printout t "|Q" )
   (bind ?more (- 8 ?col))
   (if (> ?more 0) then (loop-for-count ?more (printout t "|_")))
   (printout t crlf)
   (assert (print (+ ?row 1))))
CLIPS> (reset)
CLIPS> (run)
1:|Q|_|_|_|_|_|_|_
2:|_|_|_|_|_|Q|_|_
3:|_|_|_|_|_|_|_|Q
4:|_|_|Q|_|_|_|_|_
5:|_|_|_|_|_|_|Q|_
6:|_|_|_|Q|_|_|_|_
7:|_|Q|_|_|_|_|_|_
8:|_|_|_|_|Q|_|_|_
CLIPS>

CLIPS 8 皇后 defrule

CLIPS 8 queens defrule

clips