Nombre parell d'ics P20151

Donada una matriu $n \times n$ de caràcters, amb algunes posicions lliures i algunes fixades, l’heu de completar amb punts i ics de manera que cada fila i cada columna tingui un nombre parell d’ics.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb la mida $n$, seguida d’$n$ files amb $n$ caràcters cadascuna. Els ‘.’ i ‘X’ marquen posicions fixades. Els ‘?’ indiquen una posició encara per determinar. Podeu suposar que $n$ està entre 1 i 20, i que sempre hi ha almenys una solució possible.

Sortida

Per a cada cas, escriviu en ordre lexicogràfic totes les solucions possibles. Per ordenar-les, suposeu que les recorreu per files de dalt a baix, i cada fila d’esquerra a dreta. Tingueu en compte que un ‘.’ va abans que una ‘X’. Escriviu una línia buida després de cada solució, i una línia amb 10 guions al final de cada cas.

Puntuació

La solució esperada és un backtracking raonablement optimitzat. El jutge us donarà una estimació de la nota màxima que podeu treure (7 o 10) en funció de l’eficiència del vostre codi. En qualsevol cas, tots els últims enviaments s’avaluaran manualment, inclosos els que rebin 0 punts automàtics.