Cómo llenar un tablero cuadrado de 2 ^ n * 2 ^ n con un bloque que falta con mosaicos en forma de L

Answer 1

Supongo que la pregunta que haces es el problema del tablero de ajedrez defectuoso. Déjame exponer el problema primero.

Un tablero de ajedrez defectuoso es un tablero de cuadrados 2 ^ n * 2 ^ n con exactamente un cuadrado defectuoso.
Cuando n = 0, solo hay un posible tablero de ajedrez defectuoso.
Cuando n = 1, hay 4 posibles tableros de ajedrez defectuosos.

Ahora, un tablero de ajedrez defectuoso con n = 0 se puede cubrir fácilmente ya que no tiene cuadrados no defectuosos. Aquí, el número de mosaicos es cero.
Para n = 1, hay exactamente tres cuadrados no defectuosos (sin sombrear en la imagen de arriba) y se pueden cubrir fácilmente con el mosaico en forma de L en una de las orientaciones.

Podemos utilizar la metodología de divide y vencerás para resolver este problema. El método sugiere reducir el tablero 2 ^ n * 2 ^ n en tableros de ajedrez defectuosos más pequeños y luego colocarlos en mosaico. Una forma natural de pensar es dividir el tablero 2 ^ n * 2 ^ n en cuatro tableros 2 ^ (n-1) * 2 ^ (n-1).

Tenga en cuenta que solo uno de los cuatro subcuadrados es defectuoso. Entonces, colocamos el mosaico en forma de L de tal manera que los tres subcuadrados restantes también sean defectuosos.

Esta técnica de partición convierte el problema original en 4 subproblemas que pueden resolverse de forma recursiva. La recursión termina cuando el tablero se ha reducido a 1X1 (que no tiene un cuadrado no defectuoso, por lo tanto, no es necesario colocar fichas).

Espero que esto ayude. 🙂