Use a greedy, recursive approach. 1. While the board still has area, take the largest square that fits into the remaining rectangle. 2. Subtract that square, leaving at most one smaller rectangle on each side. 3. Recurse on each leftover rectangle. If the board is a rectangle of dimensions \(w \times h\) with \(w \ge h\), you cut a square of side \(h\). This is exactly the Euclidean algorithm: each step you replace \((w,h)\) with \((w-h,h)\). The process ends when one dimension is zero, meaning the board has been tiled perfectly. The waste is zero if you can only use squares of the same size; otherwise you’ll end up with a few leftover strips. To minimise waste, choose the greatest common divisor of the sides as the square size, then apply the same greedy cut on the remaining strips. That gives you the fewest and smallest waste pieces.