# Modeling tiling problems as SAT problems

I read that tiling problems can be modeled as satisfiability problems (2-SAT?), but the author did not explain how. Is this true? What would be an example?

By a "tiling problem" I mean you have a matrix and have to fill it up according to some constraint. For example, you might have to fill the matrix with a particular shape, or the values in the matrix have to adhere to some constraint. For example, imagine a partially filled matrix and the rule is that you have to fill it with values that are one more or one less than the adjoining values, or something like that.

• Where did you read this? What did the authors say to support their statement?
– Raphael
Apr 15, 2017 at 8:23
• In addition to Raphael's comments, the definition of "tiling problem" could be made more precise. Can we use an unlimited number of copies of the shape? Is there just one shape or multiple? (I don't see what filling cells with numbers has to do with tiling.) It might help to know what the problem is before trying to find algorithms for it.
– D.W.
Apr 15, 2017 at 10:03
• @D.W. The question is not about a specific problem. It is about a concept. It doesn't matter what example of a tiling problem the answerer chooses. I just want to understand the application of SAT to tiling. If the answerer wants to include an example, then they are free to use any tiling problem they choose as the example problem. Apr 15, 2017 at 12:35