Programs to Read

I write lots of CWEB programs, primarily for my own edification. If there is sufficient interest, I'll make a large subset of them available via the Internet. For now, I'm listing only a few. The first one was used as a handout for a lecture on literate programming that I once gave at Frys Electronics in Sunnyvale. The next two show (by quite different methods) that exactly 2,432,932 knight's tours are unchanged by 180-degree rotation of the chessboard. The fourth was used to compute some of the tables in Axioms and Hulls that several people have asked about. The fifth was used in one of my otherwise unpublished lectures in the Computer Musings series. The next few were requested by members of the Academy of Recreational Mathematicians in Japan. And so on.

Note: Many of my programs, including the first two samples, use the conventions and library of The Stanford GraphBase.

HWTIME

Brief demonstration of CWEB: "Hello, world" plus time (October 1992)

SHAM

Enumerates symmetrical Hamiltonian cycles (December 1992)

OBDD

Enumerates perfect matchings of bipartite graphs (May 1996)

REFLECT; also a change file for REFLECT

Enumerates equivalence classes of reflection networks, aka CC systems (January 1991)

HULL, HULLS, HULLT, HULLTR

Programs used as examples in Axioms and Hulls; also change files for ngons, square deletion, and uniform input distribution

TCALC

Interactively calculates with humungous numbers (December 1994)

DECAGON; also a change file for DECAGON (stars); also a change file for DECAGON (color); also a change file for DECAGON (color stars)

Packs golden triangles into decagons, stars, pentagons, etc. (September 1994)

ANTISLIDE; also a change file for ANTISLIDE

Finds solutions to Strijbos's antisliding block puzzle (November 1994)

ANTISLIDE3

Improved version of ANTISLIDE, finds all nonisomorphic solutions (December 1996)

SETSET

Enumerates nonisomorphic unplayable hands in the game of SET® (February 2001)

SETSET-ALL

Improvement of SETSET---fifty times faster---when a huge automorphism group is considered (March 2001)

SETSET-RANDOM

Simple Monte Carlo routine to validate the previous two programs (March 2001)

SLIDING

Finds solutions to sliding block puzzles (November 2001; revised January 2009 and September 2020)

STRAIGHTEN

Computes irreducible matrix representations of permutations (August 2003)

DOMINATION

Computes the covering relation for an interesting partial ordering of multiset permutations (August 2003)

FOG2MF

Rudimentary conversion from Fontographer to METAFONT (August 1996)

LAGFIB

Calculator of weights related to the random number generator below (July 1997)

GARSIA-WACHS

Simple implementation of Algorithm 6.2.2G (January 1998, revised September 2004)

HALFTONE

Preprocessor for typeset halftones; also example input files lisa-64, lisa-rot, lisa-128, lin-64, lin-rot, lin-128, lib-64, lib-rot, lib-128 (June 1998)

DOT-DIFF

Preprocessor for halftones by dot diffusion; also an example input file lisa-512, and a change file for EPS output (June 1998)

TOGPAP

Generates examples of halftones for paper P116 on dot diffusion (June 1998)

DANCE, POLYOMINOES, POLYIAMONDS, POLYSTICKS, QUEENS

Generates examples for paper P159 on dancing links (July 1999); and another, SUDOKU (February 2005); also a change file for Monte Carlo estimates (corrected 25 Jan 07)

GDANCE, MACMAHON-TRIANGLES-SYM-TILE, XGDANCE, GDANCE-CUTOFF

Experimental extensions of the Dancing Links algorithm (November 2000)

HAMDANCE

A dancing-link-based program for Hamiltonian circuits (May 2001, slightly revised March 2010), which you might want to compare to the more traditional algorithm of HAM

POLYNUM, POLYSLAVE, and their change files POLYNUM-RESTART and POLYSLAVE-RESTART for long runs

Enumerates polyominoes with Iwan Jensen's algorithm, thousands of times faster than previous approaches (but is a memory hog); also notes from Jensen about potential further improvements and the probable value of t(48); also a MetaPost source file polyomino.mp to make an illustration for the documentation of both POLYNUM and a now-obsolete program POLYENUM

ADVENT

The original Crowther/Woods Adventure game, Version 1.0, translated into CWEB form (version of 21 January 2022); this program was published as Chapter 27 of my Fun and Games book, and errata can be in the corrections to pages 235--394 that appear on that webpage

ROST

Monte Carlo confirmation of exercise 5.1.4--40 (October 1998)

RAN-PRIM

Monte Carlo exploration of exercise 5.3.4--40 (October 1998)

