Dudeney's Star Puzzle

Tomado textual de mathpuzzle.com Alex Ravsky encontro una solucion mejor para un puzzle de Dudeney.

Similar como el caso de Klondike de Sam Loyd en los 70s.


The task of the star puzzle, ((X36 = AM329) according to the list [Knu] by Donald E.
Knuth) published a century ago in The Strand Magazine [Dud2], is to construct a path,
consisting of 14 straight strokes, on the following field of stars from one light star to the
other such that all the stars lay on the path.

Paper original puede ser obtenido en http://arxiv.org/abs/1205.0747

Four on a Match

Kadon has many fun puzzles and some contests.

by solving one of them, I received Four on a Match two years ago:

I think it was good time to publish it :P

Combinatorial Explosion

I think the discussion should have more emphasis in the best practice of using this kind of tool; Just like it is mentioned and used in the MatrixGame & TheLuckyString problems, we need to generate certain rules/filters to optimize the search. To look for all n! possibilities probably never will be a feasible solution. This is also called Combinatorial Explosion which verbatim refers to a growth almost impossible to sustain for the time of this type of TC problems.

So more important than the implementation ( which is assumed know -next_permutation()- that this is called Algorithm L in Knuth's TAOCP 4: 7.2.1.2) it is the good use some criteria for pruning combinations (permutations) and at the end we obtain a reasonable running time.

Many problems use this kind of booby-trap to let the programmer to try to solve with a plenty quick solution which runs over all permutations (or combinations) that finish with a timeout or an unnecessary overhead as resources used (such us memory).