‘a 10 11 υ12:1 h21:1 h20:1, h10:0 h11:1 H’,
‘a 11 21 h11:0 υ12:0 υ22:1, h31:1 υ21:1 υ11:1 V’;
the goal is to find an exact cover with multiplicities 1 for patterns 1―9, multiplicities 3 for patterns a―i, and multiplicities 18 for H and V. (There are millions of solutions.)
Once that task is solved, we need to assign the actual dominoes whose subpaths jointly define a single loop. A (nontrivial) program, whose structure has a lot in common with Algorithm X, will find such assignments in microseconds (although a full day might be needed to actually write that program).
(b) Now H and V should have multiplicities 32 and 4. (Also, we can save about half of Algorithm M’s running time by omitting vertical placements at odd height.) The algorithm finds ...
Get The Art of Computer Programming, Volume 4, Fascicle 5: Mathematical Preliminaries Redux; Introduction to Backtracking; Dancing Links now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