STRONGCHAIN

finds shortest strong addition chains, also called Lucas chains or Chebyshev chains (August 2000)

KODA-RUSKEY

A fascinating generalized reflected Gray-code generator (new version, June 2001)

LI-RUSKEY

An even more fascinating, massive generalization of the previous program (June 2001); also a PostScript illustration li-ruskey.1 made by the MetaPost source file li-ruskey.mp

SPIDERS

A further improvement to the previous two (December 2001), and its PostScript illustration deco.5

TOPSWOPS and TOPSWOPS-FWD

Two ways to find the longest plays of John Conway's "topswops" game (August 2001)

CO-DEBRUIJN

A quick-and-dirty implementation of the recursive coroutines Algorithms 7.2.1.1R and 7.2.1.1D, which generate a de Bruijn cycle; also a Mathematica program co-debruijn.m to check the ranking and unranking functions in exercises 7.2.1.1--97 through 99

POSETS0 and POSETS

Two programs to evaluate the numbers in Sloane's sequence A006455, formerly M1805 (December 2001)

ERECTION

The algorithms described in my paper ``Random Matroids'' (March 2003)

UNAVOIDABLE

A longest word that avoids all n-letter subwords in an interesting minimal set constructed by Champernaud, Hansel, and Perrin (July 2003)

UNAVOIDABLE2

A longest word that avoids all n-letter subwords in an interesting minimal set constructed by Mykkeltveit (August 2003)

GRAYSPAN, SPSPAN, GRAYSPSPAN, and a MetaPost source file for SPSPAN, plus an auxiliary program SPGRAPH

Three instructive ways to generate all spanning trees of a graph (August 2003)

SAND

A hastily written program to experiment with sandpiles as in exercise 7.2.1.6--103 (December 2004)

ZEILBERGER, FRANÇON, VIENNOT, an explanatory introduction, and a MetaPost source file for VIENNOT

Three Catalan bijections related to Strahler numbers, pruning orders, and Kepler towers (February 2005)

BACK-KEPLER-TOWERS

Generates all Kepler towers that can be made from a given number of bricks

PROPP

A fourth Catalan bijection, this one related to Narayana numbers

LINKED-TREES

An amazingly short program to generate linked trees with given node degrees (March 2005)

VACILLATE

A program to experiment with set partitions and vacillating tableau loops (May 2005)

EMBED

An algorithm of Hagauer, Imrich, and Klavžar to embed a median graph in a hypercube (June 2005)

LP

An expository implementation of linear programming (August 2005)

HORN-COUNT

A program to enumerate Horn functions; also a change file krom-count.ch, which adapts it to Krom functions (aka 2SAT instances) (August 2005)

15PUZZLE-KORF0 and 15PUZZLE-KORF1

Two programs to solve 15-puzzle problems rather fast (but not state-of-the-art) (August 2005)

ACHAIN0, ACHAIN1, ACHAIN2, ACHAIN3, ACHAIN4, and ACHAIN-ALL

A series of programs to find minimal addition chains (September 2005), plus a trivial auxiliary program ACHAIN-DECODE.

HYPERBOLIC and a MetaPost source file for HYPERBOLIC

A program that analyzes and helps to draw the hyperbolic plane tiling made from 36-45-90 triangles (October 2005)

BOOLCHAINS

A suite of programs that find the complexity of almost all Boolean functions of five variables (December 2005)

FCHAINS4X and and a change file for don't-cares

