Arranging Squares on a Quilt (with a bunch of rules)

Question

My wife is making a quilt. We are trying to figure out a way to arrange the squares that meets her aesthetic "requirements." I see a similar question here, but we've got two aspect variables and different rules. I'm wondering if somebody can work this out.

The squares:

• There are 126 squares.
• The squares come in 7 patterns (I will assign them numbers 1-7).
• Each pattern comes in 3 colors (but there are 5 colors total: white(w), red(r), light blue(b) teal(t), navy(n))
• For each pattern, there are 6 of each of its colors.

The break down is like this:

• Pattern 1: 1w, 1b, 1n
• Pattern 2: 2b, 2t, 2n
• Pattern 3: 3w, 3r, 3n
• Pattern 4: 4w, 4t, 4n
• Pattern 5: 5w, 5b, 5r
• Pattern 6: 6w, 6t, 6n
• Pattern 7: 7w, 7t, 7n

The rules:

• Making a quilt 9 squares by 14 squares
• No two squares of the same color can be adjacent (vertically or horizontally; diagonal is fine)
• No two squares of the same pattern (but different colors) can have fewer than 2 other patterns in between them, vertically or horizontally (so 1|2||,1 is fine; 1|2|1 or 1|1 are not).
• Squares of the same pattern AND color also must follow this rule, with the additional rule that they must have at least 1 square of a different pattern AND a different color between them diagonally.

Is this a solvable problem?

BONUS: She'd also be interested in a 11x11 arrangement and 10x12 arrangement with the same rules (though these would not use every square, of course - would appreciate the leftovers [5 and 6, respectively] each be a different pattern).

Answer 1

Your problem is typical constraint satisfaction problem which in your case can be formulated as a generalized cover set problem. Some condition should be satisfied exactly once (there is one and only one patch per place); some should be satisfied at most once (one or zero patches adjacent to the edge can be white); some conditions should be satisfied no more than 2 times (among patches on diagonal 1w 5w 1w, we can have any two of them, but not 3).

Unfortunately, I couldn't easily find the solver for a generalized cover set problem and I was too lazy to write it myself. So instead, I strengthened the last condition which is now:

• There should be at least 2 squares on the diagonal between two patches of same pattern and color

In that case, we don't have “no more than 2 times condition” and we can reformulate the problem in terms of graphs.

Consider all the possible placements of all the possible patches as nodes of a graph (21 patches × 9 rows × 14 columns = 2646 nodes). For example, node 1a1w means row 1, column a, pattern 1w. Now, if two nodes share the placement or the rule, we connect them by an edge. For example, 5b1w—5b6t (two patches cannot be at the same place); 5a4t-6a6t (two adjacent patches cannot have the same color) etc.

By doing that, We will get a big graph (2646 nodes, 80081 edges):

In that graph we want to find an independent set of vertices of size 9×14. Luckily there is a function for that in Wolfram Mathematica.

Below I will show a couple of quilts I found, so your wife can choose the best-looking one:

9×14

2t 5b 4t 3r 2t 5r 7w 3n 5b 2t 3r 5b 2t 3r
5r 4w 2b 1w 5b 3w 2b 7t 3r 1b 2n 3w 5r 2b
1b 2t 5r 4t 1n 2t 3r 5w 2b 3w 5r 2b 3n 5w
3r 5b 1w 2n 3r 5b 7w 3n 5r 2t 1b 5w 2t 3r
2b 6w 3n 5b 2t 3w 5r 2b 3w 5b 2n 3r 5b 2n
1n 2t 5w 3r 6n 2b 3n 5w 6t 3r 5w 2b 3w 5r
3w 5r 1b 2t 5w 6t 1b 3r 5b 2n 1b 5r 2t 1b
5b 1n 3w 5r 2b 1w 5r 6n 2t 5r 3n 4w 5b 3r
1w 3r 2n 1b 3r 5b 6t 2b 3r 1n 2b 3r 1w 2b

5r 2b 3n 5r 1b 3n 5w 1b 2t 5r 1b 4n 2b 5r
1b 3r 5w 2b 3w 5r 2b 3r 1w 2b 6w 5b 3r 7t
2t 5b 6t 3r 5b 2t 1n 5b 3n 4t 5r 1n 6t 2b
3r 1w 2b 5w 7t 1b 3r 2t 5r 3w 1b 2t 5r 4t
5b 2t 3r 1n 2b 5r 4t 3n 1b 2t 3r 5b 4w 1b
2n 5r 1b 2t 5w 3n 1b 7t 3w 5b 2n 1w 7t 3w
1b 3w 7t 5b 1n 2b 3r 4w 5r 1w 6t 3n 2b 5r
5r 7n 2b 3w 7t 5r 4t 1b 2t 3r 1b 5r 3w 1b
2b 5w 3r 2t 5b 1w 2b 3r 1w 5b 3w 1n 5b 3r

