Fun and Games with CRV: Draw This Without Lifting Your Pencil
It's time for another installment in the "Fun and Games with CRV" series. I love doing these posts because there's something very engaging in modeling all sorts of problems as constraints. This time we're going to look at how to draw a barn without lifting our pencil from the paper and without doubling back. This wikiHow post shows us two ways how we could do that. Now lets see if we can write a solver that can find either of these solutions.
This problem is different from the other puzzle we've looked at before because it has a "time" component. We make moves one after the other and the order in which we make them limits what we can do in the next step. We know exactly how many moves we need to make; this is the number of edges the drawing has. This makes it easier to model, in comparison to more difficult problems where the number of steps is unknown.
While we are looking at how to draw a barn, this kind of puzzle is pretty widespread. Why not implement a more generic solver that can draw any type of figure? We can do this by splitting the solver part (the constraints) from the actual drawing we want to make. Such a drawing is merely a collection of edges, which connect two vertices each. These edges and vertices form a graph and what we want is to traverse it, by taking each edge exactly once. While for the drawing itself the direction of the edges doesn't matter (which is the start or the end vertex), it is important for how we draw the figure. We'll see how this impacts the solver later.
We'll encapsulate the task of modeling such a graph and the constraints needed to traverse it inside an own class. This drawer class (not the best of names, I admit) will provide a protected method that subclasses can call to define the edges of the drawing:
virtual class drawer;
typedef struct {
rand vertex_t v1;
rand vertex_t v2;
} edge_t;
protected function void add_edge(vertex_t vertex1, vertex_t vertex2);
// ...
endfunction
// ...
endclass
My first try was to store all of the edges inside an array and add a constraint to try and randomly select one from the list:
virtual class drawer;
local edge_t edges[$];
local edge_t dummy_edge;
constraint choose_existing_edges {
dummy_edge inside { edges };
}
endclass
This would have been too easy and probably have made for too short a post. "Fortunately", the SystemVerilog LRM doesn't allow this kind of construct, restricting us to using only singular types with the inside operator (integers, bit vectors, enums, etc.). We'll need to store the connected vertices in some other way if we want to be able to solve this problem. The best way (I could think of) is an associative array of queues indexed by the vertex and containing a list of all other vertices it's connected to directly via edges:
virtual class drawer;
typedef int unsigned vertex_t;
typedef vertex_t connections_t[$];
local connections_t connections[vertex_t];
endclass
Let's look at an example:
In the drawing above, this is what the connections matrix would contain:
1 : { 2, 3, 4 }
2 : { 1 }
3 : { 1 }
4 : { 1, 5 }
5 : { 4 }We can add to this data structure from the add_edge(...) function:
virtual class drawer;
protected function void add_edge(vertex_t vertex1, vertex_t vertex2);
if (connections.exists(vertex1) && vertex2 inside { connections[vertex1] })
$fatal(0, "Connection %0d -> %0d already exists", vertex1, vertex2);
connect_vertices(vertex1, vertex2);
connect_vertices(vertex2, vertex1);
begin
edge_t e;
e.v1 = vertex1;
e.v2 = vertex2;
edges.push_back(e);
end
endfunction
local function void connect_vertices(vertex_t src, vertex_t dest);
if (connections.exists(src))
connections[src].push_back(dest);
else
connections[src] = '{ dest };
endfunction
endclass
virtual class drawer;
local vertex_t vertices[$];
function void pre_randomize();
vertex_t v;
void'(connections.first(v));
do
vertices.push_back(v);
while (connections.next(v));
endfunction
endclass
At this point, it makes sense to try again and write a constraint that can select an edge from the ones we've added to the list. I wanted to try something fancy here:
virtual class drawer;
constraint choose_existing_edge {
dummy_edge.v1 inside { vertices } &&
dummy_edge.v2 inside { connections[dummy_edge.v1] };
}
endclass
The idea was to choose the first vertex at random. The second vertex we could then choose from the list of vertices connected to the first one. In theory, this is great, but in practice, this constraint doesn't work because the index we are using for connections (dummy_edge.v1) is a random variable itself and this doesn't seem to be allowed. I'm not entirely sure if this is a simulator limitation or if the LRM forbids it.
We shouldn't give up on the idea just yet. With a bit of massaging, we can get it to compile. In the second constraint expression we can just loop over all entries inside connections and stop when we've reached the one corresponding to our chosen "starting" vertex:
virtual class drawer;
constraint choose_existing_edges {
dummy_edge.v1 inside { vertices };
foreach (connections[v])
if (dummy_edge.v1 == v)
dummy_edge.v2 inside { connections[v] };
}
endclass
It's a little more code, but it does the job perfectly. Now we have a solid base to really start building our solver. We'll need to keep track of what edges we've already drawn and when. We'll store them in an array, where index 0 will be the first edge we drawn, index 1 the second and so on:
virtual class drawer;
local rand edge_t edge_being_drawn[];
endclass
The first constraint we'll write is that each edge we draw actually exists in the drawing. We've already written such a constraint for one edge, so we'll just extend it to cover all of them:
virtual class drawer;
constraint choose_existing_edges {
foreach (edge_being_drawn[i])
edge_being_drawn[i].v1 inside { vertices };
foreach (edge_being_drawn[i])
foreach (connections[v])
if (edge_being_drawn[i].v1 == v)
edge_being_drawn[i].v2 inside { connections[v] };
}
endclass
Just choosing edges that exist inside the figure isn't enough. We have to make sure that the edges are unique. Here I tried some more fanciness than the language affords. This constraint, though short and sweet, also doesn't compile:
virtual class drawer;
constraint choose_unique_edges {
unique { edge_being_drawn };
}
endclass
As with the inside operator, the unique operator also only works on integral types. I tried to outsmart the compiler by declaring the struct as packed, but then it can't be declared as rand so that won't get us anywhere. As before, we're just going to have to throw some more code at the problem:
virtual class drawer;
constraint choose_unique_edges {
foreach (edge_being_drawn[i])
foreach (edge_being_drawn[j])
if (i != j)
!(edge_being_drawn[i].v1 == edge_being_drawn[j].v1 &&
edge_being_drawn[i].v2 == edge_being_drawn[j].v2);
foreach (edge_being_drawn[i])
foreach (edge_being_drawn[j])
if (i != j)
!(edge_being_drawn[i].v1 == edge_being_drawn[j].v2 &&
edge_being_drawn[i].v2 == edge_being_drawn[j].v1);
}
endclass
As we already know from the previous post on array constraints we can replace a unique constraint with a double foreach. It's not enough to say that the starting or ending vertices be different. We also need to make sure that we're not backtracking. Going from vertex 1 to vertex 3 is the same edge when going from vertex 3 to vertex 1 (it's just the direction that's different).
One more constraint is missing to make the solution complete. We have to make sure that when going from one edge to another, the end vertex of the previous edge is the start vertex of the current edge. If we don't, then we're lifting our pencil from the paper. This is very easy to express:
virtual class drawer;
constraint choose_connected_edges {
foreach (edge_being_drawn[i])
if (i > 0)
edge_being_drawn[i].v1 == edge_being_drawn[i - 1].v2;
}
endclass
Let's test it out by trying to draw a barn. Here's how the vertices are numbered:
The barn_drawer class only needs to define the edges using the add_edge(...) function:
class barn_drawer extends drawer;
function new();
add_edge(0, 1);
add_edge(0, 2);
add_edge(1, 2);
add_edge(1, 3);
add_edge(1, 4);
add_edge(2, 3);
add_edge(2, 4);
add_edge(3, 4);
endfunction
endclass
We just need to randomize an instance of barn_drawer and we should get the instructions we need to solve our puzzle. Sadly, things are never this easy. Immediately after putting all constraints together I got a constraint violation. After looking at the "choose" constraints over and over and hitting my head on the table, some time later I found what the problem was; it wasn't in my code. As in the first installment of the series, when solving Sudoku, a simulator bug reared its ugly head, but this time it wasn't as easy to pinpoint. I should probably consider moonlighting as a QA for an EDA company since I seem to draw such issues to me. Getting to the point, if we add this slight modification to the choose_unique_edges constraint it's going to make the clouds go away:
virtual class drawer;
constraint choose_unique_edges {
// ...
foreach (edge_being_drawn[i])
foreach (edge_being_drawn[j])
// (Very) Possible bug in simulator
if (i == j - 1)
edge_being_drawn[i].v1 != edge_being_drawn[j].v2;
else if (j == i - 1)
edge_being_drawn[j].v1 != edge_being_drawn[i].v2;
else
// This condition should be enough by itself.
if (i != j)
!(edge_being_drawn[i].v1 == edge_being_drawn[j].v2 &&
edge_being_drawn[i].v2 == edge_being_drawn[j].v1);
}
endclass
And there we have it! Now we can solve any such "draw this without lifting your pencil" puzzle. We've also learned a bit more about the limitations of the SystemVerilog constraint language. I can't help thinking that the whole thing would have been much cleaner in e. I might try it out in the future just to see. If someone else does it, it would be nice to compare. In the meantime, you can find the code on SourceForge if you want to experiment drawing other figures.
Comments