2. a) L'autorité intimée soutient, dans ses observations, que certains des griefs formés par les recourants seraient irrecevables parce qu'ils sont allégués pour la première fois dans le recours de droit public. Ce point de vue appelle la distinction suivante.

Dans la mesure où les arguments développés par les recourants reposent sur des éléments de fait qui n'ont pas été invoqués en procédure cantonale, ils sont irrecevables, l'allégation de faits nouveaux n'étant pas admissible dans les recours de droit public soumis à l'exigence de l'épuisement des instances cantonales (ATF 102 Ia 246 consid. 2; ATF 99 Ia 86 consid. 3b). S'agissant, en revanche, de moyens de droit nouveaux développés dans de tels recours, la jurisprudence admet en principe leur recevabilité lorsque l'autorité de dernière instance cantonale jouissait d'un libre pouvoir d'examen et devait appliquer le droit d'office. Seuls font exception à cette règle les recours pour arbitraire et ceux où le grief de violation d'un autre droit constitutionnel n'a pas de portée propre et se confond avec le grief d'arbitraire (ATF 102 Ia 246 consid. 2; ATF 100 Ia 270 consid. 4a). Ne tombent cependant pas sous le coup de cette exception les recours pour violation d'un autre droit constitutionnel dans lesquels le grief soulevé a une portée propre alors même que le Tribunal fédéral ne l'examine qu'avec un pouvoir de cognition limité. Tel est le cas, par exemple, du grief de défaut de base légale dans un recours pour violation de la garantie de la propriété (art. 22ter Cst.). Un tel grief est en principe recevable dans les circonstances décrites ci-dessus, même si le Tribunal fédéral ne l'examine qu'avec un pouvoir restreint parce que l'atteinte à la propriété n'est pas particulièrement grave (arrêt non publié E. Schertenleib et consorts c. Conseil communal de Saint-Blaise du 3 novembre 1976).

Il n'est pas contesté que le Tribunal administratif jouissait en l'espèce d'un pouvoir d'examen libre et qu'il devait appliquer le droit d'office, ce qui, au demeurant, ressort clairement de l'art. 78 lettre a - en relation avec l'art. 79 al. 2 - de la loi valaisanne du 6 octobre 1976 sur la procédure et la juridiction administratives (LPJA). Par ailleurs, le présent recours de droit public est fondé tant sur l'art. 4 Cst. que sur l'art. 22ter Cst. Les arguments juridiques du recours, ainsi mis en discussion par l'autorité intimée, ne sont donc pas irrecevables du seul fait qu'ils n'auraient pas été allégués en procédure cantonale.