Faits: Faits: A. A.a F._, né en 1955, exerçait la profession de manoeuvre dans le bâtiment. Il a déposé une demande de mesures de réadaptation professionnelle de l'assurance-invalidité, le 21 janvier 2000, en alléguant souffrir de douleurs dorsales depuis janvier 1997. Son médecin traitant, le docteur B._, attestait une incapacité de travail variant de 50 à 100 % depuis le 3 avril 1998, en raison de lombalgies chroniques d'origine statique, avec hyperlordose (rapport du 5 mai 2000). Ce diagnostic a été posé précédemment par le docteur C._, médecin-chef à l'Hopital X._, après que l'assuré y eut séjourné du 20 mars au 7 avril 2000, pour traitement et réadaptation. Le docteur C._ a toutefois estimé que les atteintes organiques étaient modestes et n'entraînaient plus d'incapacité de travail dans la profession exercée jusqu'alors; il a proposé une reprise du travail à 50 % dès le 17 avril 2000, puis à 100 % dès le 1er mai suivant (rapport du 13 avril 2000). Le 8 mai 2000, F._ a repris le travail à plein temps. Par décision du 15 août 2000, l'Office de l'assurance-invalidité du canton de Neuchâtel (ci-après : l'Office AI) a rejeté sa demande de prestations. L'assuré a déféré cette décision au Tribunal administratif du canton de Neuchâtel, en alléguant la persistance de douleurs dorsales et en produisant un rapport médical établi le 13 septembre 2000 par le docteur B._, qui attestait une incapacité de travail de 50 % depuis le 28 août 2000. Par jugement du 8 décembre 2000, le Tribunal administratif du canton de Neuchâtel a annulé la décision litigieuse et renvoyé la cause à l'Office AI pour instruction complémentaire et nouvelle décision. D'après la juridiction cantonale, les documents médicaux figurant au dossier ne permettaient pas de déterminer s'il était exigible de l'assuré «qu'il s'efforce de se réadapter lui-même dans d'autres professions dites légères», ni si un tel reclassement professionnel était nécessaire. A.b Après réception de ce jugement, l'Office AI a appris que La Bâloise Assurances, qui assurait F._ contre la perte de gain en cas de maladie, avait confié une expertise médicale au docteur O._, spécialiste en chirurgie orthopédique. Selon le rapport d'expertise du 29 mars 2001, dont l'Office AI a obtenu une copie, l'assuré souffre de «lombalgies chroniques sur importante hyperlordose constitutionnelle, entraînant une discopathie lombo-sacrée et secondairement L4-L5». Le docteur O._ soupçonnait un début de syndrome somatoforme douloureux chronique et posait encore les diagnostics de début de cervicarthrose basse et d'un «impingement» de l'épaule droite sur conflit sous-acromial. A l'époque de l'expertise, le médecin traitant de l'assuré attestait une incapacité de travail de 75 %. Le docteur O._ a, pour sa part, proposé une reprise du travail à 50 %, dans l'activité exercée jusqu'alors, en précisant toutefois qu'un changement de profession était nécessaire. Du 11 au 28 mars 2002, F._ a suivi un stage d'observation au Centre Y._. Selon le rapport de stage, l'assuré a produit un travail de qualité, mais à un rythme lent; il décrivait des douleurs s'accentuant dans la journée, de sorte que les maîtres de stage n'ont proposé aucun plan de formation au Centre Y._ (rapport de stage du 17 avril 2002). Le conseiller en réadaptation de l'Office AI a alors proposé de renoncer à une mesure de réadaptation et d'étudier la question du droit à la rente, en se fondant sur une incapacité de travail de 50 % dans une activité adaptée; cette capacité de travail était au demeurant très théorique, notamment en raison du faible niveau de scolarisation de l'assuré, qui apparaissait usé et n'avait plus la possibilité de mobiliser d'autres ressources pour s'investir dans une nouvelle activité (rapport initial de réadaptation du 29 mai 2002). Le 7 août 2002, l'Office AI a refusé l'octroi de mesures d'ordre professionnel à l'assuré, en précisant qu'il statuerait ultérieurement sur le droit à la rente. Il a ensuite confié au docteur S._ le soin de réaliser une expertise psychiatrique. Ce médecin a établi son rapport le 28 avril 2003 et constaté que l'assuré souffrait d'un état dépressif subclinique léger et d'un trouble douloureux associé à la fois à des facteurs psychologiques et à une affection médicale générale chronique. Il a nié toute incapacité de travail en raison d'une atteinte à la santé psychique. Par décision du 6 août 2003 et décision sur opposition du 3 novembre 2003, l'Office AI a nié le droit de l'assuré à une rente d'invalidité. Il a considéré que celui-ci disposait encore d'une capacité de travail de 80 % au moins comme manoeuvre dans le bâtiment et de 100 % dans une activité dite «légère», ce qui excluait un taux d'invalidité ouvrant droit à une rente. Par décision du 6 août 2003 et décision sur opposition du 3 novembre 2003, l'Office AI a nié le droit de l'assuré à une rente d'invalidité. Il a considéré que celui-ci disposait encore d'une capacité de travail de 80 % au moins comme manoeuvre dans le bâtiment et de 100 % dans une activité dite «légère», ce qui excluait un taux d'invalidité ouvrant droit à une rente. B. L'assuré a recouru devant le Tribunal administratif du canton de Neuchâtel, en produisant notamment un rapport établi le 21 janvier 2004 par le docteur H._. Selon ce praticien, l'assuré souffre de «douleurs lombaires à caractère mécanique, depuis plusieurs années, dans le cadre de troubles dégénératifs radiologiquement modérés, mais invalidants, compte tenu d'un syndrome lombovertébral persistant, non amélioré par un traitement conservateur bien conduit.» Toujours selon le docteur H._, l'assuré souffre également de «douleurs cervicales à caractère mécanique dans le cadre de troubles dégénératifs et de douleurs de l'épaule droite avec, cliniquement, des signes de tendinopathie de la coiffe des rotateurs. [...] Si l'on voulait objectiver des lésions de la coiffe des rotateurs, il faudrait réaliser une IRM qui certainement montrerait une déchirure ou des signes de tendinite de la coiffe [...]». Le docteur H._ attestait que «d'un point de vue purement rhumatologique», les atteintes à la santé de l'assuré ne lui permettaient pas de reprendre son activité professionnelle antérieure, mais qu'une activité adaptée, sans mouvements répétitifs des membres supérieurs, sans port de charges, permettant la déambulation, sans position statique prolongée supérieure à 20 ou 30 minutes, pourrait être envisageable à 50 %. D'un point de vue global (psychologique et physique), une reprise d'activité professionnelle semblait toutefois utopique. Par jugement du 29 juillet 2005, le Tribunal administratif du canton de Neuchâtel a annulé la décision sur opposition du 3 novembre 2003 et renvoyé la cause à l'Office AI pour instruction complémentaire et nouvelle décision. La juridiction cantonale a considéré que les pièces médicales figurant au dossier ne permettaient pas de se prononcer sur la capacité de travail résiduelle de l'assuré eu égard aux atteintes à sa santé physique. Par jugement du 29 juillet 2005, le Tribunal administratif du canton de Neuchâtel a annulé la décision sur opposition du 3 novembre 2003 et renvoyé la cause à l'Office AI pour instruction complémentaire et nouvelle décision. La juridiction cantonale a considéré que les pièces médicales figurant au dossier ne permettaient pas de se prononcer sur la capacité de travail résiduelle de l'assuré eu égard aux atteintes à sa santé physique. C. L'Office AI interjette un recours de droit administratif contre ce jugement, dont il demande l'annulation. L'intimé conclut au rejet du recours, sous suite de dépens, alors que l'Office fédéral des assurances sociales a renoncé à se déterminer.