These dissection puzzles often rely on a stair-step cut to reduce the dimensions of a figure. If we cut a 3x3 square out of the corner of the mosaic, we are left with an L-shaped figure two tiles wide. If we cut a stair-step pattern up from the opposite corner, we create a 3x2 piece with tail extending to a height of 4. This piece can be moved down to nest with the bottom piece. Then a 2x2 square can be cut from the right side of the bottom piece and raised to complete a 4x4 square.

Sam Loyd offers a different solution: