My two year old taught me constraint solving
thecomputersciencebook.com
thecomputersciencebook.com
In true 2-year-old fashion, my kid would bend the rules as much as possible by literally forcing pieces to the edge of their tolerance to make things fit that shouldn't fit. 8 piece circle yea, cool, but with a sufficiently old brio set handed down for 40 years or whatever, you can totally make a 7 piece "circle" thing.
So I decided some day I'll craft an interview question out of that, to see if people can figure out a good way to map a set of pieces laid out with given tolerance ranges for piece, see if it can connect, etc. Haven't thought about it enough to really polish it for an interview, but some day.
A heuristic could try all kinds of fun force-directed placement stuff. For an exact solver, I think your best bet would (unfortunately) be to finely quantise the possible positions and orientations of each piece, describe each piece by 2 sets of positioned unit vectors (the vectors in one set start at the centre positions of each "hole" and are directed towards the centre of the piece, the other set is similar but holds the "plug" positions and orientations), and say that a partial solution is feasible iff every "plug" position is sufficiently far from all other plugs, and either sufficiently far from all other holes or within some small tolerances (in terms of both distance and angle) of some other hole. Actually, you would probably also need to treat the piece body as a "nothing else can occupy these positions" constraint. I say "unfortunate" because the position and orientation grids would need to be very fine relative to the size of the pieces, leading to a large state space thus long running times.
I think it would be fun to look for solutions that maximise the "badness" (e.g., sum of distances between matched holes and plugs) :)
so you work in some space where extremely good visual understanding and ability to abstract in 3 dimensions is a prerequisite?
But you have to think about something after hours of brio.
My understanding -- correct me if wrong -- is that this hugely complicates things because the search space expands so much. If you imagine three straight pieces in a row, with vrio they now form a fan of possible positions. Then with corners and so on you have a near infinite amount of wiggle room. To do it accurately you probably need to map out the physical space a given connector can move within, but for the visualisation I just loosened the "connectors must align" rule to be "connectors must be within 6mm of each other", which is wrong but fairly close.
Märklin C track needs this.
https://www.oranlooney.com/demos/soma-forest/
One of them used constraint solving with Z3, which was indeed reasonably fast. However, by far the fastest was a simple backtracking solver written in Rust which used bit twiddling to quickly test for intersections. For polyomino's in particular, this represents between 10x and 100x constant speed boost, depending on the size of board. There's no way to get that back with a smarter solver.
So we had a goal to make the train do interesting behaviors, like cover the entire track autonomously, pushing the switches itself. The biggest run I remember was a 4 bit counter.
Kid is now entering his last year of CS + Maths degree, so I guess it checks out.
Modern solvers such as CP-SAT combine some SAT features with a CP solver, based of the work of Peter Stuckey I think.
> “Dada! Degree three. No Euler circuit.”
…Oh. Okay, fine, weird rhetorical device but you do you.
If you introduce a bridge, or a tunnel, or put the goal in the middle, you can get stuck in a loop.
No, there's not really much chance of that:
>> “Dada, real planners use SAT and its relatives for timetabling, chip layout, and routing for the same reason.”