From crabapple.srv.cs.cmu.edu!fs7.ece.cmu.edu!europa.eng.gtefsd.com!uunet!elroy.jpl.nasa.gov!ames!kronos.arc.nasa.gov!jair-ed Tue Sep 14 19:25:29 EDT 1993 Article: 4 of comp.ai.jair.papers Xref: crabapple.srv.cs.cmu.edu comp.ai.jair.papers:4 Newsgroups: comp.ai.jair.papers Path: crabapple.srv.cs.cmu.edu!fs7.ece.cmu.edu!europa.eng.gtefsd.com!uunet!elroy.jpl.nasa.gov!ames!kronos.arc.nasa.gov!jair-ed From: minton@ptolemy.arc.nasa.gov Subject: Online Appendix for Ginsberg's "Dynamic Backtracking" Message-ID: <1993Sep14.042128.19891@kronos.arc.nasa.gov> Originator: jair-ed@polya.arc.nasa.gov Sender: usenet@kronos.arc.nasa.gov (usenet@ptolemy.arc.nasa.gov) Nntp-Posting-Host: polya.arc.nasa.gov Organization: NASA/ARC Information Sciences Division Date: Tue, 14 Sep 1993 04:21:28 GMT Approved: jair-ed@ptolemy.arc.nasa.gov Lines: 226 I've been requested to post the online appendix for Ginsberg's "Dynamic Backtracking". This appendix contains the data required to generate the crossword puzzles used in Ginsberg's experiments. (The Dynamic Backtracking article was the last thing posted here. It was posted at the end of August.) Once again, here is the reference for the Ginsberg paper, in case you want to access it: Ginsberg, Matthew L. "Dynamic Backtracking", Volume 1 (1993), pages 25-46. Postscript: volume1/ginsberg93a.ps Online Appendix: volume1/ginsberg93a-appendix.lisp (data file, contains crossword puzzles used in experiments) Below you will find the file ginsberg93a-appendix.lisp. ------------------------Cut here---------------------------------------- ;;; -*- Mode: LISP; Syntax: Common-lisp; Package: USER; Base: 10 -*- ;; This file contains the sample frames that were used in the experiments ;; described in "Dynamic backtracking." ;; There are 19 frames. Each is a two-dimensional array of T/NIL. A T ;; indicates that the associated square in the crossword frame is blank, ;; and a NIL indicates that it is a black square that does not need to ;; have a letter inserted. The unix dictionary /usr/dict/words was used ;; to fill the frames, subject to the usual condition that no word was ;; permitted to appear twice in the same puzzle. (defparameter f1 (make-array '(2 2) :initial-contents '((t nil) (t t)))) (defparameter f2 (make-array '(3 3) :initial-contents '((nil t t) (t t t) (t t t)))) (defparameter f3 (make-array '(4 4) :initial-contents '((t t t nil) (t t t t) (t t t t) (nil t t t)))) (defparameter f4 (make-array '(5 5) :initial-contents '((t t t nil nil) (t t t t nil) (t t t t t) (nil t t t t) (nil nil t t t)))) (defparameter f5 (make-array '(5 5) :initial-contents '((t t t t nil) (t t t nil t) (t t t t t) (t nil t t t) (nil t t t t)))) (defparameter f6 (make-array '(5 5) :initial-contents '((t t t t t) (t t t nil t) (t t t t t) (t nil t t t) (t t t t t)))) (defparameter f7 (make-array '(6 6) :initial-contents '((t t t t t nil) (t nil t t t t) (t t t nil t t) (t t nil t t t) (t t t t nil t) (nil t t t t t)))) (defparameter f8 (make-array '(7 7) :initial-contents '((t t t t nil t t) (t t t nil t t t) (t t nil t t t nil) (t t t t t t t) (nil t t t nil t t) (t t t nil t t t) (t t nil t t t t)))) (defparameter f9 (make-array '(7 7) :initial-contents '((nil nil t t t nil nil) (nil t t t t t nil) (t t t nil t t t) (t t t t t t t) (t t t nil t t t) (nil t t t t t nil) (nil nil t t t nil nil)))) (defparameter f10 (make-array '(7 7) :initial-contents '((t t t nil t t t) (t t t nil t t t) (t t t t t t t) (nil nil t nil t nil nil) (t t t t t t t) (t t t nil t t t) (t t t nil t t t)))) (defparameter f11 (make-array '(7 7) :initial-contents '((nil nil t t t t nil) (nil t t t t t t) (t t t nil t t t) (t t t nil t t t) (t t t nil t t t) (t t t t t t nil) (nil t t t t nil nil)))) (defparameter f12 (make-array '(8 8) :initial-contents '((t t t t nil t t t) (t t t t nil t t t) (t t t t nil t t t) (nil nil nil t t t t t) (t t t t t nil nil nil) (t t t nil t t t t) (t t t nil t t t t) (t t t nil t t t t)))) (defparameter f13 (make-array '(9 9) :initial-contents '((t t t t nil t t t t) (t t t t nil t t t t) (t t t nil nil nil t t t) (t t t t t t t t t) (nil nil nil t t t nil nil nil) (t t t t t t t t t) (t t t nil nil nil t t t) (t t t t nil t t t t) (t t t t nil t t t t)))) (defparameter f14 (make-array '(10 10) :initial-contents '((nil nil nil t t t t nil nil nil) (nil nil t t t t t nil nil nil) (nil t t t t t t t nil nil) (t t t t t nil nil t t t) (t t t t nil nil nil t t t) (t t t nil nil nil t t t t) (t t t nil nil t t t t t) (nil nil t t t t t t t nil) (nil nil nil t t t t t nil nil) (nil nil nil t t t t nil nil nil)))) (defparameter f15 (make-array '(11 11) :initial-contents '((t t t t nil nil nil t t t t) (t t t t t nil t t t t t) (t t t t t nil t t t t t) (t t t nil t t t nil t t t) (nil t t t t t nil t t t nil) (nil nil nil t t t t t nil nil nil) (nil t t t nil t t t t t nil) (t t t nil t t t nil t t t) (t t t t t nil t t t t t) (t t t t t nil t t t t t) (t t t t nil nil nil t t t t)))) (defparameter f16 (make-array '(13 13) :initial-contents '((t t t nil t t t t nil t t t t) (t t t nil t t t t nil t t t t) (t t t nil t t t t nil t t t t) (t t t t t t nil t t t nil nil nil) (nil nil nil t t t nil t t t t t t) (t t t t t nil t t t nil t t t) (t t t t nil t t t nil t t t t) (t t t nil t t t nil t t t t t) (t t t t t t nil t t t nil nil nil) (nil nil nil t t t nil t t t t t t) (t t t t nil t t t t nil t t t) (t t t t nil t t t t nil t t t) (t t t t nil t t t t nil t t t)))) (defparameter f17 (make-array '(15 15) :initial-contents '((t t t nil t t t nil t t t nil t t t) (t t t nil t t t nil t t t nil t t t) (t t t t t t t nil t t t t t t t) (nil nil t t t t nil t t t t t t nil nil) (t t t t t nil t t t nil t t t t t) (t t t t nil t t t t t nil t t t t) (t t t t t t t nil t t t nil t t t) (nil nil nil t t t nil nil nil t t t nil nil nil) (t t t nil t t t nil t t t t t t t) (t t t t nil t t t t t nil t t t t) (t t t t t nil t t t nil t t t t t) (nil nil t t t t t t nil t t t t nil nil) (t t t t t t t nil t t t t t t t) (t t t nil t t t nil t t t nil t t t) (t t t nil t t t nil t t t nil t t t)))) (defparameter f18 (make-array '(15 15) :initial-contents '((t t t t nil t t t t t nil t t t t) (t t t t nil t t t t t nil t t t t) (t t t t nil t t t t t nil t t t t) (t t t t t nil t t t nil nil t t t t) (nil nil nil nil t t t nil nil t t t nil nil nil) (t t t nil t t t nil t t t nil t t t) (t t t t nil t t t t t t t t t t) (t t t t nil nil t t t nil nil t t t t) (t t t t t t t t t t nil t t t t) (t t t nil t t t nil t t t nil t t t) (nil nil nil t t t nil nil t t t nil nil nil nil) (t t t t nil nil t t t nil t t t t t) (t t t t nil t t t t t nil t t t t) (t t t t nil t t t t t nil t t t t) (t t t t nil t t t t t nil t t t t)))) (defparameter f19 (make-array '(15 15) :initial-contents '((t t t t nil t t t t t nil t t t t) (t t t t nil t t t t t nil t t t t) (t t t t nil t t t t t nil t t t t) (t t t t t t t nil t t t t t t t) (nil nil nil t t t nil t t t t t nil nil nil) (t t t t t nil t t t nil t t t t t) (t t t t nil t t t t t t nil t t t) (t t t t nil t t t t t nil t t t t) (t t t nil t t t t t t nil t t t t) (t t t t t nil t t t nil t t t t t) (nil nil nil t t t t t nil t t t nil nil nil) (t t t t t t t nil t t t t t t t) (t t t t nil t t t t t nil t t t t) (t t t t nil t t t t t nil t t t t) (t t t t nil t t t t t nil t t t t))))