Kitchen Generator III

I did construct a knapsack solver for kitchen layouts with heavy computation to check adjacency rules, and to generate every possible solution in the known universe. It needed to have its results trimmed to some 500 solutions max to not kill the webpage (I have no technical skills). After this I felt that a more thought out logical and heuristic approach would be more impactful (or at least increase my iteration time).

A knapsack solver, for anyone who skipped that lecture, packs items into a fixed capacity. Here the capacity is the wall and the items are appliances and cabinets, so a solution is any row that adds up to exactly the wall length. The trouble is how many of those there are. Take the run in the solver’s picture below: 204″, which is 17 feet, with a 33″ sink, a 30″ range and a 24″ dishwasher. That’s 87″ of appliances and 117″ of casework. Fill the casework from Cabinets I’s widths, 18″ to 36″ in 3″ steps, and 36 different mixes of cabinet widths add up to exactly 117″, using four to six cabinets. Put each mix in order and you get 876 rows of cabinets. Slot the three appliances in anywhere, in any order, and that one wall has 281,064 exact fits. A cap of 500 shows less than a fifth of one percent of them.

What the solver showed

Here is a result from the knapsack solver:

Read each row as one wall, left to right. All ten start the same way: 18″ cabinet, 18″ cabinet, sink, 18″ cabinet, range. That’s the first 117″. Only the last 87″ change, and they change by shuffling the same few pieces: a 27″ cabinet, the 24″ dishwasher and a 36″ piece that is sometimes a cabinet and sometimes a refrigerator. Row five drops the dishwasher for an 18″ and a 33″ cabinet. So the fridge looks optional to this solver, a 36″ item that could stand in for a 36″ cabinet. Ten solutions, one kitchen, rearranged at the tail.

The adjacency check is harder to see. Kitchen Generator I had two rules: no fridge beside the range, no dishwasher beside the range. Six of these ten rows break one of them. Rows five through seven put the fridge against the range; rows eight through ten put the dishwasher there. Whatever the solver checked, it wasn’t those two, and the record doesn’t say which rules it did use. The rebuilt drawing follows the picture and leaves adjacency unconstrained.

To get a sense of just how many possible arrangements check out the first ~500

Video: watch the screen recording

What the drawing counts

The drawing keeps the picture’s appliance widths, a 33″ sink, 30″ range and 24″ dishwasher, plus an optional 36″ or 48″ fridge, and the 18–36″ cabinet family. What you change is the wall, from 12 to 20 feet in one-foot steps, and the fridge. The line above the plans counts every exact fit for that wall. The plans are as many of those fits as the pane holds, all at one scale, so a shorter wall draws shorter.

The first number is the point. A 14′ wall has 8,640 exact fits. The 17′ run from the picture has 281,064, about 32 times as many for three more feet. One more foot, an 18′ wall, makes it 859,824, roughly three times the 17′ count. At 20′ it’s 7,763,808. Adding the 36″ fridge to the 17′ run brings the count down to 64,680, even though there’s one more appliance to place, because the fridge eats 36″ of casework. The 48″ fridge leaves 18,360. The count grows with the casework, not the appliance list: every extra foot of cabinet is more ways to split it and more places to put the appliances.

Rules don’t fix this. Apply Kitchen I’s two range rules to the 17′ run and 210,232 of the 281,064 still pass. The rules remove about a quarter, and you can’t write enough of them to get from 210,232 to a handful. That count uses the drawing’s widths with the two rules applied; the drawing marks the plans that break them with ✕ and keeps them.

How it picks

The drawing doesn’t list the 281,064 and then filter. At 17′ it keeps 12 of the 36 cabinet mixes: the tightest and the widest spread of widths at each cabinet count, the pictured mix of 18, 18, 18, 27 and 36, then whichever mix is farthest from the ones already kept. It lays each one out in all six appliance orders, with up to six ways of spreading the cabinets between the appliances. That’s 396 candidates, which happens to be about the size of my original 500 cap, and still far too many to read.

Then it picks. Plan one is the pictured layout. Each next plan is the candidate that scores as most different from the plans already shown. A different cabinet mix scores most, 18 points against each plan already shown. A different set of appliances touching each other scores 12, a different appliance order 8, a different pattern of cabinets and appliances 6, and a different spread between the smallest and largest cabinet 3. Those weights are judgment calls in the rebuild, not something a kitchen told anyone.

The first five read like five kitchens instead of five copies. Plan two puts all the cabinets on the left and packs the sink, dishwasher and range together on the right. Plan three uses three 27s and a 36 and starts the appliances at the range. Plan four puts the range third from the left and the sink at the far end. Plan five uses six cabinets, the most of the five, and splits them on both sides of the sink. Two of the five, plans two and four, put the dishwasher beside the range, the way the picture does. Under Kitchen I’s rules they’d be out.

Since I like to avoid forcing the user to pick one of basically the same, perhaps we need a better method of generating a meaningful kitchen (say diffs on lengths, where my intuition is leading me).

The judgment

Brute force answers the wrong question. It answers “what fits,” and a 17′ wall has 281,064 answers. A person choosing a kitchen wants “what’s different,” and to them two layouts that split 54″ of cabinets as 27 + 27 instead of 24 + 30 are the same kitchen. The ten rows in the picture are one kitchen. Rules only make the list legal, not shorter in any way that matters. Cutting thousands of fits to a few worth showing takes a measure of how far apart two kitchens are, and then showing the ones farthest apart. The rebuild scores the cabinet mix highest, which is the diffs-on-lengths hunch above, written down as a number.

That is as far as this series takes the room. Room Based BIM I argued that the wall should be the result of the room, but every kitchen after it still sat against a wall the post took as given, a 12-foot run or a 17-foot one. The last part of the path takes that argument to the whole plan: store the rooms, and let the walls, doors and stairs come out of how the rooms touch.