内容简介: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:
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.
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。