Exploring constraint programming with CL's Screamer

栏目: IT技术 · 发布时间: 4年前

内容简介:A long time ago I wrote a sudoku solver - I suppose everyone does something of the sort at some point. I laboriously wrote the algorithm to solve it - the imperative way of solving this kinds of problems.I've encountered the CL library Screamer before, but

A long time ago I wrote a sudoku solver - I suppose everyone does something of the sort at some point. I laboriously wrote the algorithm to solve it - the imperative way of solving this kinds of problems. Constraint programming is the declarative way.

I've encountered the CL library Screamer before, but for some reason the cranial semantic network didn't quite connect these concepts. It took seeing Screamer listed on the list of CP implementations , alongside Google's OR-Tools , for those particular neurons to fire.

The documentation has links to the original Screamer publications, one from as far back as 1991!

1 Cryptarithmetic

The very first thing I wanted to solve using CP is a cryptarithm , so I grabbed my Emacs 26 machine. The first challenge was SEND+MORE=MONEY :

(ql:quickload :screamer)
(ql:quickload :split-sequence)

(defpackage :cp
  (:use :cl)
  (:use :screamer))

(in-package :cp)

;; SEND + MORE = MONEY
(all-values
  (let ((S (an-integer-betweenv 1 9 :S))
        (E (an-integer-betweenv 0 9 :E))
        (N (an-integer-betweenv 0 9 :N))
        (D (an-integer-betweenv 0 9 :D))
        (M (an-integer-betweenv 1 9 :M))
        (O (an-integer-betweenv 0 9 :O))
        (R (an-integer-betweenv 0 9 :R))
        (Y (an-integer-betweenv 0 9 :Y)))

    ;; All values are unique
    (assert! (/=V S E N D M O R Y))

    ;; Final constraints
    (assert! (=V (+V (*V 1000 S) (*V 100 E) (*V 10 N) D
                     (*V 1000 M) (*V 100 O) (*V 10 R) E)
                 (+V (*V 10000 M) (*V 1000 O) (*V 100 N) (*V 10 E) Y)))

    (solution (list S E N D M O R Y)
              (static-ordering #'divide-and-conquer-force))))
;; => ((9 5 6 7 1 0 8 2))

Putting this into a function:

(defun puzzle-words(puzzle op)
  (let ((split (split-sequence:split-sequence op puzzle)))
    (append (butlast split) (split-sequence:split-sequence #\= (first (last split))))))

(defun decompose-vars(word vars)
  (apply
   #'+V
   (loop
      for i from (1- (length word)) downto 0
      for char across word
      for var = (gethash char vars)
      collecting (*V var (expt 10 i)))))

(defun solve(puzzle-string)
  (let* ((puzzle (remove-if-not (lambda (char)
                                  (or (alphanumericp char)
                                      (member char '(#\+ #\- #\* #\=))))
                                puzzle-string))
         (op (find-if-not #'upper-case-p puzzle))
         (op-func (case op
                    (#\x #'*V)
                    (#\+ #'+V)
                    (#\- #'-V)))
         (puzzle-words (puzzle-words puzzle op))
         (puzzle-chars (remove-duplicates (apply #'concatenate 'string puzzle-words)))
         (puzzle-vars
          (loop for char across puzzle-chars
             collecting (an-integer-betweenv
                         (if (some (lambda (puzzle-word)
                                     (char= char (schar puzzle-word 0)))
                                   puzzle-words)
                             1
                             0)
                         9 char)))
         (vars (make-hash-table :size (length puzzle-chars))))
    (loop
       for char across puzzle-chars
       for var in puzzle-vars do
         (setf (gethash char vars) var))

    ;; All values are unique
    (assert! (apply #'/=V puzzle-vars))

    ;; Final constraints
    (assert! (=V (funcall op-func
                          (decompose-vars (first puzzle-words) vars)
                          (decompose-vars (second puzzle-words) vars))
                 (decompose-vars (third puzzle-words) vars)))

    ;; Solve
    (map 'list
         ;; Solution printer function
         (lambda(numbers)
           (map 'string (lambda(char)
                          (if (upper-case-p char)
                              (coerce (format nil "~A" (nth (position char puzzle-chars)
                                                            numbers))
                                      'character)
                              char))
                puzzle-string))
         (all-values
           (solution puzzle-vars
                     (static-ordering #'divide-and-conquer-force))))))

;; REPL
CP> (solve "SEND+MORE=MONEY")
("9567+1085=10652")
CP> (solve "FUNxBBG=SUMMER")
("715x446=318890" "746x335=249910")

Of course, for these kinds of problems, the more heuristics one could add to prune down the search-space, the better.

2 The N -Queens Puzzle

In the previous example, functions like *V and =V were predefined, so it was pretty straightforward to implement. That's because we used the constraint propagation features of Screamer. The doc distinguishes between constraint propagation features and non-deterministic features.

This paper has an example of solving the N -Queens Problem using Screamer, but the solution uses the constraint propagation features. I wanted to explore the non-deterministic features first, before I dive into how exactly the magic of the constraint propagation features works.

(defun list-either(a-list)
  (cond ((rest a-list)
         (either (first a-list) (list-either (rest a-list))))
        (a-list
         (first a-list))
        (t
         (fail))))

(defun attacks-p (a b)
  (= (abs (- (first a) (first b)))
     (abs (- (second a) (second b)))))

(defun a-piece(n row &optional pieces)
  (let* ((occupied-columns (map 'list #'second pieces))
         (columns (loop for count from 0 below n
                     unless (member count occupied-columns)
                     collect count)))
    (list row
          (list-either columns))))

(defun a-valid-piece (n row &optional pieces)
  (let ((piece (a-piece n row pieces)))
    (if (notany (lambda (arg)
                  (attacks-p arg piece))
                pieces)
        piece
        (fail))))

(defun complete-set (n &optional (row 0) pieces)
  (if (< row n)
      (complete-set n (1+ row) (append pieces (list (a-valid-piece n row pieces))))
      pieces))

Sample run for 6-queens problem - which, surprisingly, has fewer solutions (4) than the 5-queens problem (10):

CP> (all-values (complete-set 6))

(((0 1) (1 3) (2 5) (3 0) (4 2) (5 4)) ((0 2) (1 5) (2 1) (3 4) (4 0) (5 3))
 ((0 3) (1 0) (2 4) (3 1) (4 5) (5 2)) ((0 4) (1 2) (2 0) (3 5) (4 3) (5 1)))

By inserting a breakpoint I could observe the backtracking:

Exploring constraint programming with CL's Screamer

Figure 1: Backtracking on the 6queens problem

either and fail provide a declarative way to enumerate the search-space and backtrack. Screamer does this by rewriting non-deterministic functions and using Continuation-passing style - a technique the papers call CPS conversion. You can see this in the macroexpansion of a non-deterministic defun statement:

(macroexpand-1 '(defun foo-or-bar () (either :foo :bar)))
;; Expands to:
(EVAL-WHEN (:COMPILE-TOPLEVEL :LOAD-TOPLEVEL :EXECUTE)
  (SCREAMER::CACHE-DEFINITION 'FOO-OR-BAR 'NIL
                              '((EITHER
                                  :FOO
                                  :BAR))
                              '(A-BOOLEAN))
  (COMMON-LISP:DEFUN FOO-OR-BAR ()
    (DECLARE (IGNORE))
    (SCREAMER::SCREAMER-ERROR
     "Function ~S is a nondeterministic function. As such, it~%~
                  must be called only from a nondeterministic context."
     'FOO-OR-BAR))
  (COMMON-LISP:DEFUN FOO-OR-BAR-NONDETERMINISTIC (#:CONTINUATION-915)
    #:CONTINUATION-915
    (PROGN
     (LET ((#:CONTINUATION-919
            #'(LAMBDA (&OPTIONAL #:DUMMY-917 &REST #:OTHER-918)
                (DECLARE (SCREAMER::MAGIC)
                         (IGNORE #:OTHER-918))
                (IF #:DUMMY-917
                    (FUNCALL #:CONTINUATION-915 :FOO)
                    (FUNCALL #:CONTINUATION-915 :BAR)))))
       (SCREAMER::A-BOOLEAN-NONDETERMINISTIC #:CONTINUATION-919))))
  (SCREAMER::DECLARE-NONDETERMINISTIC 'FOO-OR-BAR)
  'FOO-OR-BAR)

3 Simultaneous linear equations

With this problem I finally understood the limits and essense of Screamer. Having seen how easy it is to solve this kind of problem in CLP(R) , I tested this out in Screamer:

(let ((x (a-realv :x))
      (y (a-realv :y)))

  ;; x - y = -1
  (assert! (equalv (-V x y) -1))
  ;; 3x + y = 9
  (assert! (equalv (+V (*V 3 x) y) 9))

  (list (value-of x)
        (value-of y)))

Of course it didn't work. There is no such magic, at least not in Screamer. Although there are features I haven't used, such as undoing side-effects and writing custom force-functions, after figuring out why the above didn't work I think I truly understood how Screamer works. I don't know how CLP(R) works, but one of the Screamer papers gives some insight:

...In contrast, Screamer uses constraint satisfaction features methods based on
range propagation rather than the linear programming techniques used in CLP(R)
and CHIP.

So here is what works in Screamer:

CP> (one-value (let ((x (a-realv :x))
                     (y (a-realv :y)))

                 ;; x - y = -1
                 (assert! (equalv (-V x y) -1))
                 ;; 3x + y = 9
                 (assert! (equalv (+V (*V 3 x) y) 9))

                 (solution (list x y)
                           (static-ordering #'linear-force))))
(2 3)

The variables have no finite range, so we can't use the divide-and-conquer force function, but they have a countable set, so we can use linear-force .

linear-force works by trying each potential value in turn, so if we wrapped the code above in all-values rather than one-value it would never halt.


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

产品设计思维

产品设计思维

王丁 / 机械工业出版社 / 2017-8-1 / 79

这是一本关于“产品设计思维与方法”方面的实战书籍。融合了笔者多年行为实践经验,以大量的图例和案例详细展现产品设计背后的真实思维与构建方法,全面系统地分析电子商务产品设计方案,从规划、架构、逻辑、原型等多个方面对电商平台的产品设计过程进行细致分享。 在互联网产品设计领域,设计理念与设计方法却是能持续复用的,只要你掌握了一套行之有效的互联网产品设计方法论与工具,那无论是从事什么样的行业,你都能快......一起来看看 《产品设计思维》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

html转js在线工具
html转js在线工具

html转js在线工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具