El huerto de Papá Noel

Ayuda a Papá Noel a aumentar el número de árboles de Navidad que tiene en su terreno.

Instrucciones

Entrada

Papá Noel quiere plantar wants n árboles evergreen de Navidad en su huerto.

Su terreno es siempre un cuadrado de n parcelas por n parcelas.

Una parcela puede contener un árbol de Navidad.

Sin embargo, debido a su mágica estructura radicular, estos árboles evergreen  no crecerán si hay otro alineado horizontal, vertical o diagonalmente con el árbol.

Por ejemplo, dado n = 4 y si representamos un árbol con O y un lote vacío con - (guión), entonces hay 1 salida válida y 3 inválidas.

Dado un tamaño n, intenta encontrar una solución válida para colocar los árboles en una asignación de tamaño n. Si no hay solución válida, entonces devuelve una matriz vacío.

Lógica

Así, si n = 4, podemos colocar 4 árboles de Navidad en una cuadrícula de 4 x 4 (véanse los ejemplos a continuación). 

Sin embargo, si n = 2, no caben 2 árboles en una cuadrícula de 2 x 2 siguiendo estas reglas, por lo que devolveríamos la matriz vacía.

Salida válida - Ejemplo n = 4

Salida válida - Matriz vacía

Salida inválida - Ejemplo n = 4