2t 5r 1b 7t 5r 3w 2b 4t 3r 5w 1b 3r 5b 2t
5b 4t 3r 5w 2b 7t 3r 5b 4w 2b 5r 7t 2n 5r
3r 2b 7t 1b 3n 5r 1b 2t 5r 1w 2t 5b 3w 1n
7t 5r 1w 3r 7t 2b 4n 3r 2b 4t 1b 3r 4t 2b
1b 3w 2b 7n 5r 3w 2t 5b 1w 3n 5w 2b 1w 5r
3r 1n 5r 2t 1b 7n 5r 2n 3r 1b 2t 5r 6t 1b
2t 5b 1w 3r 7t 2b 3n 1b 6n 5r 3w 4t 2b 3r
1b 3r 2t 1b 3n 5r 2t 3r 5w 2b 4n 6w 5r 2t
5r 2b 3w 5r 2b 4t 5b 2n 1b 3r 5b 2t 6n 5b

5r 2b 7t 1b 3r 2b 5r 7t 1b 6t 3r 2t 1n 3r
1b 4t 3r 2n 5b 4t 1b 3r 7n 2b 6n 3w 2b 7n
2t 5r 1n 3w 2t 5r 3w 1n 6t 3r 2t 5b 3n 1b
5b 1w 2b 5r 3n 2b 7t 5r 2b 6n 5r 2n 6t 3r
3r 6t 5w 1b 4t 3r 5b 6w 3r 2t 1b 3w 5r 2t
7w 5b 3r 6t 5b 7t 3w 1b 6t 5b 3r 6t 2b 5w
5r 7t 1b 5w 3r 2b 6n 5r 1w 6n 2b 5r 4t 3r
1b 3w 5r 2b 6t 5r 7t 6w 5b 3r 7t 1b 5w 2t
3r 5b 7t 3r 5b 6w 2b 3r 6t 1b 5r 2t 3r 5b

11×11

6w 3r 5w 1b 3r 2t 5r 1b 7t 5b 2t
5b 1n 4t 3w 6t 1n 2b 6t 5w 3r 1b
3r 6w 1b 5r 2b 3r 4t 5r 1b 2t 5r
6t 5b 3r 6t 1w 5b 7w 2b 4t 5w 2b
5r 3w 4t 2b 5r 7t 3r 1w 5b 3r 7t
2t 1b 5w 7t 3n 1b 6w 5r 2t 6w 5b
3r 7w 2b 5r 1w 3r 7t 6n 1b 5r 6t
7t 5r 3w 1n 5b 7n 1b 3r 6t 2b 3r
5b 3n 1b 7t 3r 1w 6t 2n 5b 3n 2t
3r 1w 5r 3w 1n 5b 3r 1b 2t 5r 1b
4t 5b 3n 1b 5r 6t 2b 5r 7n 2b 3r

5r 1b 6w 3r 2b 5r 3w 2b 6t 1b 2t
2b 3r 7t 5w 1n 2t 5b 4t 2n 5r 4w
3w 5b 1w 2n 5b 6w 2n 3r 5b 2t 7n
5r 2t 3r 1b 2t 5r 1w 2b 4t 3w 5r
2b 3w 6t 5r 3w 2b 6t 5r 1b 6t 2b
6w 5r 2b 6n 1b 3r 5b 6n 2t 5b 3r
5b 6t 3r 4t 5r 6t 2n 4t 5r 3n 4t
3r 1b 5w 2b 4n 5b 3r 2b 4n 1b 2n
6t 5r 2t 3r 7t 2n 1b 5w 3r 2t 5b
5b 3w 1b 5w 2b 4t 5r 3n 2b 5w 3r
3r 2b 5r 4t 3r 5b 2t 1b 5r 3n 1b

3r 2b 5r 1n 6t 2b 5r 7t 2b 5r 3n
5b 1w 6t 2b 3r 1w 2t 5b 3r 6w 5b
2t 5r 1b 3n 4t 5b 3n 6t 5w 2b 6t
1b 6n 2t 5r 1b 2t 5r 1b 6n 5r 3w
6t 3r 5b 1n 6t 3r 2b 7t 3r 4t 5b
5r 1b 6n 4t 2n 5b 1w 2n 5b 3w 2t
2b 6t 3r 2b 5r 6t 3n 5r 1w 2b 3n
1w 5b 2t 6n 1b 3r 2t 1b 3n 5r 1b
5r 2n 1b 3r 6t 2n 5b 3r 6t 1n 5w
2b 4t 5r 1w 2b 5r 3w 2b 5w 3r 2b
3r 1b 2t 5b 3r 1b 2t 5r 1b 2t 7w

