2 ms·

Only half of the squares are empty, you can almost make a chechboard pattern with the pieces. I don't expect an easy small worst case.