This is the rs-dlx Reference Manual, version 1.1, generated automatically by Declt version 4.0 beta 2 "William Riker" on Sun Dec 15 07:37:34 2024 GMT+0.
The main system appears first, followed by any subsystem dependency.
rs-dlxKnuth’s Algorithm X with dancing links.
Ralph Schleicher <rs@ralph-schleicher.de>
Modified BSD License
1.1
alexandria (system).
iterate (system).
packages.lisp (file).
common.lisp (file).
dlx.lisp (file).
api.lisp (file).
Files are sorted by type and then listed depth-first from the systems components trees.
rs-dlx/common.lisppackages.lisp (file).
rs-dlx (system).
rs-dlx/dlx.lispcommon.lisp (file).
rs-dlx (system).
print-object (method).
print-object (method).
print-object (method).
print-object (method).
solve (function).
%initialize-node (function).
%make-element (function).
%make-header (function).
%make-node (function).
%make-root (function).
*search-tree* (special variable).
*search-tree-p* (special variable).
*solution* (special variable).
*solution-count* (special variable).
*solution-count-limit* (special variable).
*solutions* (special variable).
add-search-path (function).
choose-column (function).
column (reader).
(setf column) (writer).
column-header (function).
column-index-type (function).
column-insert-node (function).
column-insert-node-before (function).
column-remove-node (function).
columns (reader).
(setf columns) (writer).
copy-solution (function).
cover-column (function).
down (reader).
(setf down) (writer).
element (structure).
element-type (reader).
(setf element-type) (writer).
element-type-p (function).
header (structure).
header-index (function).
header-name (function).
index (reader).
(setf index) (writer).
left (reader).
(setf left) (writer).
make-element (function).
make-header (function).
make-node (function).
make-root (function).
make-solution (function).
merge-search-path (function).
name (reader).
(setf name) (writer).
node (structure).
non-empty-solution-p (function).
not-null-element (function).
null-element (reader).
(setf null-element) (writer).
null-element-p (function).
pop-solution (function).
push-solution (function).
remove-column (function).
remove-row (function).
right (reader).
(setf right) (writer).
root (structure).
row (reader).
(setf row) (writer).
row-header (function).
row-index-type (function).
row-insert-node (function).
row-insert-node-before (function).
row-remove-node (function).
rows (reader).
(setf rows) (writer).
search (function).
size (reader).
(setf size) (writer).
test (reader).
(setf test) (writer).
tree-from-path (function).
uncover-column (function).
up (reader).
(setf up) (writer).
value (reader).
(setf value) (writer).
with-tracing (macro).
rs-dlx/api.lispdlx.lisp (file).
rs-dlx (system).
add-matrix-column (function).
add-matrix-row (function).
array-from-matrix (function).
column-index (function).
column-name (function).
(setf column-name) (function).
(setf column-names) (function).
make-matrix (function).
map-matrix-column (function).
map-matrix-row (function).
matrix-columns (function).
matrix-element (function).
(setf matrix-element) (function).
(setf matrix-elements) (function).
matrix-from-array (function).
matrix-rows (function).
remove-matrix-column (function).
remove-matrix-column-by-name (function).
remove-matrix-columns (function).
remove-matrix-columns-by-name (function).
remove-matrix-row (function).
remove-matrix-row-by-name (function).
remove-matrix-rows (function).
remove-matrix-rows-by-name (function).
row-index (function).
row-name (function).
(setf row-name) (function).
(setf row-names) (function).
%remove-matrix-column (function).
%remove-matrix-columns (function).
%remove-matrix-row (function).
%remove-matrix-rows (function).
Packages are listed by definition order.
de.ralph-schleicher.dlxKnuth’s Algorithm X using the dancing links technique.
The algorithm itself is executed by the ‘solve’ function. The
remaining functions manage the incidence matrix, i.e. the sparse
matrix data structure based on circular doubly linked lists as
described in Knuth’s “Dancing Links” paper.
Donald E. Knuth: “Dancing Links”, ‹https://arxiv.org/abs/cs/0011047›.
rs-dlx
common-lisp.
iterate.
add-matrix-column (function).
add-matrix-row (function).
array-from-matrix (function).
column-index (function).
column-name (function).
(setf column-name) (function).
(setf column-names) (function).
make-matrix (function).
map-matrix-column (function).
map-matrix-row (function).
matrix-columns (function).
matrix-element (function).
(setf matrix-element) (function).
(setf matrix-elements) (function).
matrix-from-array (function).
matrix-rows (function).
remove-matrix-column (function).
remove-matrix-column-by-name (function).
remove-matrix-columns (function).
remove-matrix-columns-by-name (function).
remove-matrix-row (function).
remove-matrix-row-by-name (function).
remove-matrix-rows (function).
remove-matrix-rows-by-name (function).
row-index (function).
row-name (function).
(setf row-name) (function).
(setf row-names) (function).
solve (function).
%initialize-node (function).
%make-element (function).
%make-header (function).
%make-node (function).
%make-root (function).
%remove-matrix-column (function).
%remove-matrix-columns (function).
%remove-matrix-row (function).
%remove-matrix-rows (function).
*search-tree* (special variable).
*search-tree-p* (special variable).
*solution* (special variable).
*solution-count* (special variable).
*solution-count-limit* (special variable).
*solutions* (special variable).
add-search-path (function).
choose-column (function).
column (reader).
(setf column) (writer).
column-header (function).
column-index-type (function).
column-insert-node (function).
column-insert-node-before (function).
column-remove-node (function).
columns (reader).
(setf columns) (writer).
copy-solution (function).
cover-column (function).
defconst (macro).
defsubst (macro).
down (reader).
(setf down) (writer).
element (structure).
element-type (reader).
(setf element-type) (writer).
element-type-p (function).
header (structure).
header-index (function).
header-name (function).
index (reader).
(setf index) (writer).
left (reader).
(setf left) (writer).
make-element (function).
make-header (function).
make-node (function).
make-root (function).
make-solution (function).
merge-search-path (function).
name (reader).
(setf name) (writer).
node (structure).
non-empty-solution-p (function).
not-null-element (function).
null-element (reader).
(setf null-element) (writer).
null-element-p (function).
pop-solution (function).
push-solution (function).
remove-column (function).
remove-row (function).
right (reader).
(setf right) (writer).
root (structure).
row (reader).
(setf row) (writer).
row-header (function).
row-index-type (function).
row-insert-node (function).
row-insert-node-before (function).
row-remove-node (function).
rows (reader).
(setf rows) (writer).
search (function).
size (reader).
(setf size) (writer).
test (reader).
(setf test) (writer).
tree-from-path (function).
uncover-column (function).
up (reader).
(setf up) (writer).
value (reader).
(setf value) (writer).
with-tracing (macro).
Definitions are sorted by export status, category, package, and then by lexicographic order.
Add a column vector at the end of a matrix.
First argument MATRIX is a matrix object.
Second argument ELEMENTS specifies the matrix elements. Value has
to be a list with elements of the form ‘(INDEX . VALUE)’ or just
‘INDEX’ where INDEX and VALUE is the row index and value of a
matrix element. For a plain ‘INDEX’, a value of one is used.
The matrix elements have to be supplied in strictly monotonically
increasing order of the row index.
Keyword argument NAME is the symbolic identifier of the new matrix
column.
Value is the matrix object. If an error occurs, the structure of
the original matrix is retained.
See also ‘make-matrix’, ‘matrix-element’, and ‘add-matrix-row’.
Exceptional Situations:
* Signals an error of type ‘program-error’ if the matrix
elements are not specified in strictly monotonically
increasing order of the row indices or if a row index
is out of bounds.
Examples:
(array-from-matrix
(add-matrix-column (add-matrix-column (make-matrix 5 0) ’(1 2 4)) ’(0 3)))
⇒ #2A((0 1) (1 0) (1 0) (0 1) (1 0))
Add a row vector at the end of a matrix.
First argument MATRIX is a matrix object.
Second argument ELEMENTS specifies the matrix elements. Value has
to be a list with elements of the form ‘(INDEX . VALUE)’ or just
‘INDEX’ where INDEX and VALUE is the column index and value of a
matrix element. For a plain ‘INDEX’, a value of one is used.
The matrix elements have to be supplied in strictly monotonically
increasing order of the column index.
Keyword argument NAME is the symbolic identifier of the new matrix
row.
Value is the matrix object. If an error occurs, the structure of
the original matrix is retained.
See also ‘make-matrix’, ‘matrix-element’, and ‘add-matrix-column’.
Exceptional Situations:
* Signals an error of type ‘program-error’ if the matrix
elements are not specified in strictly monotonically
increasing order of the column indices or if a column
index is out of bounds.
Examples:
(array-from-matrix
(add-matrix-row (add-matrix-row (make-matrix 0 5) ’(1 2 4)) ’(0 3)))
⇒ #2A((0 1 1 0 1) (1 0 0 1 0))
Convert a matrix object into an array.
Argument MATRIX is a matrix object.
Keyword argument ELEMENT-TYPE specifies the type of the values
intended to be stored in the array elements. Value is a type
specifier. Default is the element type of the matrix object.
Value is an array with two dimensions.
See also ‘matrix-from-array’ and ‘make-matrix’.
Exceptional Situations:
* The consequences are undefined if ELEMENT-TYPE is not a valid type specifier.
Return the index of a matrix column.
Argument OBJECT can be a matrix element or a column header.
Value is the zero-based column index.
Read or update the symbolic identifier of a matrix column.
First argument OBJECT can be a matrix, a column header, or a matrix
element.
Optional second argument INDEX is the column index. This argument is
only required if OBJECT is a matrix.
Value is the symbolic identifier of the matrix column.
Exceptional Situations:
* Signals an error of type ‘program-error’ if INDEX is out
out bounds.
Update the symbolic identifiers of the matrix columns.
Argument MATRIX is a matrix object.
Value is a list of column names. Not more than the total number of matrix columns are updated. If the list is shorter, the names of the remaining matrix columns are set to ‘nil’.
Create a new matrix object.
First argument ROWS is the number of matrix rows. Value has to
be a non-negative integer.
Second argument COLUMNS is the number of matrix columns. Value
has to be a non-negative integer.
Keyword argument ELEMENT-TYPE specifies the type of the values
intended to be stored in the matrix elements. Value is a type
specifier. Default is ‘bit’.
Keyword argument NULL-ELEMENT is the value of a null element.
Value has to be either the number zero or ‘nil’. Default is
the number zero if ELEMENT-TYPE specifies a numeric type.
Otherwise, the default is ‘nil’.
Value is a matrix object.
A matrix object is a sparse matrix based on circular doubly linked
lists as described in Knuth’s “Dancing Links” paper. The matrix
elements are addressed by a zero-based row and column index. Any
index has to be a valid array index. All matrix elements are set
to the null element initially. You can read or update a matrix
element with the ‘matrix-element’ function. A more efficient way
to fill a matrix is to create an empty matrix with either zero
rows or zero columns, then use the ‘add-matrix-row’ function or
‘add-matrix-column’ function respectively to define the non-null
elements.
See also ‘matrix-rows’, ‘matrix-columns’, ‘matrix-element’,
‘matrix-elements’, ‘add-matrix-row’, ‘add-matrix-column’,
‘matrix-from-array’, and ‘array-from-matrix’.
Exceptional Situations:
* The consequences are undefined if ELEMENT-TYPE is not
a valid type specifier.
Examples:
;; Create a logical matrix with elements in {0, 1}.
(array-from-matrix (make-matrix 3 4))
⇒ #2A((0 0 0 0) (0 0 0 0) (0 0 0 0))
;; Create a logical matrix of generalized Boolean values.
(array-from-matrix (make-matrix 3 4 :element-type t))
⇒ #2A((NIL NIL NIL NIL) (NIL NIL NIL NIL) (NIL NIL NIL NIL))
Apply a function to every non-null element in a matrix column.
First argument FUNCTION is the function to be applied.
Second argument MATRIX is the matrix object.
Third argument INDEX is the column index.
The function is called with one argument, the matrix element.
Candidates for the FUNCTION argument are, e.g. ‘row-index’ or
‘row-name’.
Value is a list containing the results returned by FUNCTION.
See also ‘map-matrix-row’.
Exceptional Situations:
* Signals an error of type ‘program-error’ if INDEX is out of bounds.
Apply a function to every non-null element in a matrix row.
First argument FUNCTION is the function to be applied.
Second argument MATRIX is the matrix object.
Third argument INDEX is the row index.
The function is called with one argument, the matrix element.
Candidates for the FUNCTION argument are, e.g. ‘column-index’
or ‘column-name’.
Value is a list containing the results returned by FUNCTION.
See also ‘map-matrix-column’.
Exceptional Situations:
* Signals an error of type ‘program-error’ if INDEX is out of bounds.
Return the number of matrix columns.
Argument MATRIX is a matrix object.
Value is the number of matrix columns.
Read or update the value of a matrix element.
First argument MATRIX is a matrix object.
Second argument ROW-INDEX is the row index of the matrix element.
Third argument COLUMN-INDEX is the column index of the matrix element.
Value is the value of the referenced matrix element.
Exceptional Situations:
* Signals an error of type ‘program-error’ if ROW-INDEX or
COLUMN-INDEX is out of bounds.
* Signals an error of type ‘type-error’ if the new value is
not compatible with the matrix element type.
Update multiple elements of a matrix.
First argument MATRIX is a matrix object.
Optional second argument START-ROW is the row index of the first
matrix element. Default is zero.
Optional third argument START-COLUMN is the column index of the
first matrix element. Default is zero.
Value is a two-dimensional array whose elements will be assigned
to the block starting at START-ROW and START-COLUMN.
Exceptional Situations:
* Signals an error of type ‘program-error’ if START-ROW or
START-COLUMN is out of bounds or if the dimensions of the
new value relative to START-ROW and START-COLUMN exceed
the matrix dimensions.
* Signals an error of type ‘type-error’ if the array element type of the new value is not a subtype of the matrix element type.
Convert an array into a matrix object.
Argument ARRAY is an array with two dimensions.
Keyword argument ELEMENT-TYPE specifies the type of the values
intended to be stored in the matrix elements. Value is a type
specifier. Default is ‘bit’.
Keyword argument NULL-ELEMENT defines the value of a null element.
Default is the number zero if ELEMENT-TYPE specifies a numeric
type. Otherwise, the default is ‘nil’.
Value is a matrix object.
See also ‘array-from-matrix’ and ‘make-matrix’.
Exceptional Situations:
* The consequences are undefined if ELEMENT-TYPE is not
a valid type specifier.
Return the number of matrix rows.
Argument MATRIX is a matrix object.
Value is the number of matrix rows.
Remove a matrix column.
First argument MATRIX is a matrix object.
Second argument INDEX is a column index.
Value is the matrix object. If an error occurs, the structure of the
original matrix is retained.
See also ‘remove-matrix-column-by-name’ and ‘remove-matrix-columns’.
Exceptional Situations:
* Signals an error of type ‘program-error’ if INDEX is out of bounds.
Remove a matrix column.
First argument MATRIX is a matrix object.
Second argument NAME is a column name. Only the first column name
matching NAME will be removed.
Keyword argument TEST defines the function to compare two column names
for equality. Default is ‘eql’.
Value is the matrix object. If an error occurs, the structure of the
original matrix is retained.
See also ‘remove-matrix-column’ and ‘remove-matrix-columns-by-name’.
Exceptional Situations:
* Signals an error of type ‘program-error’ if no column named NAME exists.
Remove some matrix columns.
First argument MATRIX is a matrix object.
Second argument INDICES is a list of column indices. No error is
signaled if a column index does not exist.
Value is the matrix object.
See also ‘remove-matrix-columns-by-name’ and ‘remove-matrix-column’.
Remove some matrix columns.
First argument MATRIX is a matrix object.
Second argument NAMES is a list of column names. No error is signaled
if a column name does not exist.
Keyword argument TEST defines the function to compare two column names
for equality. Default is ‘eql’.
Value is the matrix object.
See also ‘remove-matrix-columns’ and ‘remove-matrix-column-by-name’.
Remove a matrix row.
First argument MATRIX is a matrix object.
Second argument INDEX is a row index.
Value is the matrix object. If an error occurs, the structure of the
original matrix is retained.
See also ‘remove-matrix-row-by-name’ and ‘remove-matrix-rows’.
Exceptional Situations:
* Signals an error of type ‘program-error’ if INDEX is out of bounds.
Remove a matrix row.
First argument MATRIX is a matrix object.
Second argument NAME is a row name. Only the first row name matching
NAME will be removed.
Keyword argument TEST defines the function to compare two row names
for equality. Default is ‘eql’.
Value is the matrix object. If an error occurs, the structure of the
original matrix is retained.
See also ‘remove-matrix-row’ and ‘remove-matrix-rows-by-name’.
Exceptional Situations:
* Signals an error of type ‘program-error’ if no row named NAME exists.
Remove some matrix rows.
First argument MATRIX is a matrix object.
Second argument INDICES is a list of row indices. No error is
signaled if a row index does not exist.
Value is the matrix object.
See also ‘remove-matrix-rows-by-name’ and ‘remove-matrix-row’.
Remove some matrix rows.
First argument MATRIX is a matrix object.
Second argument NAMES is a list of row names. No error is signaled
if a row name does not exist.
Keyword argument TEST defines the function to compare two row names
for equality. Default is ‘eql’.
Value is the matrix object.
See also ‘remove-matrix-rows’ and ‘remove-matrix-row-by-name’.
Return the row index of a matrix element.
Argument OBJECT can be a matrix element or a row header.
Value is the zero-based row index.
Read or update the symbolic identifier of a matrix row.
First argument OBJECT can be a matrix, a row header, or a matrix
element.
Optional second argument INDEX is the row index. This argument is
only required if OBJECT is a matrix.
Value is the symbolic identifier of the matrix row.
Exceptional Situations:
* Signals an error of type ‘program-error’ if INDEX is out out bounds.
Update the symbolic identifiers of the matrix rows.
Argument MATRIX is a matrix object.
Value is a list of row names. Not more than the total number of matrix rows are updated. If the list is shorter, the names of the remaining matrix rows are set to ‘nil’.
Apply Knuth’s Algorithm X to an exact cover problem.
Argument MATRIX is the incidence matrix of the exact cover problem
where the rows represent the set of choices (a.k.a. possibilities
or candidates) and the columns represent the set of constraints.
Value is a matrix object.
Keyword argument MAXIMUM-NUMBER-OF-SOLUTIONS limits the number of
solutions to search for. Value has to be a positive integer. A
value of ‘nil’ means that there is no limit, i.e. search for all
solutions. Default is one.
Keyword argument IF-DOES-NOT-EXIST specifies the action to be taken
if no solution can be found. A value of ‘:error’ means to signal
an error. A value of ‘nil’ means to return ‘nil’ to indicate
failure. Default is ‘:error’.
If keyword argument RAW is true, the row indices in a solution are
in the order as they have been found. Otherwise, they are sorted
in ascending order. Default is false.
If keyword argument SEARCH-TREE is true, build the complete search
tree and return it as the secondary value.
Return value is the list of found solutions. Each solution is a
list of row indices of the incidence matrix. Secondary value is
the search tree.
See also ‘make-matrix’.
Exceptional Situations:
* Signals an error of type ‘arithmetic-error’ if no solution can be found and the argument IF-DOES-NOT-EXIST is ‘:error’.
Examples:
;; Knuth’s example from the “Dancing Links” paper.
(let ((a (matrix-from-array #2A((0 0 1 0 1 1 0)
(1 0 0 1 0 0 1)
(0 1 1 0 0 1 0)
(1 0 0 1 0 0 0)
(0 1 0 0 0 0 1)
(0 0 0 1 1 0 1)))))
(setf (column-names a) ’(A B C D E F G))
(let ((s (first (solve a))))
(format t "Found a solution containing~%")
(dolist (i s)
(format t "~:R row with columns ~S~%"
(1+ i) (map-matrix-row #’column-name a i)))
s))
⇒ (0 3 4)
;; And the terminal output is:
Found a solution containing
first row with columns (C E F)
fourth row with columns (A D)
fifth row with columns (B G)
The complete search tree.
Value is an alist with cons cells of the form ‘(ITEM . ALIST)’ where ITEM is an element of the search path and ALIST is a subsequent search tree. If ALIST is ‘nil’, the cell is a leaf node.
Whether or not to build the search tree.
The current solution, i.e. search path.
Value is an adjustable vector with fill pointer. This is slightly slower than a simple list but it doesn’t cons.
The number of found solutions.
The maximum number of solutions to search for.
A value of ‘nil’ means that there is no limit, i.e. search for all solutions. Default is to search for a single solution.
The set of found solutions.
Define a constant variable.
This is like ‘defconstant’ except that the initially set value is reused when the ‘defconst’ form is evaluated again.
Define an inline function.
This is like ‘defun’ except that the function is globally marked for inline expansion by the compiler.
Mark analysis code.
Link a ‘node’ object to itself.
Remove a matrix column.
Remove some matrix columns.
Remove a matrix row.
Remove some matrix rows.
Add a search path to the ‘*search-tree*’ special variable.
Choose a column header from matrix H.
Find a column header by it’s index.
Signal a ‘program-error’ if the column does not exist.
Return the type specifier for a valid column index.
Insert node NODE in it’s column.
Insert node NODE in the column before node OTHER.
Remove node NODE from it’s column.
Create a copy of the current search path as a list.
Cover column C.
Return true if OBJECT is a valid element.
Return the header index of HEADER.
Return the header name of HEADER.
Create a new ‘element’ object.
Create a new ‘header’ object.
Create a new ‘node’ object.
Create a new ‘root’ object.
Create a new search path object.
Merge a search path into a search tree.
Return true if the current search path is not empty.
Return the complement of the null element.
Return true if OBJECT is a null element.
Remove the most recently added item from the current search path.
Add an item to the current search path.
Remove the matrix column designated by HEADER. Update the size of affected rows but not the root object or any column header.
Remove the matrix row designated by HEADER.
Update the size of affected columns but not the root object
or any row header.
Find a row header by it’s index.
Signal a ‘program-error’ if the row does not exist.
Return the type specifier for a valid row index.
Insert node NODE in it’s row.
Insert node NODE in the row before node OTHER.
Remove node NODE from it’s row.
Knuth’s Algorithm X.
Convert a search path into a search tree.
Uncover column C.
An element (data object) of a dancing links matrix.
A header node of a dancing links matrix.
Base class for all nodes of a dancing links matrix.
structure-object.
(or null de.ralph-schleicher.dlx::node)
The root node of a dancing links matrix.
node.
fixnum
0
t
| Jump to: | %
(
A C D E F H I L M N P R S T U V W |
|---|
| Jump to: | %
(
A C D E F H I L M N P R S T U V W |
|---|
| Jump to: | *
C D E I L N R S T U V |
|---|
| Jump to: | *
C D E I L N R S T U V |
|---|
| Jump to: | A C D E F H N P R S |
|---|
| Jump to: | A C D E F H N P R S |
|---|