You don't have to slide across the squares as the pieces must be approximately centered.

You can probably perform the matching on a "generic" piece just to find the location; when you have the (approximate) location, you can try every piece, in a smaller window.

You can perform a fist search on a reduced image (and reduced templates) to get an initial approximation; then refine to full resolution.