La Conferència de Pau de la Federació Y63099

La Federació de Planetes Units organitza una important conferència de pau on assistiran N delegacions de diferents espècies: Vulcanians, Klingons, Romulans, Bajorans, Ferengis, i altres. El Capità Picard de la USS Enterprise ha estat assignat per organitzar aquesta delicada reunió.

Degut a les conegudes tensions galàctiques, el capità s’enfronta a un repte diplomàtic important: les N delegacions s’han de col·locar en una sala de conferències que té forma de quadrícula N×N, amb una delegació a cada fila i una a cada columna.

Les tensions diplomàtiques creen les següents restriccions:

Cap delegació pot estar en línia recta amb una altra (mateixa fila o columna) per evitar enfrontaments visuals directes.

Cap delegació pot estar en diagonal amb una altra, ja que els protocols de seguretat de la Federació prohibeixen possibles atacs indirectes a través dels camps de visió lateral.

A més, tots els diplomàtics volen estar el més a l’esquerra possible de manera que, de totes les configuracions possibles, caldria preferir la configuració lexicogràficament més petita (si considerem que les columnes i les files van numerades de 0 a N-1). Això no és un problema massa important, ja que si comencem a omplir la sala des de la primera columna i la primera fila (el seient 0,0), la primera solució que trobem ja és la que volem.

La teva missió, com a oficial de ciències, és desenvolupar un algorisme que ajudi el Capità Picard a trobar una possible configuració de seients que satisfacin aquestes condicions diplomàtiques, o determinar si tal distribució no és possible.

Entrada

Un nombre enter N (1 ≤ N ≤ 20) que representa dues coses a l’hora: El nombre de delegacions i la mida de la sala de conferències.

Sortida

Si no existeix solució, un missatge indicant: "Impossible establir la configuració diplomàtica." En cas contrari, una representació de la sala de conferències on cada posició (i,j) conté un "D" si hi ha una delegació o un "." si està buida.