2b 6n 5r 2n 1b 5r 7n 1b 2t 3w 5b
3r 7t 2b 5w 3r 2b 6t 5r 7n 1b 3r
1b 5w 3n 1b 2t 3w 5b 2n 3r 5w 2b
5r 2b 1w 3r 5b 6t 1w 7t 2b 3n 5r
6t 3r 5b 2n 7t 5w 2b 3r 5w 2t 1b
1b 7n 2t 5r 1b 3n 5r 2t 1b 5r 4w
7t 2b 1w 7n 3r 2t 1w 5b 3r 4t 5b
5b 3r 7t 2b 5w 1n 2b 4t 5w 1b 3r
2n 1b 5w 3r 1b 5r 4n 3r 2t 5r 7t
3r 2t 1n 5b 2t 4w 5b 2n 1b 3w 5b
1b 5r 2b 1w 5r 2b 3r 1w 5r 2b 3r

10×12

5r 2b 7n 3r 4t 5r 2b 4t 5r 2b 3w 5b
6t 3r 4w 6t 5w 1b 7t 5b 3n 1w 5r 2n
3w 7t 5b 4n 3r 6t 5w 2t 1b 3r 2t 1b
2t 5w 3r 2b 1w 5r 2b 3r 5w 2b 1n 3r
5r 2b 4t 3w 2t 1b 6t 5b 2n 1w 5b 2t
1b 3r 5w 1b 6w 4t 5r 2t 1b 5r 2n 1b
3w 1n 2b 5r 1n 3r 2b 1n 3r 2b 1w 3r
2t 5b 3r 2t 5b 6t 3n 5b 2t 3w 5b 2t
5r 3n 7t 1b 3n 2b 5r 3w 1b 5r 4t 1b
3w 2b 4n 5r 2t 3r 7t 2b 3r 6t 2b 5r

5b 2t 3r 5b 1w 3r 2t 5r 6w 1b 3r 5b
3r 5w 2b 3w 5r 1b 3w 2b 7t 5r 2n 7t
2b 3n 5r 1n 2b 7t 5r 6t 1b 2t 5b 3r
5w 1b 3w 5b 7w 3r 2b 7n 5r 3n 6t 2b
3n 5r 2t 3r 1b 2n 7w 3r 2b 7t 3w 5r
2b 7t 5b 1w 3n 7t 1n 5b 4t 2n 5b 1w
5r 1b 3r 2t 5w 1b 3r 2t 5r 1b 4t 2b
3w 2t 1w 5r 2b 3n 5b 1n 2b 4w 1n 5r
2b 3r 5b 1n 3w 5r 2t 3w 4n 5b 3r 7t
5r 1b 2t 3r 1b 7t 3r 5b 1w 3n 5w 2b

3r 2b 5r 1w 3r 2b 5r 1w 2b 5r 6t 2b
5b 3w 1b 2n 5b 7w 2t 5b 3r 7t 5b 3r
2t 5r 4t 3r 2t 5r 1b 7n 5w 3n 2t 1b
3r 1b 5w 7t 3w 2b 7t 3r 6t 2b 3w 5r
5b 7t 3r 5b 1n 6t 5r 2b 4n 5r 6t 2b
7w 5r 1b 2t 5r 3n 1b 6t 3r 4t 5b 3r
1b 2t 5w 3r 2b 5w 3r 1n 5b 3n 2t 5w
5r 3n 2b 7t 3w 1b 6t 2b 4t 5r 3w 2b
2b 5w 3r 1b 5r 2n 1w 5r 6w 1b 4t 3r
3r 2t 5b 3w 2t 5b 3r 6t 5b 3r 1w 5b

5b 4t 1b 2t 5r 1b 2n 5b 3r 2t 1b 5r
3w 2b 5r 1n 2b 3w 5r 2t 1w 5b 3r 2b
4t 3r 2n 5b 4t 2n 1b 3r 2b 1n 5w 3n
2n 5b 4t 3r 1b 5r 2t 1n 5w 3r 1b 5r
3r 2t 5r 4n 2t 1w 3r 2b 4t 5b 3w 2b
5w 4n 2b 1w 3n 4t 5b 6t 3r 2t 5r 3n
2b 1w 3n 5r 1b 3r 4n 1b 5w 3n 2b 5w
4w 3r 5b 2t 4w 5b 7t 3w 2b 5r 3w 1b
5r 2b 4t 1b 3r 4t 2b 5r 3n 2t 5b 3r
7t 4n 3w 5r 2t 1b 3r 2t 5b 3r 7t 5w