You can also have a computer solve a block puzzle. This article introduces the most basic way to do it.
The Idea: Start From the Top-Left Empty Cell
The computer repeats the following steps.
- In the frame, find the top-left empty cell (look from the top row down, and from the left within each row).
- Take each unused piece one by one, in every rotation, and check whether it can be placed to cover that cell.
- If it can be placed, move on to the next empty cell (go back to step 1).
- If no piece can be placed, take off the piece you placed just before and try the next candidate.
- When there are no empty cells left, you have found a solution.
The top-left empty cell is always covered by the top-left cell of some piece. So you only need to try placements that line up a piece’s top-left cell with it, and you do not need to try any other positions.
In the diagram above, after the first piece is placed, the top-left empty cell is row 2, column 1 (the gold ring). Next, you try only the placements that cover this cell.
This way of searching, going as far as you can and backing up to try another path when it fails, is called depth-first search (backtracking).
In JavaScript
The frame is a table of true (empty) and false (filled), and a piece is a list of its cells as [row, column]. The cells of a piece are sorted from the top row down, and from the left within each row.
// frame: true marks an empty cell. piece: a list of [row, col] cells
function rotate(shape) {
const turned = shape.map(([r, c]) => [c, -r]);
const minR = Math.min(...turned.map(([r]) => r));
const minC = Math.min(...turned.map(([, c]) => c));
return turned
.map(([r, c]) => [r - minR, c - minC])
.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
}
function solve(frame, pieces) {
const rows = frame.length;
const cols = frame[0].length;
const used = pieces.map(() => false);
let count = 0;
function search() {
// find the top-left empty cell
let at = -1;
for (let i = 0; i < rows * cols && at < 0; i++) {
if (frame[Math.floor(i / cols)][i % cols]) at = i;
}
if (at < 0) {
count++; // everything is filled
return;
}
const r0 = Math.floor(at / cols);
const c0 = at % cols;
pieces.forEach((piece, p) => {
if (used[p]) return;
let shape = piece;
const seen = new Set();
for (let turn = 0; turn < 4; turn++, shape = rotate(shape)) {
const key = JSON.stringify(shape);
if (seen.has(key)) continue;
seen.add(key);
// line up the shape's top-left cell with the empty cell
const [dr, dc] = shape[0];
const cells = shape.map(([r, c]) => [r - dr + r0, c - dc + c0]);
const fits = cells.every(
([r, c]) => r >= 0 && r < rows && c >= 0 && c < cols && frame[r][c]
);
if (!fits) continue;
cells.forEach(([r, c]) => (frame[r][c] = false));
used[p] = true;
search();
used[p] = false;
cells.forEach(([r, c]) => (frame[r][c] = true));
}
});
}
search();
return count;
} Give solve a 4×5 frame and the five pieces P, T, L, S, and the 3-cell L, and it returns 8. This means the example in How to Solve Block Puzzles has 8 solutions, counting rotated orientations.
Backing Up Early
The code above keeps going until no piece can be placed. But the moment a small closed-off gap forms, you can already tell there is no solution beyond it.
Each time you place a piece, check the sizes of the chunks of empty cells, and if a chunk has a size that the remaining pieces cannot make, back up right away. This alone cuts down the amount of searching a great deal.
When I counted every solution for packing the 12 pentominoes into a 3×20 rectangle, it was still not done after 10 minutes before adding this trick. With it, it finished in about 6 seconds (this was a calculation made while writing this site’s articles, and the time varies with the computer).
How the App’s Hint Works
The Hint in the Wood Block Fit app also uses the same depth-first search.
- It tries only the placements that cover the empty cell with the lowest number.
- For pieces of the same shape that match after rotating, it tries just one.
- It backs up when a closed-off gap smaller than a piece appears.
- It sets an upper limit on the number of positions to examine, so it does not take too long.
If the frame can still be filled from your current placement, it makes the piece covering the hardest empty cell to fill, and where it goes, glow. If it cannot be filled, it compares against the solution made at the start, makes a piece that does not match glow, and tells you, “Take out the glowing piece to get back on track.”
For how puzzles are made, see How We Make Puzzles That Are Always Solvable, and for the number of solutions for the 12 pentominoes, see Pentomino Solutions.
