Triangles P76720

Trobeu totes les maneres de cobrir un tauler n × 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 × 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 ≤ n · m ≤ 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 × 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.