Programs for interactive minimization of multiple-output 4-input Boolean functions using the `greedy footprint' method (February 2006, revised October 2010)

TICTACTOE, a gzipped tar file tictactoe.tgz

Various programs used when preparing the tic-tac-toe examples in Section 7.1.2 (March 2006)

PRIME-SIEVE and its much faster (but more complex) cousin PRIME-SIEVE-SPARSE, plus a change file PRIME-SIEVE-BOOT to compute several million primes to be input by the other programs

Programs for the segmented sieve of Eratosthenes on 64-bit machines, tuned for finding all large gaps between primes in the neighborhood of 10^18 (May 2006)

MAXCLIQUES

The Moody--Hollis algorithm for listing all maximal cliques, all maximal independent sets, and/or all minimal vertex covers (July 2006, corrected November 2008)

ULAM and a change file for 64-bit machines

Short program to compute the Ulam numbers 1, 2, 3, 4, 6, ... (September 2006) --- but see the vastly improved version below, dated July 2016!

HWB-FAST

Short program to compute the profile of the hidden weight function, given a permutation of the variables (April 2008)

YPLAY

Simple program to play with Schensted's Y function (April 2008)

BDD12

A program to find the best and worst variable orderings for a given BDD (May 2008)

BDD14 and a typical driver program to generate input for it

Bare-bones BDD package that I used for practice when preparing Section 7.1.4 of TAOCP (May 2008; version of September 2011)

BDD15

Bare-bones ZDD package that I used for practice when preparing Section 7.1.4 of TAOCP (August 2008)

SIMPATH, SIMPATH-REDUCE, SIMPATH-EXAMPLE, and change files for cycles, Hamiltonian paths, and Hamiltonian paths with one endpoint given

Several programs to make ZDDs for simple paths of graphs (August 2008)

SIMPATH-DIRECTED-CYCLES

And another for simple cycles in directed graphs (August 2008)

BDD-ZDD-UTILS

A suite of programs to analyze computed BDDs and ZDDs

EULER-TRAIL

A simple algorithm that computes an Eulerian trail of a given connected graph (March 2010)

CELTIC-PATHS

A fun program to typeset certain Celtic knots, using special fonts CELTICA, CELTICA13, CELTICB, CELTICB13; you also need this simple illustration (August 2010)

NNNCMBX.MF

The font used for my paper ``N-ciphered texts'' (1981, 1987, 2010)

DRAGON-CALC

An interactive program to compute with and display generalized dragon curves (September 2010)

SQUAREGRAPH

Brute-force enumeration of all small squaregraphs --- an very interesting class of median graphs, generalizing polyominoes (August 2011)

SQUAREGRAPH-RAND

A short routine that generates more-or-less random pairs of chord edges, obtaining squaregraphs by "crocheting" them around the boundary

TREEPROBS and an illustration for its documentation

Computes probabilities in Bayesian binary tree networks (July 2011)

GRAPH-SIG-V0

A simple program that helps find automorphisms of a graph (July 2015)

SKEW-TERNARY-CALC and a MetaPost file for its illustrations

Computes planar graphs that correspond to ternary trees in an amazing way; here's a PDF file for its documentation

RANDOM-TERNARY

Implementation of Panholzer and Prodinger's beautiful algorithm for generating random ternary trees
(see also the change files RANDOM-TERNARY-QUADS and SKEW-TERNARY-CALC-RAW with which you can use this with SKEW-TERNARY-CALC)

DIMACS-TO-SAT and SAT-TO-DIMACS

Filters to convert between DIMACS format for SAT problems and the symbolic semantically meaningful format used in the programs below

SAT0

My implementation of Algorithm 7.2.2.2A (very basic SAT solver)

SAT0W

My implementation of Algorithm 7.2.2.2B (teeny tiny SAT solver)

SAT8

My implementation of Algorithm 7.2.2.2W (WalkSAT)

SAT9

My implementation of Algorithm 7.2.2.2S (survey propagation SAT solver)

SAT10

My implementation of Algorithm 7.2.2.2D (Davis-Putnam SAT solver)

SAT11

My implementation of Algorithm 7.2.2.2L (lookahead 3SAT solver)

SAT11K

Change file to adapt SAT11 to clauses of arbitrary length

SAT12 and the companion program SAT12-ERP

My implementation of a simple preprocessor for SAT

SAT13

My implementation of Algorithm 7.2.2.2C (conflict-driven clause learning SAT solver)

SAT-LIFE

Various programs to formulate Game of Life problems as SAT problems (July 2013)

SAT-NFA

Produce a forcing encoding of regular languages into SAT via nondeterministic finite automata (April 2016)

SATexamples

Programs for various examples of SAT in Section 7.2.2.2 of TAOCP; also more than a hundred benchmarks (updated 08 July 2015)

BACK-20Q and a change file for the paradoxical variant, and another

A backtrack program to analyze Don Woods's Twenty Questions (August 2015)

BACK-MXN-WORDS-NEW and BACK-MXN-WORDS-MXM. with some word lists

Demonstration backtrack programs for word rectangles (August 2015)

BACK-PDI

A backtrack program to find perfect digital invariants (e.g. 153=1^3+5^3+3^3) (September 2015)

BACK-PI-DAY

A backtrack program that solves exercise 7.2.2--68 with an interesting bitwise method (March 2018)

COMMAFREE-EASTMAN and COMMAFREE-EASTMAN-NEW

Eastman's encoding algorithm for commafree codes of odd block lengths (September 2015 and December 2015)

SAT-COMMAFREE

Clauses to construct binary commafree codes with one codeword per cycle class (September 2015)

BACK-COMMAFREE4

Finds all commafree 4-letter codes of given size on small alphabets (September 2015)

BACK-SKELETON

Finds potential skeleton multiplication puzzles whose special digits obey a given pixel pattern (January 2016)

BACK-DISSECT

Finds dissections of a square into a given shape (February 2016)

BACK-GRACEFUL-KMP3

Finds graceful labelings of the graphs $K_m\sqprod P_3$ (August 2020)

BACK-GRACEFUL

Finds all graceful labelings of a given graph (October 2020)

BACK-GRACEFUL-ROOTED-RANDOMRESTARTS

Tries to find rooted graceful labelings of difficult graphs (October 2020)

ULAM-GIBBS and the auxiliary illustration file ulam-gibbs.1

Computes billions of Ulam numbers if you've got enough memory (July 2016) (read the documentation)

DLX1

Algorithm 7.2.2.1X for exact cover via dancing links (September 2016 and August 2017, an update of the old DANCE program above)

QUEENS-DLX

Simple program to generate DLX data for the n queens problem

POLYOMINO-DLX, POLYIAMOND-DLX, and POLYCUBE-DLX

Programs to generate polyform data for the DLX solvers

SUDOKU-DLX, SUDOKU-GENERAL-DLX, and DLX1-SUDOKU

Improved programs for solving sudoku puzzles with DLX1

FILLOMINO-DLX

Converting a fillomino puzzle to an exact cover problem (May 2020)

DE-BRUIJN-DLX IAN-DLX MACMAHON-TRIANGLES-DLX MASYU-DLX PI-DAY-DLX SLITHERLINK-DLX TORTO-DLX WINDMILL-DOMINOES-DLX WORD-RECT-DLX

Miscellaneous additional driver programs for exact covering

DLX2

Algorithm 7.2.2.1C, the extension to color-controlled covers (September 2016, an update of the old GDANCE program above)

DLX-PRE

A preprocessor for DLX data (March 2017)

DLX2-POLYOM and DLX2-WORDSEARCH and DLX2-SHARP and DLX2-CUTOFF and DLX2-KLUDGE and DLX2-CUTOFF-KLUDGE DLX2-LOOP

Examples of change files typically used to reformat solutions found by DLX2 or to change its logic for column choice, etc.

DLX3

Algorithm 7.2.2.1M, the extension to general column sums (December 2017)

DLX3-SHARP and DLX3-SHARP-WORDCROSS and DLX3-REDRECT and DLX3-MOTLEY

Examples of change files for DLX3 (November 2017)

REDRECT-DLX and MOTLEY-DLX and QUEENDOM-DLX

Examples of driver files for DLX3 (March 2017)

DLX5

Algorithm 7.2.2.1C$, the extension to min-cost covers (July 2018)

DLX6

Algorithm 7.2.2.1Z, "dancing with ZDDs" (February 2019)

DLX6-NOMRV

a change file that branches on items in strictly left-to-right order

SSXCC0

a rewrite of DLX2, using sparse-set data structures "dancing cells" instead of dancing links (November 2020, revised November 2022)

SSXCC

improved version of SSXCC0 (October 2023)

SSXCC-WTD0 and SSXCC-FRB0

change files for SSXCC, they try experimental branching heuristics

SSXCC-BINARY

SSXCC0 modified to do binary branching not d-ary (December 2022; revised October 2023)

SSXCC-WTD and SSXCC-FRB

change files for SSXCC-BINARY, they try experimental branching heuristics

SSMCC

a rewrite of DLX3, using sparse-set data structures "dancing cells" instead of dancing links (November 2023)

SSMCC-WTD and SSMCC-FRB

change files for SSMCC, try experimental branching heuristics

XCCDC

a major extension of SSXCC, maintains full domain consistency (November 2022)

XCCDC-WTD and XCCDC-FRB

change files for XCCDC, try experimental branching heuristics

INFTY-QUEENS

Exploration of the infinity queens problem (November 2017)

GRACEFUL-COUNT and GRACEFUL-COUNT-SMALL

Counting graceful labelings that are connected (with graceful data structures!) (November 2019)

GRACEFUL-DLX and GRACEFUL-DLX-DOMAINS and GRACEFUL-DLX-PRESETS

To generate DLX2 data for graceful labeling (October 2020)

SQUAREPAL

Finds n-bit binary squares that are palindromic (December 2019)

HISTOSCAPE-COUNT and HISTOSCAPE-UNRANK

Enumerates $m\times n$ histoscapes that are trivalent polyhedra, or finds the $k$th solution in that enumeration (April 2020)

WHIRLPOOL-COUNT

Enumerates $m\times n$ whirlpool permutations for small $m$ and $n$ (April 2020)

WHIRLPOOL2N-ENCODE and WHIRLPOOL2N-DECODE

Exhibits a bijection between $2\times n$ whirlpool permutations and up-up-or-down-down permutations of size $2n-1$ (May 2020)

GRAPH-HASH

Quick way to compute an isomorphic variant that distinguishes small graphs (December 2020)

HOPCROFT-KARP

The Hopcroft–Karp algorithm for maximum cardinality bipartite matching (April 2021)

MATULA and illustration matula.S and illustration matula.T and illustration matula.ST

Efficient subtree isomorphism testing (May 2021)

MATULA-BIG and MATULA-BIG-PLANTED

Change files for MATULA allowing large trees in rectree format (May 2021)

MATULA-EXHAUSTIVE

Change file for MATULA that tests all m-trees against all n-trees (May 2021)

TCHOUKAILLON-ARRAYS

Generates some fascinating numerical patterns (June 2021)

OFFLINE-TREE-INSERTION

Tarjan's efficient solution to a new exercise about binary tree insertion (September 2021)

FLOORPLAN-TO-TWINTREE, FLOORPLAN-TO-TWINTREE-TTFORM, TWINTREE-TO-BAXTER, BAXTER-TO-FLOORPLAN

A trilogy of interesting bijections between floorplans, twintrees, and Baxter permutations (September 2021)

QUEENON-PARTITION, QUEENON-PARTITION.mp, QUEENON-PARTITION.0, QUEENON-PARTITION.1

A program to compute and illustrate Simkin's discretizations of “queenons” (September 2021)

PARTIAL-LATIN-GAD and changefile PARTIAL-LATIN-GAD-SWAP

Finds all ways to complete a partially specified latin square (a “quasigroup with holes”) (October 2021)

RANDOM-DFS-A and RANDOM-DFS-B

Empirical tests on the arcs of “jungles” produced by depth-first search on random digraphs, using two random models (November 2021)

RANK-PARADE1 and RANK-PARADE2 and UNRANK-PARADE1 and UNRANK-PARADE2

Ranking and unranking parades (March 2024)

OTHELLO

Experiments with Othello on rectangular boards and more than two players (May 2024)

PERFECT-PARTITION-SQUARE

An amusing recreation (June 2024)

INDICATOR-DLX

Experiments with the indicator problem (August 2024)

Programs in languages other than CWEB:

RANARRAY

Portable random number generator recommended in Seminumerical Algorithms, 3rd edition, new and improved version (last updated November 2002)

• C version, int (corrected September 2019 to agree with TAOCP)
• C version, double
• FORTRAN version, INTEGER (corrected September 2019 to agree with the C version)
• FORTRAN version, DOUBLE PRECISION (corrected December 2023 to agree with the C version)

tpk.i

The TPK algorithm in INTERCAL (version of November 2010); also some sample input and its corresponding output

SGBFIG

MetaPost sources for the illustrations in The Stanford GraphBase (1994)

color-mode.el

An experimental line-oriented color mode for Emacs (August 2000)

Sample Fvwm2 Config File

The emacs-oriented desktop layouts I use on my home computer to write books; these also need icons zero.xpm, one.xpm, two.xpm, three.xpm (May 2000, updated December 2007)

my6x13.bdf and my6x13B.bdf

TeX-oriented bitmap fonts that I use for text editing with emacs

DonKeys.keylayout and DonKeysExtended.keylayout

Custom keyboards for my Macintoshes -- more logical and efficient because they switch () with [], also + with = (April 2005); use them with DonKeys.icns and DonKeysExtended.icns

texmf-sail.tgz

source code listings for the first implementations of TeX and METAFONT (late 1970s)

tex.web

TeX version -0.25 as it existed when I gave twelve lectures on the internal details of TeX82 in July 1982

matulatree.m

Mathematica code to generate Matula trees in rectree format (May 2021)

randomfreetree.m

Mathematica code to generate a random free tree in rectree format (May 2021)

VOL1TEXT.txt

The text of TAOCP Volume 1, all uppercased, without spaces or punctuation or math or code

Datasets for exercises in The Art of Computer Programming:

wordlists.tgz

English words of lengths 2 thru 12 [OSPD4], ordered by frequency

Don Knuth's home page