Le maréchal Bugeaud se prêta volontiers à l’arrangement. « Il ne faut pas, écrivait-il au maréchal Soult, négliger les dons que la fortune nous offre. La partie habitée du désert nous est nécessaire politiquement et commercialement. Nous devons régner partout où a régné Abd-el-Kader, sous peine d’être sans cesse sur le qui-vive dans le Tell. Ce n’est que par la domination que nous pouvons ouvrir à notre commerce des relations avec l’intérieur de l’Afrique. Il faut aussi enlever à Abd-el-Kader les ressources qu’il pourrait trouver dans cette contrée et jusqu’à l’apparence même d’un reste de puissance. »
On a déjà un comment, pour agir rapidement dans le sud, le colonel Jusuf avait inventé le cavalier-fantassin monté à mulet. le général Marey voulut faire mieux ; ayant à s’enfoncer plus avant dans le désert, il s’inspira des souvenirs de la grande expédition d’Egypte et rétablit à sa façon le régiment de dromadaires jadis institué par le général Bonaparte. Pour commencer l’expérience, il mit 100 hommes sur 100 chameaux et leur fit exécuter des manœuvres : marches en bataille, marches en colonne, formations sur la droite, sur la gauche, en avant, en bataille. Au commandement À terre ! les hommes sautaient à bas de leur monture ; les numéros de 1 à 3 se formaient en ligne, tandis que les numéros 4 gardaient les animaux. L’épreuve ayant été satisfaisante, le général Marey organisa sa troupe.
Le chameau portait un homme avec son fusil, les sacs de deux hommes, une besace contenant leurs vivres pour vingt-cinq ou trente jours, et deux outres contenant ensemble de 10 à 12 litres d’eau, en somme, une charge de 150 à 160 kilogrammes. Un bridon de corde, un bât arabe légèrement modifié avec des étriers de bois à deux échelons, constituaient tout le harnachement. L’un des deux hommes marchait à pied avec son fusil, pendant que l’autre était monté ; toutes les 2 lieues ils alternaient. De la sorte, on pouvait faire de 12 à 13 lieues par jour.
Le 1er mai, la colonne chamelière partit de Médéa ; elle était le 14 à Taguine, où elle acheva de s’organiser. Elle comprenait 1,700 hommes du 33e de ligne, 230 du train, 30 artilleurs avec 2 obusiers de montagne, 140 spahis, 400 cavaliers des goums, 300 serviteurs arabes, 100 chevaux et mulets, 1,300 chameaux de guerre et de charge. Le 18, elle entra dans le Djebel-Amour, d’où elle déboucha, le 21, sur Tadjemout. Là, le général Marey trouva le khalifa Ben-Salem et les chefs des Ksour qui l’attendaient avec les chevaux de soumission.
Pour Aïn-Madhi, les choses n’avaient pas marché toutes seules. Mohammed-el-Tedjini, le marabout vénéré. L’ennemi juré d’Abd-el-Kader,
