Rellenar con piezas un tablero

Concurso de El Pais, mayo de 2011

Piezas del rompecabezas

Tenemos un tablero cuadrado de 9x9=81 casillas iguales y 20 piezas idénticas que forman una "S" o una "Z", según hacia donde se gire.

Se trata de ir poniendo piezas en el tablero en cualquier posición, como en un puzzle, con el objetivo final de cubrir el mayor número de cuadrados posible, o lo que es lo mismo, dejando vacíos el menor número de cuadrados posible. Cada cuadrado de la pieza ocupa exactamente un cuadrado del tablero y las piezas no se pueden solapar.

¿Cuál es el menor número de cuadrados que pueden dejarse vacíos en el tablero al recubrirlo con este tipo de piezas?

Nota: Las piezas son reversibles, es decir, podemos invertirlas y girarlas.

Solución