Quadrats llatins P97271

Un quadrat llatí és una matriu n × n tal que cada fila i cada columna conté tots els nombres entre 1 i n. Feu un programa que, donades algunes posicions fixes d’una matriu n × n, compti totes les maneres de completar-la per formar un quadrat llatí.

Entrada

L’entrada consisteix en diversos casos, cadascun amb una n entre 1 i 9, seguida d’n files amb n caràcters cadascuna. Els punts indiquen posicions lliures, i els dígits entre 1 i n posicions fixes.

Sortida

Per a cada cas, escriviu el nombre de maneres d’omplir la matriu de forma que sigui un quadrat llatí. Sempre hi haurà, almenys, una manera.