El solitari de les pedres (1) P39965

Considereu un solitari consistent en un taulell n × n, on cada casella està buida o té una pedra. L’únic moviment permès consisteix a fer saltar una pedra sobre una altra de veïna (horitzontalment o verticalment), deixant la pedra moguda a la posició següent, que ha d’estar buida abans del salt. La pedra sobre la que s’ha saltat es treu del taulell. (És com el moviment de matar una fitxa del joc de les dames, però amb salts horitzontals o verticals en comptes de salts diagonals.) L’objectiu del solitari és acabar amb una sola pedra al taulell.

Feu un programa que digui si un solitari donat té solució o no. Si en té, cal dir si és possible que la pedra quedi a la posició del mig; en aquest cas direm que té una solució maca.

Entrada

L’entrada consisteix en un natural senar n ≥ 3, seguit de n files amb n caràcters cadascuna. Una ’X’ indica una pedra. Les posicions buides s’indiquen amb un punt.

Sortida

Escriviu "te solucio maca", "te solucio" o bé "no te solucio" segons convingui.