1
$\begingroup$

I'm using Knuth's Dancing Links (dlx) algorithm to solve for solutions to tiling a 2xN rectangle using 3 different pieces of one, two, or three squares. It's working correctly in its basic form but now I want to add some additional constraints that limit how the pieces can fit together. I want the solutions to adhere to a rule that states that 4 pieces cannot share a common point. To me, this implies some sort of memor, or finite state machine, is required so that only a subset of available pieces can be used based on previous piece insertions.

To depict this graphically, if the solver has proceeded to the following state:

 > -----+--+
    >      |  |
    > -----+--+
    >      |
    > -----+

There is no other piece that can be placed that won't violate the rule so the solver would backtrack one level and try the next option. If that option happened to be

> -----+--+
>      |  |
> -----+  +
>      |  |
> -----+--+

The placement of this vertical piece means that the rule won't be violated at this stage so the solving may continue.

Can additional constraints be devised to reject states that will violate the rule as necessary?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.