HOW to blindfolded SQ1

[Lucas Garron]

A while ago I tried to compute how many cases need to be fully learned if you allow making one initial turn speed bld style. Don't remember the number, but maybe a dozen or less. With two initial turns this of course gets reduced further, and this should then be fairly easy to learn and do.

Darn. I know this is a set cover problem, but I thought it would be more precisely be a vertex cover problem. Checking that again, I noticed I was wrong. Is there a name for the problem of having an undirected graph, a vertex considered covered iff itself or one of its neighbours is marked, and the task is to mark as few vertices as needed to cover all?

Yeah, that's a covering (as opposed to a packing). Even Mathworld agrees for n=1. I was trying to find a covering of all Square-1 shapes using Jaap's graph in Mathematica, but that never finished. (And even kastellorizo, with a "Master's in Algebraic Graph Theory," couldn't help !)
And then I decided it was useless. Better memorize the few 6-shapes (much less to keep in mind/refresh) and speed BLD those 4 twists to them -maybe memo those twists, too, if they're not obvious.

But I'd still love to know the minimal coverings for distances n=1 to 5.
(1 and 7 are trivial, and so is 6 if you know the graph. I know it has a diameter of 7, is any shape removed from more than one other shape by 7 twists?)

 

[Stefan]

No, it's not the vertex cover problem. That mathworld page sucks. The definition is at best incomplete, at worst wrong. Vertex cover according to both Wikipedia and mathworld's own diagrams is a set of vertices that covers all *edges*, not all vertices.

Did you try a greedy covering, always adding the vertex that covers the most not yet covered vertices?

Did you try a minimal covering for the two-steps sets? There the sets are much larger, thus you need fewer. Probably allows brute force.

Also, there's at least one shape (double square) that's clearly an end-point, having just one neighbour. Using this neighbour for the covering is no mistake and can be done right away. Not sure whether there are more end-points, though I'd guess not.