Ciao!
La funzione gen_tree deve generare l'albero interamente, utilizzando la ricorsione. Per ogni configurazione iniziale (che è un vero e proprio nodo dell'albero) si dovranno trovare i figli, ovvero le mosse che è possibile fare (e volendo, aggiungerle all'attributo lista_figli di quel nodo). A questo punto ricorsivamente dovrai applicare lo stesso processo a tutti i figli del nodo iniziale e così via.
Inoltre fai caso al fatto che le possibili mosse sono 3 soltanto in un caso specifico, in generale potrebbero essere di più.
Spero di essere stato chiaro, se hai qualche dubbio chiedi pure ;)