REVIEW 5 cited by
Dancing links
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
read the original abstract
The author presents two tricks to accelerate depth-first search algorithms for a class of combinatorial puzzle problems, such as tiling a tray by a fixed set of polyominoes. The first trick is to implement each assumption of the search with reversible local operations on doubly linked lists. By this trick, every step of the search affects the data incrementally. The second trick is to add a ghost square that represents the identity of each polyomino. Thus puts the rule that each polyomino be used once on the same footing as the rule that each square be covered once. The coding simplifies to a more abstract form which is equivalent to 0-1 integer programming. More significantly for the total computation time, the search can naturally switch between placing a fixed polyomino or covering a fixed square at different stages, according to a combined heuristic. Finally the author reports excellent performance for his algorithm for some familiar puzzles. These include tiling a hexagon by 19 hexiamonds and the N queens problem for N up to 18.
Forward citations
Cited by 5 Pith papers
-
Resolvable Triple Arrays
A new construction produces resolvable triple arrays from symmetric and resolvable 2-designs, including infinite families in bijection with affine planes of order q and new examples for parameters like (21x15,63).
-
Tetris: Tile-level Sampling for Efficient and High-Fidelity Video Object Tracking
Tetris uses tile-level polyomino sampling and packing to materialize object tracks from stationary video with up to 68.8x throughput gain at under 5% HOTA loss.
-
Finding and counting permutations via CSPs
Permutation Pattern Matching can be solved in n^{k/4+o(k)} time and in O(1.6181^n) polynomial-space time, with matching counting algorithms and an ETH-based near-optimal lower bound for the counting problem.
-
An Integer Linear Programming Model for the Evolomino Puzzle
An ILP formulation for Evolomino encodes puzzle rules as linear constraints and supports generation of unique instances, with solver tests up to 18x18 grids.
-
Using Reasoning Models to Generate Search Heuristics that Solve Open Instances of Combinatorial Design Problems
LLM-generated search heuristics run through the CPro1 protocol with the reasoning model o3-mini-high produced verified constructions resolving open instances in 7 Handbook design families and newer problems.
Discussion (0). Continue with ORCID to comment.