Triangles P76720

Trobeu totes les maneres de cobrir un tauler $n \times m$ amb peces de tres lletres idèntiques posades en forma de triangle, que es poden orientar de quatre maneres:

              zz        zz         z         z
              z          z        zz         zz

Ompliu el tauler recorrent-lo per files, de dalt a baix, i cada fila d’esquerra a dreta, fent servir lletres consecutives començant en ‘a’. Per a cada posició encara lliure, proveu de posar-hi un triangle de les quatre maneres anteriors, i en l’ordre indicat.

Per exemple, aquestes són dues maneres consecutives de cobrir un tauler $6 \times 7$:

                    aabccdd       aabccdd
                    abbecdf       abbecdf
                    ggheeff       ggheeff
                    ghhiijj       ghhiijj
                    kklimnj       kllimnj
                    kllmmnn       kklmmnn

Entrada

L’entrada consisteix en diversos casos, cadascun amb $n$ i $m$. Podeu suposar $6 \le n \cdot m \le 60$, i que les combinacions donades tenen almenys una solució.

Sortida

Per a cada cas, escriviu en l’ordre demanat totes les maneres de cobrir un tauler $n \times m$. Escriviu una línia amb 10 guions després de cada tauler, i una línia amb 20 asterics al final de cada cas.

Pista

La solució esperada per a aquest problema és un backtracking relativament simple.